计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 243-248.doi: 10.11896/jsjkx.200400053
鲍志强, 陈卫东
BAO Zhi-qiang, CHEN Wei-dong
摘要: 随着互联网的普及,信息能够通过互联网以极快的速度被传播给大众。但同时,一些虚假信息比如谣言也借助网络的级联效应泛滥成灾,因此如何在传播网络中快速准确地确定谣言传播源成为一个亟待解决的问题。文章针对社交网络提出了一种谣言源定位的方法,与现有的基于最大后验(Maximum-a-posteriori,MAP)概率估计的方法不同,该方法首先考虑全局和局部感染点、非感染点的影响,使用效果更优的MAP先验概率估计(Prior Probability Estimation,PPE)计算方式。然后基于最小生成树贪心算法来稀疏化社交网络,让MAP中的似然估计(Likelihood Estimation,LE)计算更符合真实的传播结构。最后,采用新的MAP值来估计传播网络中节点为传播源的可能性,从而更准确地定位谣言源点。将所提方法与现有的几种方法分别在模型网络和真实网络中进行了对比,实验结果表明,所提方法优于现有的谣言源定位方法。
中图分类号:
[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] | 王剑, 彭雨琦, 赵宇斐, 杨健. 基于深度学习的社交网络舆情信息抽取方法综述 Survey of Social Network Public Opinion Information Extraction Based on Deep Learning 计算机科学, 2022, 49(8): 279-293. https://doi.org/10.11896/jsjkx.220300099 |
[2] | 魏鹏, 马玉亮, 袁野, 吴安彪. 用户行为驱动的时序影响力最大化问题研究 Study on Temporal Influence Maximization Driven by User Behavior 计算机科学, 2022, 49(6): 119-126. https://doi.org/10.11896/jsjkx.210700145 |
[3] | 余皑欣, 冯秀芳, 孙静宇. 结合物品相似性的社交信任推荐算法 Social Trust Recommendation Algorithm Combining Item Similarity 计算机科学, 2022, 49(5): 144-151. https://doi.org/10.11896/jsjkx.210300217 |
[4] | 畅雅雯, 杨波, 高玥琳, 黄靖云. 基于SEIR的微信公众号信息传播建模与分析 Modeling and Analysis of WeChat Official Account Information Dissemination Based on SEIR 计算机科学, 2022, 49(4): 56-66. https://doi.org/10.11896/jsjkx.210900169 |
[5] | 左园林, 龚月姣, 陈伟能. 成本受限条件下的社交网络影响最大化方法 Budget-aware Influence Maximization in Social Networks 计算机科学, 2022, 49(4): 100-109. https://doi.org/10.11896/jsjkx.210300228 |
[6] | 郭磊, 马廷淮. 基于好友亲密度的用户匹配 Friend Closeness Based User Matching 计算机科学, 2022, 49(3): 113-120. https://doi.org/10.11896/jsjkx.210200137 |
[7] | 邵玉, 陈崚, 刘维. 独立级联模型下基于最大似然的负影响力源定位方法 Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model 计算机科学, 2022, 49(2): 204-215. https://doi.org/10.11896/jsjkx.201100190 |
[8] | 王剑, 王玉翠, 黄梦杰. 社交网络中的虚假信息:定义、检测及控制 False Information in Social Networks:Definition,Detection and Control 计算机科学, 2021, 48(8): 263-277. https://doi.org/10.11896/jsjkx.210300053 |
[9] | 谭琪, 张凤荔, 王婷, 王瑞锦, 周世杰. 融入结构度中心性的社交网络用户影响力评估算法 Social Network User Influence Evaluation Algorithm Integrating Structure Centrality 计算机科学, 2021, 48(7): 124-129. https://doi.org/10.11896/jsjkx.200600096 |
[10] | 张人之, 朱焱. 基于主动学习的社交网络恶意用户检测方法 Malicious User Detection Method for Social Network Based on Active Learning 计算机科学, 2021, 48(6): 332-337. https://doi.org/10.11896/jsjkx.200700151 |
[11] | 张少杰, 鹿旭东, 郭伟, 王世鹏, 何伟. 供需匹配中的非诚信行为预防 Prevention of Dishonest Behavior in Supply-Demand Matching 计算机科学, 2021, 48(4): 303-308. https://doi.org/10.11896/jsjkx.200900090 |
[12] | 袁得嵛, 陈世聪, 高见, 王小娟. 基于斯塔克尔伯格博弈的在线社交网络扭曲信息干预算法 Intervention Algorithm for Distorted Information in Online Social Networks Based on Stackelberg Game 计算机科学, 2021, 48(3): 313-319. https://doi.org/10.11896/jsjkx.200400079 |
[13] | 谭琪, 张凤荔, 张志扬, 陈学勤. 社交网络用户影响力的建模方法 Modeling Methods of Social Network User Influence 计算机科学, 2021, 48(2): 76-86. https://doi.org/10.11896/jsjkx.191200102 |
[14] | 郁友琴, 李弼程. 基于多粒度文本特征表示的微博用户兴趣识别 Microblog User Interest Recognition Based on Multi-granularity Text Feature Representation 计算机科学, 2021, 48(12): 219-225. https://doi.org/10.11896/jsjkx.201100128 |
[15] | 马理博, 秦小麟. 话题-位置-类别感知的兴趣点推荐 Topic-Location-Category Aware Point-of-interest Recommendation 计算机科学, 2020, 47(9): 81-87. https://doi.org/10.11896/jsjkx.191100120 |
|