计算机科学 ›› 2021, Vol. 48 ›› Issue (4): 243-248.doi: 10.11896/jsjkx.200400053

• 人工智能 • 上一篇    下一篇

基于最大后验估计的谣言源定位器

鲍志强, 陈卫东   

  1. 华南师范大学计算机学院 广州510631
  • 收稿日期:2020-06-24 修回日期:2020-07-04 出版日期:2021-04-15 发布日期:2021-04-09
  • 通讯作者: 陈卫东 (CHENWD@SCNU.EDU.CN)
  • 基金资助:
    国家自然科学基金(61370003)

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).

摘要: 随着互联网的普及,信息能够通过互联网以极快的速度被传播给大众。但同时,一些虚假信息比如谣言也借助网络的级联效应泛滥成灾,因此如何在传播网络中快速准确地确定谣言传播源成为一个亟待解决的问题。文章针对社交网络提出了一种谣言源定位的方法,与现有的基于最大后验(Maximum-a-posteriori,MAP)概率估计的方法不同,该方法首先考虑全局和局部感染点、非感染点的影响,使用效果更优的MAP先验概率估计(Prior Probability Estimation,PPE)计算方式。然后基于最小生成树贪心算法来稀疏化社交网络,让MAP中的似然估计(Likelihood Estimation,LE)计算更符合真实的传播结构。最后,采用新的MAP值来估计传播网络中节点为传播源的可能性,从而更准确地定位谣言源点。将所提方法与现有的几种方法分别在模型网络和真实网络中进行了对比,实验结果表明,所提方法优于现有的谣言源定位方法。

关键词: 社交网络, 稀疏化网络, 谣言源, 源定位, 最大后验概率估计

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

中图分类号: 

  • 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] 王剑, 彭雨琦, 赵宇斐, 杨健.
基于深度学习的社交网络舆情信息抽取方法综述
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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!