A New Algorithm for Rumor Source Detection Based on Information Transmission

doi:10.3969/j.issn.1006-2475.2020.03.011

Abstract

Abstract: In recent years, rumor and rumor source detection has attracted wide attention from scholars in many fields. It is of great theoretical and practical significance to accurately and efficiently discover the sources of rumor propagation in social networks. Most traditional detection methods usually only detect the existence of rumors and rarely detect the source of rumors. MPA (Message-passing Algorithm) is a rumor source detection method based on rumor centrality. Based on this method, an IMPA algorithm (Improved Message-passing Algorithm) is proposed to improve the accuracy of relevant algorithm. Experimental results show that the new algorithm is more accurate in detecting rumor sources. In addition, the actual execution time is shorter for the same detection task.

Key words: rumor source, detection, rumor centrality

CLC Number:

TP391

LIU Che, LIU Zu-gen. A New Algorithm for Rumor Source Detection Based on Information Transmission[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2020.03.011.

References

［1］ NEWMAN M E J. The structure and function of complex networks［J］. SIAM Review, 2003,45(2):167-256.
［2］ LAZER D M J, BAUM M A, BENKLER Y, et al. The science of fake news［J］. Science, 2018,359(6380):1094-1096.

［3］ EDUNOV S, DIUK C, FILIZ I, et al.Three and a Half Degrees of Separation ［EB/OL］. ［2019-10-01］. https://www.mendeley.com/catalogue/three-half-degrees-separation/.
［4］ GUESS A, NAGLER J, TUCKER J. Less than you think: Prevalence and predictors of fake news dissemination on Facebook［J］.Science Advances, 2019,5(1):eaau4586.
［5］ METAXAS P T, FINN S, MUSTAFARAJ E. Using TwitterTrails.com to investigate rumor propagation［C］// Proceedings of the 18th ACM Conference on Companion Computer Supported Cooperative Work and Social Computing. 2015:69-72.
［6］ GUPTA A, KUMARAGURU P, CASTILLO C, et al. TweetCred: Real-time credibility assessment of content on Twitter［C］// The 6th International Conference on Social Informatics. 2014:228-243.
［7］ SHAO C C, CIAMPAGLIA G L ,FLAMMINI A, et al. Hoaxy: A platform for tracking online misinformation［C］// Proceedings of the 3rd Workshop on Social News on the Web. 2016.
［8］ Emergent Website. Home［EB/OL］.［2019-10-01］. http://www.emergent.info/.
［9］ Snopes Media Group Inc. Home［EB/OL］.［2019-10-01］. https://www.snopes.com/.
［10］Factcheck.org. Home［EB/OL］.［2019-10-01］. https://www.factcheck.org/.
［11］SHAH D, ZAMAN T R. Rumors in a network: Who’s the culprit?［J］. IEEE Transactions on Information Theory, 2011,57(8):5163-5181.
［12］SHAH D, ZAMAN T. Rumor centrality: A universal source detector［J］. ACM SIGMETRICS Performance Evaluation Review, 2012,40(1):199-210.
［13］〖JP3〗DONG W X, ZHANG W Y, TAN C W. Rooting out the rumor culprit from suspects［C］// Proceedings of IEEE International Symposium on Information Theory. 2013:2671-2675.
［14］YU P D, TAN C W, FU H L. Rumor source detection in finite graphs with boundary effects by message-passing algorithms［C］//IEEE/ACM International Conference on Advancesin Social Networks Analysis and Mining. 2018:175-192.
［15］〖JP3〗LUO W P, TAY W P, LENG M . How to identify an infection source with limited observations［J］. IEEE Journal of Selected Topics in Signal Processing, 2014,8(4):586-597.
［16］WANG Z X, ZHANG W Y, TAN C W. On inferring rumor source for SIS model under multiple observations［C］// IEEE International Conference on Digital Signal Processing. 2015:755-759.
［17］SAITO K, KIMURA M, MOTODA H. Discovering influential nodes for SIS models in social networks［C］// International Conference on Discovery Science. 2009:302-316.
［18］ZHU K, YING L. Information source detection in the SIR model: A sample path based approach［J］. IEEE/ACM Transactions on Networking, 2012,24(1):408-421.
［19］WOO J Y, CHEN H C. Epidemic model for information diffusion in Web forums: Experiments in marketing exchange and political dialog［J］. SpringerPlus, 2016:5(1):Article Number 66.
［20］SONG L P, JIN Z, SUN G Q. Modeling and analyzing of botnet interactions［J］. Physica A: Statistical Mechanics and Its Applications, 2011,390(2):347-358.
［21］ZANG W Y, 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.
［22］PALUCH R, LU X, SUCHECKI K, et al. Fast and accurate detection of spread source in large complex networks［J］. Scientific Reports, 2018,8(1):Article number 2508.
［23］CHOI J Y, MOON S W, WOO J, et al. Rumor source detection under querying with untruthful answers［C］// IEEE Conference on Computer Communications. 2017.

[1]	WANG Qiu-yi, ZHOU Hao, ZHENG Ting-ting. Improved RetinaNet Target Detection Method for Power Equipment [J]. Computer and Modernization, 2024, 0(01): 47-52.
[2]	NING Juan, ZHOU Qing-hua, ZENG Xiao-wei. Application of Improved YOLOv7 Algorithm in Detection of Capping Defects of Vials [J]. Computer and Modernization, 2023, 0(12): 82-86.
[3]	YANG Bo, ZHUANG Yi. Fault Detection Method of Control Cluster Based on AOA-MSVM [J]. Computer and Modernization, 2023, 0(12): 112-116.
[4]	XU Hong-kui, LI Zhen-ye, GUO Wen-tao, ZHAO Jing-zheng, GUO Xu-bin. Real-time Detection of Arbitrary Shape Scene Text Based on Segmentation [J]. Computer and Modernization, 2023, 0(11): 95-100.
[5]	OU Jia-cheng, ZENG An, JIN Liang. CP-YOLOX-based Algorithm for Protein Target Detection in Cryo-electron Micrographs [J]. Computer and Modernization, 2023, 0(11): 113-119.
[6]	YAN Zi-xian, DONG Bao-liang, TANG Si-mi. Improved YOLOv7 Algorithm for Low-resolution Ship Object Detection in Complex Backgrounds#br# [J]. Computer and Modernization, 2023, 0(11): 120-126.
[7]	GU Ming-xuan, FAN Bing-bing. Feature-level Multimodal Fusion for Depression Recognition [J]. Computer and Modernization, 2023, 0(10): 17-22.
[8]	ZHANG Jia-Qi, XU Qi-lei. Apple Defect Detection Algorithm Based on NAM-YOLO Network [J]. Computer and Modernization, 2023, 0(10): 53-58.
[9]	LI Yan-man, WANG Bi-heng, ZHAO Ling-yan. Safety Helmet Detection Based on Lightweight YOLOv5 [J]. Computer and Modernization, 2023, 0(10): 59-64.
[10]	GU Cheng-wei, DING Yong, LI Deng-hua. Personnel Safety Warning System in Industrial Plant Based on Computer Vision [J]. Computer and Modernization, 2023, 0(09): 20-26.
[11]	NONG Hao-cheng, REN De-jun, REN Qiu-lin, LIU Peng-li, HUANG De-cheng. Surface Anomaly Detection Algorithm of Flexible Plastic Packaging Based on Improved ConvNeXt [J]. Computer and Modernization, 2023, 0(08): 12-17.
[12]	LIU Yu-shan, LIU Wei-kang, LIU Qing-hua, ZHE Tian-tian, WANG Jia-cheng. Pedestrian Detection Algorithm for Ship-borne Vehicles Based on YOLOX Combined#br# with DeepSort [J]. Computer and Modernization, 2023, 0(08): 60-67.
[13]	OUYANG Fei, WU Xu, XIANG Dong-sheng. Garbage Classification and Detection Method Based on Improved YOLOX [J]. Computer and Modernization, 2023, 0(08): 68-73.
[14]	HU Rui-jie, CHE Dou. Review of Infrared Small Target Detection [J]. Computer and Modernization, 2023, 0(08): 79-86.
[15]	LI Lan-lan, GAO Jian-long, ZHU Xiao, MU Pei-zheng. Insertion/Deletion Genomic Variations Detection Method Based on Regional Read#br# Segments Classification#br# [J]. Computer and Modernization, 2023, 0(07): 13-19.