mlsanityData to 14 Oct 2026

Online Influence Maximization: Concept and Algorithm

arXiv 2312.00099 ↗First posted 30 Nov 2023cs.SI cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

In this survey, we offer an extensive overview of the Online Influence Maximization (IM) problem by covering both theoretical aspects and practical applications. For the integrity of the article and because the online algorithm takes an offline oracle as a subroutine, we first make a clear definition of the Offline IM problem and summarize those commonly used Offline IM algorithms, which include traditional approximation or heuristic algorithms and ML-based algorithms. Then, we give a standard definition of the Online IM problem and a basic Combinatorial Multi-Armed Bandit (CMAB) framework, CMAB-T. Here, we summarize three types of feedback in the CMAB model and discuss in detail how to study the Online IM problem based on the CMAB-T model. This paves the way for solving the Online IM problem by using online learning methods. Furthermore, we have covered almost all Online IM algorithms up to now, focusing on characteristics and theoretical guarantees of online algorithms for different feedback types. Here, we elaborately explain their working principle and how to obtain regret bounds. Besides, we also collect plenty of innovative ideas about problem definition and algorithm designs and pioneering works for variants of the Online IM problem and their corresponding algorithms. Finally, we encapsulate current challenges and outline prospective research directions from four distinct perspectives.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 32 of its 84 references that are in the map. First posted on arXiv 30 Nov 2023.

Builds on

32 of 84 references.

References · 32

  1. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,548
  2. 2015Pointer Networkscited by 895
  3. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 608
  4. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  5. 2017A Tutorial on Thompson Samplingcited by 433
  6. 2018Deep Learning on Graphs: A Surveycited by 393
  7. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 333
  8. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
  9. 2018Learning Scheduling Algorithms for Data Processing Clusterscited by 134
  10. 2014Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Armscited by 79
  11. 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
  12. 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
20 more
  1. 2019Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use casecited by 53
  2. 2017Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applicationscited by 45
  3. 2023Deep Graph Representation Learning and Optimization for Influence Maximizationcited by 27
  4. 2023Contextual Combinatorial Bandits with Probabilistically Triggered Armscited by 18
  5. 2020Online Influence Maximization under Linear Threshold Modelcited by 17
  6. 2016Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networkscited by 15
  7. 2022Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Armscited by 15
  8. 2022A Survey on Influence Maximization: From an ML-Based Combinatorial Optimizationcited by 15
  9. 2019Factorization Bandits for Online Influence Maximizationcited by 10
  10. 2021Network Inference and Influence Maximization from Samplescited by 9
  11. 2019Thompson Sampling for Combinatorial Network Optimization in Unknown Environmentscited by 7
  12. 2016Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Modelscited by 5
  13. 2016Online Influence Maximization in Non-Stationary Social Networkscited by 3
  14. 2018Online Influence Maximization with Local Observationscited by 3
  15. 2019A Multi-Feature Diffusion Model: Rumor Blocking in Social Networkscited by 3
  16. 2022A Survey on Location-Driven Influence Maximizationcited by 3
  17. 2023Online Influence Maximization under Decreasing Cascade Modelcited by 2
  18. 2021Online Learning of Independent Cascade Models with Node-level Feedbackcited by 1
  19. 2023Adversarial Bandits with Multi-User Delayed Feedback: Theory and Applicationcited by 1
  20. 2023DSCom: A Data-Driven Self-Adaptive Community-Based Framework for Influence Maximization in Social Networkscited by 1

Built on by

Not cited yet.