Document Open Access Logo

Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies

Authors Gianlorenzo D'Angelo, Debashmita Poddar, Cosimo Vinci

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.59.pdf
  • Filesize: 0.69 MB
  • 19 pages

Document Identifiers

Author Details

Gianlorenzo D'Angelo
  • Gran Sasso Science Institute, L'Aquila, Italy
Debashmita Poddar
  • Gran Sasso Science Institute, L'Aquila, Italy
Cosimo Vinci
  • Gran Sasso Science Institute, L'Aquila, Italy

Funding

This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Markets".

Cite As Get BibTex

Gianlorenzo D'Angelo, Debashmita Poddar, and Cosimo Vinci. Improved Approximation Factor for Adaptive Influence Maximization via Simple Greedy Strategies. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ICALP.2021.59

Abstract

In the adaptive influence maximization problem, we are given a social network and a budget k, and we iteratively select k nodes, called seeds, in order to maximize the expected number of nodes that are reached by an influence cascade that they generate according to a stochastic model for influence diffusion. The decision on the next seed to select is based on the observed cascade of previously selected seeds. We focus on the myopic feedback model, in which we can only observe which neighbors of previously selected seeds have been influenced and on the independent cascade model, where each edge is associated with an independent probability of diffusing influence. While adaptive policies are strictly stronger than non-adaptive ones, in which all the seeds are selected beforehand, the latter are much easier to design and implement and they provide good approximation factors if the adaptivity gap, the ratio between the adaptive and the non-adaptive optima, is small. Previous works showed that the adaptivity gap is at most 4, and that simple adaptive or non-adaptive greedy algorithms guarantee an approximation of 1/4 (1-1/e) ≈ 0.158 for the adaptive optimum. This is the best approximation factor known so far for the adaptive influence maximization problem with myopic feedback.
In this paper, we directly analyze the approximation factor of the non-adaptive greedy algorithm, without passing through the adaptivity gap, and show an improved bound of 1/2 (1-1/e) ≈ 0.316. Therefore, the adaptivity gap is at most 2e/e-1 ≈ 3.164. To prove these bounds, we introduce a new approach to relate the greedy non-adaptive algorithm to the adaptive optimum. The new approach does not rely on multi-linear extensions or random walks on optimal decision trees, which are commonly used techniques in the field. We believe that it is of independent interest and may be used to analyze other adaptive optimization problems. Finally, we also analyze the adaptive greedy algorithm, and show that guarantees an improved approximation factor of 1-1/(√{e)}≈ 0.393.

Subject Classification

ACM Subject Classification
  • Theory of computation → Stochastic approximation
  • Theory of computation → Online algorithms
  • Theory of computation → Probabilistic computation
  • Theory of computation → Graph algorithms analysis
