Competitive influence maximisation on signed networks

Abstract The influence maximisation problem endeavours to determine the optimal allocation of limited resources on a network that maximises influence spread within the network through exploitation of its inherent connectivity. Competitive influence maximisation studies the problem in an adversarial setting where two external controllers compete to maximise the spread of their own influence in the network. In the past, this problem has been largely studied under the assumption of strictly positive influence propagation within the network. However, real- world networks, positive ties often co-exist with negatives ties. Here negative ties indicate a negative relationship between two individuals such that the opinion of one node adversely affects the opinion of the other, giving rise to a polarity in opinions across the connection. Inclusion of negative ties not only significantly increases the challenge of the optimisation problem but more importantly presents an interesting study where conventional degree-based targeting methods are no longer adequate, and a more qualitative assessment of the network structure is required to determine optimal strategies. In this paper, we demonstrate how the optimal strategy varies with change in fraction of negative links in the network under adversarial settings.
  • 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