Efficient Influence Maximization Under Network Uncertainty

Abstract We consider the influence maximization (IM) problem in a partially visible social network. The goal is to design a decision-making framework for an autonomous agent to select a limited set of influential seed nodes to spread a message as widely as possible across the network. We consider the realistic case where only a partial section of the network is visible to the agent, while the rest is one of a finite set of known structures, each with a given realization probability. We show that solving the IM problem in this setting is NP-hard, and we provide analytical guarantees for the performance of a novel computationally-efficient seed-selection approximation algorithm for the agent. In empirical experiments on real-world social networks, we demonstrate the efficiency of our scheme and show that it outperforms state-of-the-art approaches that do not model the uncertainty.
  • Soheil Eshghi (Yale)
  • Setareh Maghsudi (Yale)
  • Valerio Restocchi (Southampton)
  • Sebastian Stein (Southampton)
  • Leandros Tassiulas (Yale)
Date Apr-2019
Venue First International INFOCOM Workshop on Communications and Networking Aspects of Online Social Networks