The Importance of Communities for Learning to Influence - Balkanski, Eric; Immorlica, Nicole; Singer, Yaron (Advances in Neural Information Processing Systems 30 (NIPS 2017), 2017)
We consider the canonical problem of inﬂuence maximization in social networks. Since the seminal work of Kempe, Kleinberg, and Tardos [KKT03] there have been two, largely disjoint efforts on this problem. The ﬁrst studies the problem associated with learning the generative model that produces cascades, and the second focuses on the algorithmic challenge of identifying a set of inﬂuencers, assuming the generative model is known. Recent results on learning and optimization imply that in general, if the generative model is not known but rather learned from training data, no algorithm for inﬂuence maximization can yield a constant factor approximation guarantee using polynomially-many samples, drawn from any distribution. In this paper we describe a simple algorithm for maximizing inﬂuence from training data. The main idea behind the algorithm is to leverage the strong community structure of social networks and identify a set of individuals who are inﬂuentials but whose communities have little overlap. Although in general,the approximation guarantee of such an algorithm is unbounded, we show that this algorithm performs well experimentally. To analyze its performance, we prove this algorithm obtains a constant factor approximation guarantee on graphs generated through the stochastic block model, traditionally used to model networks with community structure.