Maximizing Influence in an Unknown Social Network

Authors

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

Keywords:

Influence maximization, network sampling, stochastic block model

Abstract

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.

Downloads

Published

2018-04-26

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). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11585

Issue

Section

AAAI Technical Track: Multiagent Systems