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

Abstract

In this paper, we study the adaptivity gap of the influence maximization problem under 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 in-arborescence is between $[\frac{e}{e-1},\frac{2e}{e-1}]$ and for the out-arborescence, the gap is between $[\frac{e}{e-1},2]$. These are the first constant upper bounds in the full-adoption feedback model. We provide several novel ideas to tackle with correlated feedback appearing in the adaptive stochastic optimization, which we believe to be of independent interests.

References in corpus (3)

• Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency
• Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
• Adaptive Influence Maximization with Myopic Feedback

Cited by in corpus (4)

• Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization
• Efficient Approximation Algorithms for Adaptive Influence Maximization
• Time-constrained Adaptive Influence Maximization
• Dynamic Influence Maximization