# Online Influence Maximization: Concept and Algorithm

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

## 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 (most cited first, 30 of 32)

- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Learning Scheduling Algorithms for Data Processing Clusters](https://mlsanity.com/paper/1810.01963/) (2018)
- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case](https://mlsanity.com/paper/1910.07421/) (2019)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Deep Graph Representation Learning and Optimization for Influence Maximization](https://mlsanity.com/paper/2305.02200/) (2023)
- [Contextual Combinatorial Bandits with Probabilistically Triggered Arms](https://mlsanity.com/paper/2303.17110/) (2023)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks](https://mlsanity.com/paper/1605.07990/) (2016)
- [Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms](https://mlsanity.com/paper/2208.14837/) (2022)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Factorization Bandits for Online Influence Maximization](https://mlsanity.com/paper/1906.03737/) (2019)
- [Network Inference and Influence Maximization from Samples](https://mlsanity.com/paper/2106.03403/) (2021)
- [Thompson Sampling for Combinatorial Network Optimization in Unknown Environments](https://mlsanity.com/paper/1907.04201/) (2019)
- [Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models](https://mlsanity.com/paper/1602.03110/) (2016)
- [Online Influence Maximization in Non-Stationary Social Networks](https://mlsanity.com/paper/1604.07638/) (2016)
- [Online Influence Maximization with Local Observations](https://mlsanity.com/paper/1805.11022/) (2018)
- [A Multi-Feature Diffusion Model: Rumor Blocking in Social Networks](https://mlsanity.com/paper/1912.03481/) (2019)
- [A Survey on Location-Driven Influence Maximization](https://mlsanity.com/paper/2204.08005/) (2022)
- [Online Influence Maximization under Decreasing Cascade Model](https://mlsanity.com/paper/2305.15428/) (2023)
- [Online Learning of Independent Cascade Models with Node-level Feedback](https://mlsanity.com/paper/2109.02519/) (2021)

## 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.