# Online Influence Maximization with Local Observations

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2018.

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

- [Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization](https://mlsanity.com/paper/2206.14846/) (2022)
- [Online Influence Maximization: Concept and Algorithm](https://mlsanity.com/paper/2312.00099/) (2023)
- [Budgeted Online Influence Maximization](https://mlsanity.com/paper/2604.19672/) (2026)

## Abstract (arXiv)

We consider an online influence maximization problem in which a decision maker selects a node among a large number of possibilities and places a piece of information at the node. The node transmits the information to some others that are in the same connected component in a random graph. The goal of the decision maker is to reach as many nodes as possible, with the added complication that feedback is only available about the degree of the selected node. Our main result shows that such local observations can be sufficient for maximizing global influence in two broadly studied families of random graph models: stochastic block models and Chung--Lu models. With this insight, we propose a bandit algorithm that aims at maximizing local (and thus global) influence, and provide its theoretical analysis in both the subcritical and supercritical regimes of both considered models. Notably, our performance guarantees show no explicit dependence on the total number of nodes in the network, making our approach well-suited for large-scale applications.