Time-Constrained Adaptive Influence Maximization
Time-Constrained Adaptive Influence Maximization
复制标题
时间约束的自适应影响力最大化
DOI：
10.1109/tcss.2020.3032616
复制
发表时间：
2021-02-01
影响因子：
5
通讯作者：
Li, Xiang
中科院分区：
文献类型：
--
作者：
Tong, Guangmo;Wang, Ruiqi;Li, Xiang
著名的影响力最大化问题（IM）的目的是通过选择合适的种子用户之前的扩散过程中的社会网络中的一个信息级联的影响力最大化。在其自适应版本中，可以在观察某些扩散结果之后选择额外的种子用户。另一方面，社会计算任务通常是时间关键的，因此，只有在早期阶段产生的影响是值得的，这可以通过强制执行时间约束自然建模。在这篇文章中，我们提出了一个时间约束的自适应IM问题的分析。在理论方面，我们提供了计算最优策略的困难结果和自适应差距的下限，它衡量了自适应政策优于非自适应政策。对于实际的解决方案，从基本到高级，我们设计了一系列的播种策略，以实现高效率和可扩展性。最后，我们通过基于真实世界数据集的广泛模拟来研究所提出的解决方案。
The well-known influence maximization problem (IM) 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 article, we present an analysis of the time-constrained adaptive IM problem. On the theory side, we provide the hardness results of computing the optimal policy and a lower bound on the adaptive gap, which measures the superiority of adaptive policies over the nonadaptive policies. 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 data sets.