No Time to Observe: Adaptive Influence Maximization with Partial Feedback

No Time to Observe: Adaptive Influence Maximization with Partial Feedback

Jing Yuan, Shaojie Tang

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 3908-3914. https://doi.org/10.24963/ijcai.2017/546

Although influence maximization problem has been extensively studied over the past ten years, majority of existing work adopt one of the following models: full-feedback model or zero-feedback model. In the zero-feedback model, we have to commit the seed users all at once in advance, this strategy is also known as non-adaptive policy. In the full-feedback model, we select one seed at a time and wait until the diffusion completes, before selecting the next seed. Full-feedback model has better performance but potentially huge delay, zero-feedback model has zero delay but poorer performance since it does not utilize the observation that may be made during the seeding process. To fill the gap between these two models, we propose partial-feedback model, which allows us to select a seed at any intermediate stage. We develop a novel alpha-greedy policy that achieves a bounded approximation ratio.
Keywords:
Multidisciplinary Topics and Applications: AI and Social Sciences
Planning and Scheduling: Planning with Incomplete information