TY - JOUR
AU - Chen, Wei
AU - Peng, Binghui
AU - Schoenebeck, Grant
AU - Tao, Biaoshuai
PY - 2020/04/03
Y2 - 2021/05/17
TI - Adaptive Greedy versus Non-Adaptive Greedy for Influence Maximization
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 34
IS - 01
SE - AAAI Technical Track: Applications
DO - 10.1609/aaai.v34i01.5398
UR - https://ojs.aaai.org/index.php/AAAI/article/view/5398
SP - 590-597
AB - <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>
ER -