Zhai Xuming, Wu Weili, Xu Wen
Department of Computer Science, University of Texas at Dallas, 800 W. Campbell Rd, Richardson, 75080 TX USA.
College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan, 030024 China.
Comput Soc Netw. 2015;2(1):17. doi: 10.1186/s40649-015-0017-4. Epub 2015 Oct 19.
Cascades of information, ideas, rumors, and viruses spread through networks. Sometimes, it is desirable to find the source of a cascade given a snapshot of it. In this paper, source inference problem is tackled under Independent Cascade (IC) model. First, the #P-completeness of source inference problem is proven. Then, a Markov chain Monte Carlo algorithm is proposed to find a solution. It is worth noting that our algorithm is designed to handle large networks. In addition, the algorithm does not rely on prior knowledge of when the cascade started. Finally, experiments on real social network are conducted to evaluate the performance. Under all experimental settings, our algorithm identified the true source with high probability.
信息、思想、谣言和病毒的级联通过网络传播。有时，在给定级联的一个快照的情况下，希望找到其源头。在本文中，在独立级联（IC）模型下解决源头推断问题。首先，证明了源头推断问题的#P完全性。然后，提出了一种马尔可夫链蒙特卡罗算法来寻找解决方案。值得注意的是，我们的算法旨在处理大型网络。此外，该算法不依赖于级联开始时间的先验知识。最后，在真实社交网络上进行实验以评估性能。在所有实验设置下，我们的算法都以高概率识别出真实源头。
