# Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 13 Sep 2021.

## Builds on (most cited first, 14 of 14)

- [Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms](https://mlsanity.com/paper/1407.8339/) (2014)
- [Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications](https://mlsanity.com/paper/1703.01610/) (2017)
- [Provably Optimal Algorithms for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/1703.00048/) (2017)
- [Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency](https://mlsanity.com/paper/1404.0900/) (2014)
- [Online Influence Maximization (Extended Version)](https://mlsanity.com/paper/1506.01188/) (2015)
- [Online Influence Maximization under Linear Threshold Model](https://mlsanity.com/paper/2011.06378/) (2020)
- [Estimating Diffusion Network Structures: Recovery Conditions, Sample Complexity & Soft-thresholding Algorithm](https://mlsanity.com/paper/1405.2936/) (2014)
- [Influence Maximization with Bandits](https://mlsanity.com/paper/1503.00024/) (2015)
- [Inferring Graphs from Cascades: A Sparse Recovery Framework](https://mlsanity.com/paper/1505.05663/) (2015)
- [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)
- [Trace Complexity of Network Inference](https://mlsanity.com/paper/1308.2954/) (2013)
- [Scalable Influence Estimation in Continuous-Time Diffusion Networks](https://mlsanity.com/paper/1311.3669/) (2013)
- [Learning Influence Functions from Incomplete Observations](https://mlsanity.com/paper/1611.02305/) (2016)

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

- [DSCom: A Data-Driven Self-Adaptive Community-Based Framework for Influence Maximization in Social Networks](https://mlsanity.com/paper/2311.11080/) (2023)

## Abstract (arXiv)

We study the online influence maximization (OIM) problem in social networks, where the learner repeatedly chooses seed nodes to generate cascades, observes the cascade feedback, and gradually learns the best seeds that generate the largest cascade in multiple rounds. In the demand of the real world, we work with node-level feedback instead of the common edge-level feedback in the literature. The edge-level feedback reveals all edges that pass through information in a cascade, whereas the node-level feedback only reveals the activated nodes with timestamps. The node-level feedback is arguably more realistic since in practice it is relatively easy to observe who is influenced but very difficult to observe from which relationship (edge) the influence comes. Previously, there is a nearly optimal tildeO(√T)-regret algorithm for OIM problem under the linear threshold (LT) diffusion model with node-level feedback. It remains unknown whether the same algorithm exists for the independent cascade (IC) diffusion model. In this paper, we resolve this open problem by presenting an tildeO(√T)-regret algorithm for OIM problem under the IC model with node-level feedback.