# Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization

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

## Key facts

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

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

- [DeepSN: A Sheaf Neural Framework for Influence Maximization](https://mlsanity.com/paper/2412.12416/) (2024)
- [Who Are the Best Adopters? User Selection Model for Free Trial Item Promotion](https://mlsanity.com/paper/2202.09508/) (2022)
- [Stochastic Multi-round Submodular Optimization with Budget](https://mlsanity.com/paper/2404.13737/) (2024)

## Abstract (arXiv)

We consider the *adaptive influence maximization problem*: given a network and a budget k, iteratively select k seeds in the network to maximize the expected number of adopters. In the *full-adoption feedback model*, after selecting each seed, the seed-picker observes all the resulting adoptions. In the *myopic feedback model*, the seed-picker only observes whether each neighbor of the chosen seed adopts. Motivated by the extreme success of greedy-based algorithms/heuristics for influence maximization, we propose the concept of *greedy adaptivity gap*, which compares the performance of the adaptive greedy algorithm to its non-adaptive counterpart. Our first result shows that, for submodular influence maximization, the adaptive greedy algorithm can perform up to a (1-1/e)-fraction worse than the non-adaptive greedy algorithm, and that this ratio is tight. More specifically, on one side we provide examples where the performance of the adaptive greedy algorithm is only a (1-1/e) fraction of the performance of the non-adaptive greedy algorithm in four settings: for both feedback models and both the *independent cascade model* and the *linear threshold model*. On the other side, we prove that in any submodular cascade, the adaptive greedy algorithm always outputs a (1-1/e)-approximation to the expected number of adoptions in the optimal non-adaptive seed choice. Our second result shows that, for the general submodular diffusion model with full-adoption feedback, the adaptive greedy algorithm can outperform the non-adaptive greedy algorithm by an unbounded factor. Finally, we propose a risk-free variant of the adaptive greedy algorithm that always performs no worse than the non-adaptive greedy algorithm.