Rumor source identification under incomplete information in dynamic social network

LI Yutao, ZHU Jianming, WANG Guoqing, HUANG Jun

Systems Engineering - Theory & Practice ›› 2023, Vol. 43 ›› Issue (4) : 1132-1144.

PDF(534 KB)
中国科学院数学与系统科学研究院期刊网
PDF(534 KB)
Systems Engineering - Theory & Practice ›› 2023, Vol. 43 ›› Issue (4) : 1132-1144. DOI: 10.12011/SETP2022-0262

Rumor source identification under incomplete information in dynamic social network

  • LI Yutao1, ZHU Jianming2, WANG Guoqing1, HUANG Jun1
Author information +
History +

Abstract

After emergencies, online social networks often become the hardest hit areas for rumors to breed and spread. Tracing the source of rumors and blocking the spread of rumors from the source is an effective means of public opinion control. However, in practice, online social networks are dynamic, and it is difficult to fully obtain the historical information of rumor propagation. Usually, we can only obtain the rumor propagation at the current moment. Therefore, this paper focuses on the rumor traceability under incomplete information in dynamic social networks. In this paper, the objective function is constructed according to the expected symmetric difference between the infected set on the last layer of the network and the new infected node set at the current time. It is proved that the objective function has the property of #P-hard and is neither a submodular function nor a supermodular function. Next, a method based on reachable set sampling is designed to find the rumor source node, the algorithm framework and computational complexity analysis are given. Finally, the simulation results on three real dynamic network data sets verify that the rumor tracing method RSS proposed in this paper is better than the existing methods, and explore the impact of the topology change of dynamic social networks on the accuracy of the rumor tracing method proposed in this paper.

Key words

dynamic social network / incomplete information / rumor source identification / maximum likelihood estimate / sample algorithm

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
LI Yutao , ZHU Jianming , WANG Guoqing , HUANG Jun. Rumor source identification under incomplete information in dynamic social network. Systems Engineering - Theory & Practice, 2023, 43(4): 1132-1144 https://doi.org/10.12011/SETP2022-0262

References

