Time-constrained Adaptive Influence Maximization
arXiv:2001.01742
Abstract
The well-known influence maximization problem aims at maximizing the influence of one information cascade in a social network by selecting appropriate seed users prior to the diffusion process. In its adaptive version, additional seed users can be selected after observing certain diffusion results. On the other hand, social computing tasks are often time-critical, and therefore only the influence resulted in the early period is worthwhile, which can be naturally modeled by enforcing a time constraint. In this paper, we present an analysis of the time-constrained adaptive influence maximization problem. We show that the new problem is combinatorially different from the existing problems, and the current techniques such as submodular maximization and adaptive submodularity are unfortunately inapplicable. On the theory side, we provide the hardness results of computing the optimal policy and a lower bound on the adaptive gap. For practical solutions, from basic to advanced, we design a series of seeding policies for achieving high efficacy and scalability. Finally, we investigate the proposed solutions through extensive simulations based on real-world datasets.
References in corpus (8)
- Adaptive Influence Maximization in Dynamic Social Networks
- Fake News Mitigation via Point Process Based Intervention
- Scalable Methods for Adaptively Seeding a Social Network
- Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio
- Adaptive Influence Maximization with Myopic Feedback
- On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback
- Adaptive Influence Maximization under General Feedback Models
- Adaptive Influence Maximization in Social Networks: Why Commit when You can Adapt?