Competitive influence maximisation using voting dynamics

Abstract

We identify optimal strategies for maximising influence within a social network in competitive settings under budget constraints. While existing work has focussed on simple threshold models, we consider more realistic settings, where (i) states are dynamic, i.e., nodes oscillate between influenced and uninfluenced states, and (ii) continuous amounts of resources (e.g., incentives or effort) can be expended on the nodes. We propose a mathematical model using voting dynamics to characterise optimal strategies in a prototypical star topology against known and unknown adversarial strategies. In cases where the adversarial strategy is unknown, we characterise the Nash Equilibrium. To generalise the work further, we introduce a fixed cost incurred to gain access to nodes, together with the dynamic cost proportional to the influence exerted on the nodes, constrained by the same budget. We observe that, as the cost changes, the system interpolates between the historic discrete and the current continuous case.