Adaptive Influence Maximization under General Feedback Models
arXiv:1902.00192
Abstract
Influence maximization is a prototypical problem enabling applications in various domains, and it has been extensively studied in the past decade. The classic influence maximization problem explores the strategies for deploying seed users before the start of the diffusion process such that the total influence can be maximized. In its adaptive version, seed nodes are allowed to be launched in an adaptive manner after observing certain diffusion results. In this paper, we provide a systematic study on the adaptive influence maximization problem, focusing on the algorithmic analysis of the scenarios when it is not adaptive submodular. We introduce the concept of regret ratio which characterizes the key trade-off in designing adaptive seeding strategies, based on which we present the approximation analysis for the well-known greedy policy. In addition, we provide analysis concerning improving the efficiencies and bounding the regret ratio. Finally, we propose several future research directions.
References in corpus (6)
- Benchmark graphs for testing community detection algorithms
- Adaptive Influence Maximization in Dynamic Social Networks
- Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks
- Model-Independent Online Learning for Influence Maximization
- Adaptive Influence Maximization in Social Networks: Why Commit when You can Adapt?
- Beyond Uniform Reverse Sampling: A Hybrid Sampling Technique for Misinformation Prevention