Computer Science ›› 2021, Vol. 48 ›› Issue (4): 243-248.doi: 10.11896/jsjkx.200400053

• Artificial Intelligence • Previous Articles     Next Articles

Rumor Source Detection in Social Networks via Maximum-a-Posteriori Estimation

BAO Zhi-qiang, CHEN Wei-dong   

  1. School of Computer Science,South China Normal University,Guangzhou 510631,China
  • Received:2020-06-24 Revised:2020-07-04 Online:2021-04-15 Published:2021-04-09
  • About author:BAO Zhi-qiang,born in 1995,postgra-duate.His main research interests include graph theory,computation complexity,and algorithm.(530420396@qq.com)
    CHEN Wei-dong,born in 1968,Ph.D,professor,Ph.D supervisor.His main research interests include graphtheory,computation complexity,algorithm and machine learning.
  • Supported by:
    National Natural Science Foundation of China(61370003).

Abstract: With the popularization of Internet,information can be transmitted to the public at an extremely rapid rate through Internet.But at the same time,some abnormal information,such as rumors,has been flooded with the cascade effect of Internet.How to quickly and accurately identify the source of a rumor spreading under a complex network becomes an urgent problem to be solved.This paper proposes a source localization algorithm in social networks.Different from some existing methods based on Maximum-a-posteriori(MAP) probability estimation,this method first considers the influence of global and local infected nodes and non-infected nodes,and proposes a better MAP prior probability estimation(PPE) calculation mode.Then,asocial network is sparsified through a greedy algorithm based on minimum spanning trees,which makes the likelihood estimation(LE) calculation in MAP more consistent with the real propagation structure.Finally,a new MAP value is used to estimate the possibility of a node as the source of propagation in the social network as to locate the source of the rumor more accurately.The proposed me-thod is compared with some existing methods by an experiment on some model networks and real networks,and experimental results show that the proposed method is superior to these existing methods of locating the rumor source.

Key words: Maximum-a-posteriori estimation, Rumor source, Social network, Source location, Sparse network

CLC Number: 

  • TP301
