@article{Chen_Peng_Schoenebeck_Tao_2020, title={Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization}, volume={34}, url={https://ojs.aaai.org/index.php/AAAI/article/view/5398}, DOI={10.1609/aaai.v34i01.5398}, abstractNote={<p>We consider the <em>adaptive influence maximization problem</em>: given a network and a budget <em>k</em>, iteratively select <em>k</em> seeds in the network to maximize the expected number of adopters. In the <em>full-adoption feedback model</em>, after selecting each seed, the seed-picker observes all the resulting adoptions. In the <em>myopic feedback model</em>, 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 <em>greedy adaptivity gap</em>, 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/<em>e</em>)-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/<em>e</em>) fraction of the performance of the non-adaptive greedy algorithm in four settings: for both feedback models and both the <em>independent cascade model</em> and the <em>linear threshold model</em>. On the other side, we prove that in any submodular cascade, the adaptive greedy algorithm always outputs a (1-1/<em>e</em>)-approximation to the expected number of adoptions in the optimal non-adaptive seed choice. Our second result shows that, for the general submodular cascade 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.</p>}, number={01}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Chen, Wei and Peng, Binghui and Schoenebeck, Grant and Tao, Biaoshuai}, year={2020}, month={Apr.}, pages={590-597} }