Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback

Abstract

We study the online influence maximization problem in social networks under the independent cascade model. Specifically, we aim to learn the set of "best influencers" in a social network online while repeatedly interacting with it. We address the challenges of (i) combinatorial action space, since the number of feasible influencer sets grows exponentially with the maximum number of influencers, and (ii) limited feedback, since only the influenced portion of the network is observed. Under a stochastic semi-bandit feedback, we propose and analyze IMLinUCB, a computationally efficient UCB-based algorithm. Our bounds on the cumulative regret are polynomial in all quantities of interest, achieve near-optimal dependence on the number of interactions and reflect the topology of the network and the activation probabilities of its edges, thereby giving insights on the problem complexity. To the best of our knowledge, these are the first such results. Our experiments show that in several representative graph topologies, the regret of IMLinUCB scales as suggested by our upper bounds. IMLinUCB permits linear generalization and thus is both statistically and computationally suitable for large-scale problems. Our experiments also show that IMLinUCB with linear generalization can lead to low regret in real-world online influence maximization.

Compared with the previous version, this version has fixed a mistake. This version is also consistent with the NIPS camera-ready version

References in corpus (7)

• Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Cascading Bandits for Large-Scale Recommendation Problems
• Matroid Bandits: Fast Combinatorial Optimization with Learning
• An Adaptive Algorithm for Finite Stochastic Partial Monitoring
• Model-Independent Online Learning for Influence Maximization
• Information Gathering in Networks via Active Exploration

Cited by in corpus (7)

• GIN-SD: Source Detection in Graphs with Incomplete Nodes via Positional Encoding and Attentive Fusion
• Online Influence Maximization under Linear Threshold Model
• A study of distributionally robust mixed-integer programming with Wasserstein metric: on the value of incomplete data
• Seeding with Costly Network Information
• Stochastic Online Learning with Probabilistic Graph Feedback
• Evolving Influence Maximization in Evolving Networks
• Automatic Ensemble Learning for Online Influence Maximization