[1]SHELKE S,ATTAR V.Source detection of rumor in social network-A review[J].Online Social Networks and Media,2019,9:30-42.
[2]SHAH D,ZAMAN T.Detecting sources of computer viruses in networks:theory and experiment[C]//Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems.2010:203-214.
[3]DONG W,ZHANG W,TAN C W.Rooting out the rumor culprit from suspects[C]//2013 IEEE International Symposium on Information Theory.IEEE,2013:2671-2675.
[4]FUCHS M,YU P D.Rumor source detection for rumor spreading on random increasing trees[J].Electronic Communications in Probability,2015,20:1-12.
[5]WANG Z,DONG W,ZHANG W,et al.Rumor source detection with multiple observations:Fundamental limits and algorithms[J].ACM SIGMETRICS Performance Evaluation Review,2014,42(1):1-13.
[6]CHANG B,ZHU F,CHEN E,et al.Information source detection via maximum a posteriori estimation[C]//2015 IEEE International Conference on Data Mining.IEEE,2015:21-30.
[7]CHANG B,CHEN E,ZHU F,et al.Maximum a posteriori> estimation for information source detection[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2018:2242-2256.
[8]KAI Z,LEI Y.Information Source Detection in the SIR Model:A Sample Path Based Approach[J].IEEE/ACM Transactions on Networking,2012,24(1):408-421.
[9]JI F,TANG W,TAY W P.Properties and applications of Gromov matrices in network inference[C]//2018 IEEE Statistical Signal Processing Workshop(SSP).IEEE,2018:478-482.
[10]ALI S S,ANWAR T,RASTOGI A,et al.EPA:Exoneration and Prominence based Age for Infection Source Identification[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management.2019:891-900.
[11]KOU L,MARKOWSKY G,BERMAN L.A fast algorithm for Steiner trees[J].ACTA Informatica,1981,15(2):141-145.
[12]SRIDHAR A,POOR H V.Sequential Estimation of Network Cascades[J].arXiv:1912.03800,2019.
[13]ZHU L,WANG B.Stability analysis of a SAIR rumor spreading model with control strategies in online social networks[J].Information Sciences,2020,536:1-19.
[14]HETHCOTE H W.The mathematics of infectious diseases[J].SIAM Review,2000,42(4):599-653.
[15]SHELKE S,ATTAR V.Source detection of rumor in social network-a review[J].Online Social Networks and Media,2019,9:30-42.
[16]LOKHOV A Y,MÉZARD M,OHTA H,et al.Inferring the origin of an epidemic with a dynamic message-passing algorithm[J].Physical Review E,2014,90(1):012801.
[17]FIORITI V,CHINNICI M.Predicting the sources of an out-break with a spectral technique[J].arXiv:1211.2333,2012.
[18]BAILEYN T J.The mathematical theory of infectious diseases and its applications[M].Charles Griffin & Company Ltd,5a Crendon Street,High Wycombe,Bucks HP13 6LE,1975.
[19]OLIVEIRA C A S,PARDALOS P M.A survey of combinatorial optimization problems in multicast routing[J].Computers & Operations Research,2005,32(8):1953-1981.
[20]COMIN C H,LUCIANO D F C.Identifying the starting point of a spreading process in complex networks[J].Physical Review E,2011,84(5):056105.
[21]https://networkx.github.io/documentation/stable/news.html#networkx-2-4.
[22]https://snap.stanford.edu/data/.
[1] WANG Jian, PENG Yu-qi, ZHAO Yu-fei, YANG Jian. Survey of Social Network Public Opinion Information Extraction Based on Deep Learning [J]. Computer Science, 2022, 49(8): 279-293.
[2] WEI Peng, MA Yu-liang, YUAN Ye, WU An-biao. Study on Temporal Influence Maximization Driven by User Behavior [J]. Computer Science, 2022, 49(6): 119-126.
[3] YU Ai-xin, FENG Xiu-fang, SUN Jing-yu. Social Trust Recommendation Algorithm Combining Item Similarity [J]. Computer Science, 2022, 49(5): 144-151.
[4] CHANG Ya-wen, YANG Bo, GAO Yue-lin, HUANG Jing-yun. Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR [J]. Computer Science, 2022, 49(4): 56-66.
[5] ZUO Yuan-lin, GONG Yue-jiao, CHEN Wei-neng. Budget-aware Influence Maximization in Social Networks [J]. Computer Science, 2022, 49(4): 100-109.
[6] GUO Lei, MA Ting-huai. Friend Closeness Based User Matching [J]. Computer Science, 2022, 49(3): 113-120.
[7] SHAO Yu, CHEN Ling, LIU Wei. Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model [J]. Computer Science, 2022, 49(2): 204-215.
[8] WANG Jian, WANG Yu-cui, HUANG Meng-jie. False Information in Social Networks:Definition,Detection and Control [J]. Computer Science, 2021, 48(8): 263-277.
[9] TAN Qi, ZHANG Feng-li, WANG Ting, WANG Rui-jin, ZHOU Shi-jie. Social Network User Influence Evaluation Algorithm Integrating Structure Centrality [J]. Computer Science, 2021, 48(7): 124-129.
[10] WU Cheng-feng, CAI Li, LI Jin, LIANG Yu. Frequent Pattern Mining of Residents’ Travel Based on Multi-source Location Data [J]. Computer Science, 2021, 48(7): 155-163.
[11] ZHANG Ren-zhi, ZHU Yan. Malicious User Detection Method for Social Network Based on Active Learning [J]. Computer Science, 2021, 48(6): 332-337.
[12] ZHANG Shao-jie, LU Xu-dong, GUO Wei, WANG Shi-peng, HE Wei. Prevention of Dishonest Behavior in Supply-Demand Matching [J]. Computer Science, 2021, 48(4): 303-308.
[13] ZHANG Hao-chen, CAI Ying, XIA Hong-ke. Delivery Probability Based Routing Algorithm for Vehicular Social Network [J]. Computer Science, 2021, 48(3): 289-294.
[14] YUAN De-yu, CHEN Shi-cong, GAO Jian, WANG Xiao-juan. Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game [J]. Computer Science, 2021, 48(3): 313-319.
[15] TAN Qi, ZHANG Feng-li, ZHANG Zhi-yang, CHEN Xue-qin. Modeling Methods of Social Network User Influence [J]. Computer Science, 2021, 48(2): 76-86.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!