[1] 朱宏淼, 齐佳音, 靳祯, 等. 重大公共卫生事件中公众防控意识传播模型研究 [J]. 系统工程理论与实践, 2021, 41(11): 2865-2875.Zhu H M, Qi J Y, Jin Z, et al. Research on transmission model of consciousness of prevention and control among the public in major public health emergencies[J]. Systems Engineering — Theory & Practice, 2021, 41(11): 2865-2875.
[2] 丁学君, 蒋曼, 田勇, 等. 在线社交网络中考虑抑制代价的谣言澄清策略研究 [J]. 系统工程理论与实践, 2021, 41(5): 1119-1137.Ding X J, Jiang M, Tian Y, et al. Rumor clarifying strategies considering restrain costs in online social networks[J]. Systems Engineering — Theory & Practice, 2021, 41(5): 1119-1137.
[3] 王家坤, 于灏, 王新华, 等. 基于用户相对权重的在线社交网络舆情传播控制模型 [J]. 系统工程理论与实践, 2019, 39(6): 1565-1579.Wang J K, Yu H, Wang X H, et al. Dissemination and control model of public opinion in online social networks based on users' relative weight[J]. Systems Engineering — Theory & Practice, 2019, 39(6): 1565-1579.
[4] Shah D, Zaman T. Detecting sources of computer viruses in networks: Theory and experiment[C]// Sigmetrics 2010: Proceedings of the 2010 ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems, 2010: 203-214.
[5] Shah D, Zaman T. Rumors in a network: Who's the culprit?[J]. IEEE Transactions on Information Theory, 2011, 57(8): 5163-5181.
[6] Shah D, Zaman T. Finding rumor sources on random trees[J]. Operations Research, 2016, 64(3): 736-755.
[7] Suthanthiradevi P, Karthika S. Veracity assessment by single and multi-source identification algorithms during the crisis[J]. Journal of Intelligent & Fuzzy Systems, 2022, 42: 1421-1431.
[8] Kesavareddigari H, Spencer S, Eryilmaz A, et al. Identification and asymptotic localization of rumor sources using the method of types[J]. IEEE Transactions on Network Science and Engineering, 2020, 7(3): 1145-1157.
[9] Wang Z, Dong W, Zhang W, et al. Rooting our rumor sources in online social networks: The value of diversity from multiple observations[J]. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(4): 663-677.
[10] Rácz M Z, Richey J. Rumor source detection with multiple observations under adaptive diffusions[J]. IEEE Transactions on Network Science and Engineering, 2021, 8(1): 2-12.
[11] Cai K, Xie H, Lui J. Information spreading forensics via sequential dependent snapshots[J]. IEEE/ACM Transactions on Networking, 2018, 26(1): 478-492.
[12] 张聿博, 张锡哲, 张斌. 面向社交网络信息源定位的观察点部署方法[J]. 软件学报, 2014, 25(12): 2837-2851.Zhang Y B, Zhang X Z, Zhang B. Observer deployment method for locating the information source in social network[J]. Journal of Software, 2014, 25(12): 2837-2851.
[13] Pinto P C, Thiran P, Vetterli M. Locating the source of diffusion in large-scale networks[J]. Physical Review Letters, 2012, 109(6): 068702.
[14] Gajewski G, Paluch R, Suchecki K, et al. Comparison of observer based methods for source localisation in complex networks[J]. Scientific Reports, 2022, 12(1): 5079.
[15] Yang F, Yang S, Peng Y, et al. Locating the propagation source in complex networks with a direction-induced search based Gaussian estimator[J]. Knowledge-Based Systems, 2020, 195: 105674.
[16] Louni A, Subbalakshmi K P. Who spread that rumor: Finding the source of information in large online social networks with probabilistically varying internode relationship strengths[J]. IEEE Transactions on Computational Social Systems, 2018, 5(2): 335-343.
[17] Shi C, Zhang Q, Chu T. Source estimation in continuous-time diffusion networks via incomplete observation[J]. Physica A: Statistical Mechanics and its Applications, 2022, 592: 126843.
[18] Lecomte V, Ódor G, Thiran P. The power of adaptivity in source identification with time queries on the path[J]. Theoretical Computer Science, 2022, 911: 92-123.
[19] 李文钰, 朱建明, 王国庆. 基于最大可达概率的虚假信息溯源问题研究[J]. 系统工程理论与实践, 2022, 42(7): 1941-1951.Li W Y, Zhu J M, Wang G Q. False information source estimation based on the maximum reachable probability[J]. Systems Engineering — Theory & Practice, 2022, 42(7): 1941-1951.
[20] Zhu K, Ying L. Information source detection in the SIR model: A sample-path-based approach[J]. IEEE-ACM Transactions on Networking, 2016, 24(1): 408-421.
[21] Fan L, Li B, Liu D, et al. Identifying propagation source in temporal networks based on label propagation[C]// Springer Singapore, 2020: 72-88.
[22] Zhou J, Jiang Y, Huang B. Source identification of infectious diseases in networks via label ranking[J]. PLoS One, 2021, 16(1): e0245344.
[23] Zhu P, Cheng L, Gao C, et al. Locating multi-sources in social networks with a low infection rate[J]. IEEE Transactions on Network Science and Engineering, 2022, 9(3): 1853-1865.
[24] Zang W, Zhang P, Zhou C, et al. Locating multiple sources in social networks under the SIR model: A divide-and-conquer approach[J]. Journal of Computational Science, 2015, 10: 278-287.
[25] 张锡哲, 张聿博, 吕天阳, 等. 基于子图抽取的在线社交网络多传播源点定位方法[J]. 中国科学:信息科学, 2016, 46(4): 496-510.Zhang X Z, Zhang Y B, Lü T Y, et al. A multi-diffusion source-localization method for online social networks based on sub-graph extraction[J]. Chinese Science: Information Science, 2016, 46(4): 496-510.
[26] Jiang J, Sheng W, Shui Y, et al. K-Center: An approach on the multi-source identification of information diffusion[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(12): 2616-2626.
[27] Wang Z, Sun C, Rui X, et al. Localization of multiple diffusion sources based on overlapping community detection[J]. Knowledge-Based Systems, 2021, 226: 106613.
[28] Zhang Z, Xu W, Wu W, et al. A novel approach for detecting multiple rumor sources in networks with partial observations[J]. Journal of Combinatorial Optimization, 2017, 33(1): 132-146.
[29] Nguyen H T, Ghosh P, Mayo M L, et al. Multiple infection sources identification with provable guarantees[C]// Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 2016: 1663-1672.
[30] Li L, Zhou J, Jiang Y, et al. Propagation source identification of infectious diseases with graph convolutional networks[J]. Journal of Biomedical Informatics, 2021, 116: 103720.
[31] Dong M, Zheng B, Li G, et al. Wavefront-based multiple rumor sources identification by multi-task learning[J]. IEEE Transactions on Emerging Topics in Computational Intelligence. doi: 10.1109/TETCI.2022.3142627.
[32] Antulov-Fantulin N, Lancic A, Smuc T, et al. Identification of patient zero in static and temporal networks: Robustness and limitations[J]. Physical Review Letters, 2015, 114(24): 248701.
[33] Huang Q, Zhao C, Zhang X, et al. Locating the source of spreading in temporal networks[J]. Physica A: Statistical Mechanics and its Applications, 2017, 468: 434-444.
[34] Jiang J, Wen S, Yu S, et al. Rumor source identification in social networks with time-varying topology[J]. IEEE Transactions on Dependable and Secure Computing, 2018, 15(1): 166-179.
[35] Hu Z L, Shen Z, Cao S, et al. Locating multiple diffusion sources in time varying networks from sparse observations[J]. Scientific Reports, 2018, 8: 2685.
[36] Chai Y, Wang Y, Zhu L. Information sources estimation in time-varying networks[J]. IEEE Transactions on Information Forensics and Security, 2021, 16: 2621-2636.
[37] Dagum P, Karp R, Luby M, et al. An optimal algorithm for monte carlo estimation[J]. SIAM Journal on Computing, 2000, 29(5): 1484-1496.
[38] Panzarasa P, Opsahl T, Carley K M. Patterns and dynamics of users' behavior and interaction: Network analysis of an online community[J]. Journal of the American Society for Information Science and Technology, 2009, 60(5): 911-932.
[39] Kumar S F. Spezzano V S. Subrahmanian, et al. Edge weight prediction in weighted signed networks[C]// IEEE International Conference on Data Mining (ICDM), 2016: 221-230.
[40] Kumar S, Hooi B, Makhija D, et al. REV2: Fraudulent user prediction in rating platforms[C]// 11th ACM International Conference on Web Search and Data Mining (WSDM), 2018: 333-341.

Funding

National Natural Science Foundation of China (72074203)
PDF(534 KB)

718

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