  We consider the canonical problem of influence maximization in social
networks. Since the seminal work of Kempe, Kleinberg, and Tardos, there have
been two largely disjoint efforts on this problem. The first studies the
problem associated with learning the parameters of the generative influence
model. The second focuses on the algorithmic challenge of identifying a set of
influencers, assuming the parameters of the generative model are 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 can
yield a constant factor approximation guarantee using polynomially-many
samples, drawn from any distribution.
  In this paper, we design a simple heuristic that overcomes this negative
result in practice by leveraging the strong community structure of social
networks. Although in general the approximation guarantee of our algorithm is
necessarily unbounded, we show that this algorithm performs well
experimentally. To justify its performance, we prove our algorithm obtains a
constant factor approximation guarantee on graphs generated through the
stochastic block model, traditionally used to model networks with community
structure.
