On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full-Adoption Feedback

In this paper, we study the adaptivity gap of the influence maximization problem under the independent cascade model when full-adoption feedback is available. Our main results are to derive upper bounds on several families of well-studied influence graphs, including in-arborescences, out-arborescences and bipartite graphs. Especially, we prove that the adaptivity gap for the inarborescences is between [ e/(e−1) , 2e/(e−1) ], and for the out-arborescences the gap is between [ e/(e−1) , 2]. These are the first constant upper bounds in the full-adoption feedback model. Our analysis provides several novel ideas to tackle the correlated feedback appearing in adaptive stochastic optimization,
which may be of independent interest.