Influence Diffusion in Online Social Networks With Propagation Rate Changes
Influence Diffusion in Online Social Networks With Propagation Rate Changes
复制标题
DOI：
10.1109/tnse.2020.3015935
复制
发表时间：
2020-10
影响因子：
6.6
通讯作者：
Tianyi Pan;Xiang Li;Alan Kuhnle;M. Thai
中科院分区：
文献类型：
--
作者：
Tianyi Pan;Xiang Li;Alan Kuhnle;M. Thai
信息可以在在线社交网络(OSN)用户中高速传播，这使得在线社交网络成为病毒式营销的重要平台。尽管在过去的十年中，与病毒营销相关的问题在OSN中得到了广泛的研究，但已有的工作都假定传播速度已知。在本文中，我们提出了一种新的模型--动态影响传播(DIP)，该模型允许在话题变得流行后传播率增加，并且能够更真实地描述信息在OSN中的传播。在DIP的基础上，定义了一个新的研究问题：DIP下的门限激活问题(TAP-DIP)。然而，它在已经存在的#P-Hard Tap问题上又增加了一层复杂性。尽管难度很大，但我们能够以$O(\log|V|)$比率来近似TAP-DIP，其中$|V|$是网络中的用户数。我们的解决方案包括全局优化技术和TAP通用版本的新解决方案。我们还考虑了更复杂的情况，即传播速率可能发生多次变化，并且变化是非即时的，并给出了相应的解决方案和分析。我们使用各种真实的OSN数据集测试我们的解决方案，并证明我们的解决方案不仅生成高质量的种子集，而且还具有可扩展性。
Information can propagate among Online Social Network (OSN) users at a high speed, which makes the OSNs important platforms for viral marketing. Although the viral marketing related problems in OSNs have been extensively studied in the past decade, the existing works all assume known propagation rates. In this paper, we propose a novel model, Dynamic Influence Propagation (DIP), which allows propagation rates to increase after a topic becomes popular and can be used for describing information propagation in OSNs more realistically. Based on DIP, we define a new research problem: Threshold Activation Problem under DIP (TAP-DIP). However, it adds another layer of complexity over the already #P-hard TAP problem. Despite it hardness, we are able to approximate TAP-DIP with $O(\log |V|)$ ratio, where $|V|$ is the number of users in the network. Our solution consists of global optimization techniques and a novel solution to the general version of TAP. We also consider the more complicated case when the propagation rates may change multiple times and the changes are non-immediate, with corresponding solution and analyses. We test our solution using various real OSN datasets, and demonstrate that our solution not only generates high-quality seed sets, but also scales.