Maximizing Influence in an Unknown Social Network


  • Bryan Wilder University of Southern California
  • Nicole Immorlica Microsoft Research, New England
  • Eric Rice University of Southern California
  • Milind Tambe University of Southern California



Influence maximization, network sampling, stochastic block model


In many real world applications of influence maximization, practitioners intervene in a population whose social structure is initially unknown. This poses a multiagent systems challenge to act under uncertainty about how the agents are connected. We formalize this problem by introducing exploratory influence maximization, in which an algorithm queries individual network nodes (agents) to learn their links. The goal is to locate a seed set nearly as influential as the global optimum using very few queries. We show that this problem is intractable for general graphs. However, real world networks typically have community structure, where nodes are arranged in densely connected subgroups. We present the ARISEN algorithm, which leverages community structure to find an influential seed set. Experiments on real world networks of homeless youth, village populations in India, and others demonstrate ARISEN's strong empirical performance. To formally demonstrate how ARISEN exploits community structure, we prove an approximation guarantee for ARISEN on graphs drawn from the Stochastic Block Model.




How to Cite

Wilder, B., Immorlica, N., Rice, E., & Tambe, M. (2018). Maximizing Influence in an Unknown Social Network. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1).



AAAI Technical Track: Multiagent Systems