Competitive influence maximisation using nonlinear budget constraints

Abstract We study competitive influence maximisation (IM) in social networks using voter dynamics, under nonlinear budget constraints. Our model assumes a continuous distribution of external influence as opposed to the traditional binary allocation. Continuous allocation of influence allows an unconstrained set of nodes to be targeted with varying intensities. In previous work, we observed that under voter dynamics and linear budget constraints, the influence maximisation problem using continuous allocation takes a concave form, where influence spread in the network is positively correlated with the number of targeted nodes in the network. However, realistically the cost of targeting a node may not always be proportional to the influence ex- perienced by them (e.g., there may be “diminishing returns”). Here we present results that demonstrate sensitivity of optimal strategies to nonlinearity in budget constraints. First, we define the optimisation problem for voter dynamics under nonlinear budget constraints and derive analytical closed-form solutions for optimal strategies of IM, in the presence of an adversary in star networks. We then propose a mean-field approximation, which we solve numerically for large core-periphery networks.
  • Sukankana Chakraborty (Southampton)
  • Sebastian Stein (Southampton)
  • Markus Brede (Southampton)
  • Ananthram Swami (ARL)
  • Geeth de Mel (IBM UK)
Date Sep-2020
Venue 4th Annual Fall Meeting of the DAIS ITA, 2020