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

arXiv: https://arxiv.org/abs/1907.01707 · HTML: https://mlsanity.com/paper/1907.01707/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jul 2019.

## Built on by (most cited first, 1 of 1)

- [Stochastic Multi-round Submodular Optimization with Budget](https://mlsanity.com/paper/2404.13737/) (2024)

## Abstract (arXiv)

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 [fracee-1, frac2ee - 1] and for the out-arborescence, the gap is between [fracee-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.