Keywords
  • Adaptive Optimization
  • Influence Maximization
  • Submodular Optimization
  • Stochastic Optimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Marek Adamczyk, Maxim Sviridenko, and Justin Ward. Submodular stochastic probing on matroids. In 31st International Symposium on Theoretical Aspects of Computer Science, (STACS), pages 29-40, 2014. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.29.
  2. Georgios Amanatidis, Federico Fusco, Philip Lazos, Stefano Leonardi, and Rebecca Reiffenhäuser. Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, (NeurIPS), 2020. Google Scholar
  3. Arash Asadpour and Hamid Nazerzadeh. Maximizing stochastic monotone submodular functions. Management Science, 62(8):2374-2391, 2016. Google Scholar
  4. Arash Asadpour, Hamid Nazerzadeh, and Amin Saberi. Stochastic submodular maximization. In Internet and Network Economics, 4th International Workshop, (WINE), pages 477-489, 2008. Google Scholar
  5. Ashwinkumar Badanidiyuru, Christos Papadimitriou, Aviad Rubinstein, Lior Seeman, and Yaron Singer. Locally adaptive optimization: Adaptive seeding for monotone submodular functions. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), 1:414-429, 2016. Google Scholar
  6. Domagoj Bradac, Sahil Singla, and Goran Zuzic. (near) optimal adaptivity gaps for stochastic multi-value probing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 49:1-49:21, 2019. Google Scholar
  7. Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740-1766, 2011. Google Scholar
  8. Carri W. Chan and Vivek F. Farias. Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems. Math. Oper. Res., 34(2):333-350, 2009. URL: https://doi.org/10.1287/moor.1080.0364.
  9. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput., 43(6):1831-1879, 2014. Google Scholar
  10. Wei Chen, Laks V. S. Lakshmanan, and Carlos Castillo. Information and Influence Propagation in Social Networks. Synthesis Lectures on Data Management. Morgan & Claypool, 2013. Google Scholar
  11. Wei Chen and Binghui Peng. On adaptivity gaps of influence maximization under the independent cascade model with full-adoption feedback. 30th International Symposium on Algorithms and Computation, (ISAAC), pages 24:1-24:19, 2019. Google Scholar
  12. Wei Chen, Binghui Peng, Grant Schoenebeck, and Biaoshuai Tao. Adaptive Greedy versus Non-adaptive Greedy for Influence Maximization. In The Thirty-Fourth AAAI Conference on Artificial Intelligence, (AAAI), 2020. Google Scholar
  13. Wei Chen, Chi Wang, and Yajun Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1029-1038, 2010. Google Scholar
  14. Edith Cohen, Daniel Delling, Thomas Pajor, and Renato F. Werneck. Sketch-based influence maximization and computation: Scaling up with guarantees. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, (CIKM), pages 629-638, 2014. Google Scholar
  15. Gianlorenzo D'Angelo, Debashmita Poddar, and Cosimo Vinci. Improved approximation factor for adaptive influence maximization via simple greedy strategies. CoRR, abs/2007.09065, 2020. URL: http://arxiv.org/abs/2007.09065.
  16. Gianlorenzo D'Angelo, Debashmita Poddar, and Cosimo Vinci. Better bounds on the adaptivity gap of influence maximization under full-adoption feedback. In AAAI Conference on Artificial Intelligence, (AAAI), 2021. To appear. Google Scholar
  17. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Adaptivity and approximation for stochastic packing problems. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 395-404, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070487.
  18. Brian C. Dean, Michel X. Goemans, and Jan Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res., 33(4):945-964, 2008. URL: https://doi.org/10.1287/moor.1080.0330.
  19. Pedro Domingos and Matt Richardson. Mining the network value of customers. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 57-66, 2001. Google Scholar
  20. Alina Ene and Huy L. Nguyen. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 274-282, 2019. Google Scholar
  21. Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, (ICML), pages 1833-1842, 2019. Google Scholar
  22. Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam. Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 255-273, 2019. Google Scholar
  23. Michel X. Goemans and Jan Vondrák. Stochastic covering and adaptivity. In Theoretical Informatics, 7th Latin American Symposium, (LATIN), pages 532-543, 2006. URL: https://doi.org/10.1007/11682462_50.
  24. Sharon Goldberg and Zhenming Liu. The diffusion of networking technologies. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 1577-1594, 2013. Google Scholar
  25. Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research, 42:427-486, 2011. Google Scholar
  26. Alkis Gotovos, Amin Karbasi, and Andreas Krause. Non-monotone adaptive submodular maximization. In Proceedings of the 24th International Conference on Artificial Intelligence (IJCAI), page 1996–2003. AAAI Press, 2015. Google Scholar
  27. Amit Goyal, Wei Lu, and Laks V. S. Lakshmanan. CELF++: optimizing the greedy algorithm for influence maximization in social networks. In Proceedings of the 20th International Conference on World Wide Web, (WWW), pages 47-48, 2011. Google Scholar
  28. Andrew Guillory and Jeff A. Bilmes. Interactive submodular set cover. In Proceedings of the 27th International Conference on Machine Learning, (ICML), pages 415-422, 2010. URL: https://icml.cc/Conferences/2010/papers/436.pdf.
  29. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Algorithms and Adaptivity Gaps for Stochastic Probing. Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, (SODA), 151:1731-1747, 2016. Google Scholar
  30. Anupam Gupta, Viswanath Nagarajan, and Sahil Singla. Adaptivity gaps for stochastic probing: Submodular and XOS functions. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 1688-1702, 2017. Google Scholar
  31. Kai Han, Keke Huang, Xiaokui Xiao, Jing Tang, Aixin Sun, and Xueyan Tang. Efficient algorithms for adaptive influence maximization. Proceedings of the VLDB Endowment, 11(9):1029-1040, 2018. Google Scholar
  32. Lisa Hellerstein, Devorah Kletenik, and Patrick Lin. Discrete stochastic submodular maximization: Adaptive vs. non-adaptive vs. offline. In Algorithms and Complexity - 9th International Conference, (CIAC), pages 235-248, 2015. URL: https://doi.org/10.1007/978-3-319-18173-8_17.
  33. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 137-146. ACM, 2003. Google Scholar
  34. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. Theory of Computing, 11:105-147, 2015. Google Scholar
  35. Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne M. VanBriesen, and Natalie S. Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 420-429, 2007. Google Scholar
  36. Y. Li, J. Fan, Y. Wang, and K. Tan. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 30(10):1852-1872, 2018. Google Scholar
  37. Hung T. Nguyen, My T. Thai, and Thang N. Dinh. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. In Proceedings of the 2016 International Conference on Management of Data, (SIGMOD), pages 695-710, 2016. Google Scholar
  38. Srinivasan Parthasarathy. An analysis of the greedy algorithm for stochastic set cover. CoRR, abs/1803.07639, 2018. URL: http://arxiv.org/abs/1803.07639.
  39. Binghui Peng and Wei Chen. Adaptive influence maximization with myopic feedback. Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing System, (NeurIPS), pages 5575-5584, 2019. Google Scholar
  40. Matthew Richardson and Pedro M. Domingos. Mining knowledge-sharing sites for viral marketing. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 61-70, 2002. Google Scholar
  41. Aviad Rubinstein, Lior Seeman, and Yaron Singer. Approximability of adaptive seeding under knapsack constraints. Proceedings of the 2015 ACM Conference on Economics and Computation, (EC), pages 797-814, 2015. Google Scholar
  42. Guillaume Salha, Nikolaos Tziortziotis, and Michalis Vazirgiannis. Adaptive submodular influence maximization with myopic feedback. Proceedings of the 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 455-462, 2018. Google Scholar
  43. Lior Seeman and Yaron Singer. Adaptive seeding in social networks. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pages 459-468, 2013. Google Scholar
  44. Yaron Singer. Influence maximization through adaptive seeding. ACM SIGecom Exchanges, 15(1):32-59, 2016. Google Scholar
  45. Lichao Sun, Weiran Huang, Philip S. Yu, and Wei Chen. Multi-round influence maximization. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 2249-2258, 2018. Google Scholar
  46. Jing Tang, Laks V.S. Lakshmanan, Keke Huang, Xueyan Tang, Aixin Sun, Xiaokui Xiao, and Andrew Lim. Efficient approximation algorithms for adaptive seed minimization. Proceedings of the ACM SIGMOD International Conference on Management of Data, pages 1096-1113, 2019. Google Scholar
  47. Youze Tang, Yanchen Shi, and Xiaokui Xiao. Influence maximization in near-linear time: A martingale approach. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 1539-1554, 2015. Google Scholar
  48. Youze Tang, Xiaokui Xiao, and Yanchen Shi. Influence Maximization : Near-Optimal Time Complexity Meets Practical Efficiency. SIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, pages 75-86, 2014. Google Scholar
  49. Guangmo Tong and Ruiqi Wang. Adaptive Influence Maximization under General Feedback Models, 2019. URL: http://arxiv.org/abs/1902.00192v3.
  50. Guangmo Tong, Ruiqi Wang, Zheng Dong, and Xiang Li. Time-constrained Adaptive Influence Maximization, 2020. URL: http://arxiv.org/abs/2001.01742v2.
  51. Guangmo Tong, Weili Wu, Shaojie Tang, and Ding Zhu Du. Adaptive Influence Maximization in Dynamic Social Networks. IEEE/ACM Transactions on Networking, 25(1):112-125, 2017. Google Scholar
  52. Sharan Vaswani and Laks V. S. Lakshmanan. Adaptive influence maximization in social networks: Why commit when you can adapt? CoRR, abs/1604.08171, 2016. URL: http://arxiv.org/abs/1604.08171.
  53. Jing Yuan and Shaojie Tang. No time to observe: Adaptive influence maximization with partial feedback. IJCAI International Joint Conference on Artificial Intelligence, pages 3908-3914, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact