# Online Influence Maximization (Extended Version)

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2015.

## Built on by (most cited first, 17 of 17)

- [Deep Graph Representation Learning and Optimization for Influence Maximization](https://mlsanity.com/paper/2305.02200/) (2023)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Combinatorial Stochastic-Greedy Bandit](https://mlsanity.com/paper/2312.08057/) (2023)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [A Community-Aware Framework for Social Influence Maximization](https://mlsanity.com/paper/2207.08937/) (2022)
- [Federated Learning with Fair Worker Selection: A Multi-Round Submodular Maximization Approach](https://mlsanity.com/paper/2107.11728/) (2021)
- [GAC: A Deep Reinforcement Learning Model Toward User Incentivization in Unknown Social Networks](https://mlsanity.com/paper/2203.09578/) (2022)
- [Online Influence Maximization under Decreasing Cascade Model](https://mlsanity.com/paper/2305.15428/) (2023)
- [Revealing graph bandits for maximizing local influence](https://mlsanity.com/paper/2605.00489/) (2026)
- [Online Learning of Independent Cascade Models with Node-level Feedback](https://mlsanity.com/paper/2109.02519/) (2021)
- [Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback](https://mlsanity.com/paper/2109.06077/) (2021)
- [Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization](https://mlsanity.com/paper/2206.14846/) (2022)
- [Targeted Advertising on Social Networks Using Online Variational Tensor Regression](https://mlsanity.com/paper/2208.10627/) (2022)
- [A Community-Aware Framework for Influence Maximization with Explicit Accounting for Inter-Community Influence](https://mlsanity.com/paper/2512.23973/) (2025)
- [Contextual Bandits for Advertising Campaigns: A Diffusion-Model Independent Approach (Extended Version)](https://mlsanity.com/paper/2201.05231/) (2022)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)
- [Rethinking Learning-Based Influence Maximization: Simple Neural Surrogates and Native Discrete Search](https://mlsanity.com/paper/2608.08406/) (2026)

## Abstract (arXiv)

Social networks are commonly used for marketing purposes. For example, free samples of a product can be given to a few influential social network users (or "seed nodes"), with the hope that they will convince their friends to buy it. One way to formalize marketers' objective is through influence maximization (or IM), whose goal is to find the best seed nodes to activate under a fixed budget, so that the number of people who get influenced in the end is maximized. Recent solutions to IM rely on the influence probability that a user influences another one. However, this probability information may be unavailable or incomplete. In this paper, we study IM in the absence of complete information on influence probability. We call this problem Online Influence Maximization (OIM) since we learn influence probabilities at the same time we run influence campaigns. To solve OIM, we propose a multiple-trial approach, where (1) some seed nodes are selected based on existing influence information; (2) an influence campaign is started with these seed nodes; and (3) users' feedback is used to update influence information. We adopt the Explore-Exploit strategy, which can select seed nodes using either the current influence probability estimation (exploit), or the confidence bound on the estimation (explore). Any existing IM algorithm can be used in this framework. We also develop an incremental algorithm that can significantly reduce the overhead of handling users' feedback information. Our experiments show that our solution is more effective than traditional IM methods on the partial information.