计算机科学 ›› 2022, Vol. 49 ›› Issue (2): 204-215.doi: 10.11896/jsjkx.201100190

• 数据库&大数据&数据科学 • 上一篇    下一篇

独立级联模型下基于最大似然的负影响力源定位方法

邵玉, 陈崚, 刘维   

  1. 扬州大学信息工程学院 江苏 扬州225000
  • 收稿日期:2020-11-26 修回日期:2021-03-24 出版日期:2022-02-15 发布日期:2022-02-23
  • 通讯作者: 陈崚(lchen@yzu.edu.cn)
  • 作者简介:shaoyuco2@163.com
  • 基金资助:
    国家自然科学基金(61379066,61702441,61070047,61379064,61472344,61402395,61602202);江苏省自然科学基金(BK20130452,BK2012672,BK2012128,BK20140492,BK20160428);江苏省教育厅自然科学基金(12KJB520019,13KJB520026,09KJB20013);江苏省研究生培养创新工程项目(CXZZ13_0173)

Maximum Likelihood-based Method for Locating Source of Negative Influence Spreading Under Independent Cascade Model

SHAO Yu, CHEN Ling, LIU Wei   

  1. College of Information Engineering,Yangzhou University,Yangzhou,Jiangsu 225000,China
  • Received:2020-11-26 Revised:2021-03-24 Online:2022-02-15 Published:2022-02-23
  • About author:SHAO Yu,born in 1996,postgraduate,is a member of China Computer Federation.Her main research interests include data mining and complex network.
    CHEN Ling,born in 1951,professor,Ph.D supervisor,is a member of China Computer Federation,IEEE CS society and ACM,a senior member of the Chinese Computer Society.His main research interests include data mining complex network and artificial intelligence.
  • Supported by:
    National Natural Science Foundation of China(61379066,61702441,61070047,61379064,61472344,61402395,61602202),Natural Science Foundation of Jiangsu Province(BK20130452,BK2012672,BK2012128,BK20140492,BK20160428),Natural Science Foundation of Jiangsu Provincial Department of Education(12KJB520019,13KJB520026,09KJB20013) and Jiangsu Province Postgraduate Trai-ning Innovation Project(CXZZ13_0173).

摘要: 如今,网络谣言、传染病、计算机病毒等负面影响力的传播,给社会稳定、人类健康和信息安全造成了巨大的隐患,识别它们的传播源,对于控制负面影响力造成的危害有着重要的意义。目前大多数方法都只致力于单个传播源的定位问题,而在实际网络中,负影响力往往来自多个传播源,而且需要进行传播过程的模拟;此外,由于忽略了顶点之间拓扑限制的差异,导致定位传播源的准确率不高而且需要大量的计算时间。针对这些问题,提出了一种基于极大似然的方法,利用少量观测点提供的信息来有效定位多个传播源。首先,提出了传播图的概念以及产生传播图的方法,根据节点的入度和边的权重将其划分成若干层级,并去除传播概率较小的边,形成包含观测节点的传播图;然后,利用似然法计算传播图中的每一层顶点的激活概率,选取相对于观测点的似然最大的k个顶点构成源节点集合;最后,对所提方法进行了模拟实验,实验结果表明,该方法能够准确识别网络中的多个传播源,源定位结果的精确度高于其他类似算法;同时,也通过实验验证了观测点的选择和网络结构在不同程度上会影响传播源的定位结果。

关键词: 传播源定位, 独立级联模型, 社会网络, 影响力传播, 最大似然

Abstract: Nowadays,the spread of negative influences such as internet rumors,infectious diseases and computer viruses has caused huge hidden dangers to social stability,human health and information security.It is of great significance to identify the source of their propagation to control the harm caused by the negative influence.However,most of the existing methods only focus on locating a single propagation source,while in the real world network,negative influence often comes from multiple sources.And the methods require time consuming simulation of the propagation process.In addition,due to ignoring the difference of topology features between the nodes,the accuracy of propagation source locating is not high and large amount of computation time is required.In order to solve these problems,a maximum likelihood based method is proposed to locate multiple sources using the information provided by a small number of observation points.Firstly,the concept of propagation graph is defined,and a method for constructing propagation graph is proposed.In the propagation graph,nodes in the network are divided into several levels according to their degrees and the weight of the edges.The edges with low propagation probability are removed,and the propagation graph is formed by combining observation nodes.Then,the activation probability of each node in each layer of the propagation graph is calculated,and the k nodes with the maximum likelihood relative to the observation points are selected to form the source node set.The simulation results show that the proposed method can accurately identify multiple propagation sources in the network,and the results of source location is higher than other similar algorithms.At the same time,it is verified that the selection of observation points and the network structure also affect the positioning results of propagation sources to varying degrees.

Key words: Independent cascade model, Influence propagation, Likelihood maximization, Location of propagation source, Social networks

中图分类号: 

  • O157.5
[1]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.
[2]WANG H J,ZHANG F F,SUN K J.An algorithm for locating propagation source in complex networks[J].Physics Letters A,2021,393:127184.
[3]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):2508.
[4]PINTO P C,THIRAN P,VETTERLI M.Locating the source of diffusion in large-scale networks[J].Phys. Rev. Lett.,2012,109(6):68702.
[5]ZANG W,ZHANG P,ZHOU C,et al.Discovering Multiple Diffusion Source Nodes in Social Networks[J].Procedia Computerscience,2014,29:443-452.
[6]HU Z,SHEN Z,CAO S,et al.Locating multiple diffusionsources in time varying networks from sparse observations[J].Scientific Reports,2018,8(1):2685.
[7]JIANG J,WEN S,YU S,et al.Rumor Source Identification in Social Networks with Time-Varying Topology[J].IEEE Tran-sactions on Dependable and Secure Computing,2018,15(1):166-179.
[8]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.
[9]DONG M,ZHENG B,HUNG N Q V,et al.Multiple rumor source detection with graphconvolutional networks[C]//Proceedings of the 28th ACM International Conference on Information and Knowledge Management.2019:569-578.
[10]WANG H.An universal algorithm for source location in complex networks[J].Physica A:Statistical Mechanics and its Applications,2019,514:620-630.
[11]YANG X,ZHU Z,YU H,et al.A Naming Game-Based Method for the Location of Information Source in Social Networks[J].Complexity,2020,2020:1-8.
[12]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.
[13]DING Y,CUI X,WANG H,et al.PRIA:a Multi-source Recognition Method Based on Partial Observation in SIR Model[J].Mobile Networks and Applications,2020,25(1):271-280.
[14]ZHANG Z,YUE K,SUN Z,et al.Locating Sources in OnlineSocial Networks via Random Walk[C]//2017 IEEE Internatio-nal Congress on Big Data (Big Data Congress).IEEE,2017:337-343.
[15]LI X,LIU Y,ZHAO C,et al.Locating Multiple Sources of Contagion in Complex Networks under the SIR Model[J].Applied Sciences,2019,9(20):4472.
[16]LI X,WANG X,ZHAO C,et al.Optimal Identification of Multiple Diffusion Sources in Complex Networks with Partial Observations[C]//The International Conference on Natural Computation,Fuzzy Systems and Knowledge Discovery.2019:214-223.
[17]ALI S S,ANWAR T,RIZVI S A M.A Revisit to the Infection Source Identification Problem under Classical Graph Centrality Measures[J].Online Social Networks and Media,2020,17(1):100061.
[18]SHAH D,ZAMAN T.Rumors in a Network:Who's the Culprit?[J].IEEE Transactions on Information Theory,2011,57(8):5163-5181.
[19]SEJEONG K,MEEYOUNG C,KYOMIN J.Rumor Detectionover Varying Time Windows[J].PloS one,2017,12(1):e0168344.
[20]FANG M,SHI P,SHANG W,et al.Locating the Source ofAsynchronous Diffusion Process in Online Social Networks[J].IEEE Access,2018,6:17699-17710.
[21]LI X,WANG X,ZHAO C,et al.Locating the Epidemic Source in Complex Networks with Sparse Observers[J].Applied Sciences,2019,9(18):3644.
[22]LI X,WANG X,ZHAO C,et al.Locating the Source of Diffusion in Complex Networks via Gaussian-Based Localization and Deduction[J].Applied Sciences,2019,9(18):3758.
[23]LEE C,SUNG C,MA H,et al.IDR:Positive Influence Maximization and Negative Influence Minimization Under Competitive Linear Threshold Model[C]//2019 20th IEEE International Conference on Mobile Data Management (MDM).IEEE,2019:501-506.
[24]LI Y,FAN J,WANG Y,et al.Influence Maximization on Social Graphs:A Survey[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(10):1852-1872.
[25]TANG Y,SHI Y,XIAO X.Influence Maximization in Near-Li-near Time:A Martingale Approach[C]//Proceedings of the 2015 ACM SIGMOD Internatio-nal Conference on Management of Data.2015:1539-1554.
[26]ZHOU J,FAN J,WANG J,et al.Cost-Efficient Influence Maximization in Online Social Networks[C]//2017 Fifth Internatio-
nal Conference on Advanced Cloud and Big Data (CBD).IEEE,2017:232-237.
[27]WANG F,SHE J,OHYAMA Y,et al.Maximizing positive influence in competitive social networks:A trust-based solution[J].Information Sciences,2021,546:559-572.
[28]LI L,LIU Y,ZHOU Q,et al.Targeted influence maximizationunder a multifactor-based information propagation model[J].Information Sciences,2020,519:124-140.
[29]TRIVEDI N,SINGH A.Efficient Influence Maximization in Social-Networks Under Independent Cascade Model[J].Procedia Computer Science,2020,173:315-324.
[30]LV J,YANG B,YANG Z,et al.A community-based algorithm for influence blocking maximization in social networks[J].Cluster Computing,2019,22(3):5587-5602.
[31]DING J,SUN W,WU J,et al.Influence maximization based on the realistic independent cascade model[J].Knowledge-Based System,2020,191:105265.
[32]FU L,SHEN Z,WANG W X,et al.Multi-source localization on complex networks with limited observers[J].EPL (Europhysics Letters),2016,113(1):18006.
[33]WOO J,CHOI J.Estimating the Information Source under Deca-ying Diffusion Rates[J].Electronics,2019,8(12):1384.
[34]KONG F,LI Q Z,LI S.Survey on Online Influence Maximization[J].Computer Science,2020,47(5):7-13.
[35]MA Y Y,HAN H,QU Q Q.Importance Evaluation Algorithm Based on Node Intimate Degree[J].Computer Science,2021,48(5):140-146.
[36]DEVARAPALLI R K,BISWAS A.Rumor Detection and Tra-cing its Source to Prevent Cyber-Crimes on Social Media[C]//Intelligent Data Analytics for Terror Threat Prediction:Architectures,Methodologies,Techniques and Applications.2021:1-30.
[37]LI W M,LI Z,LUVEMBE A M,et al.Influence maximization algorithm based on Gaussian propagation model[J].Information Sciences,2021,568:386-402.
[1] 杨卓璇, 马源培, 严冠.
基于耦合强度的多项式时间社团探测算法
Polynomial Time Community Detection Algorithm Based on Coupling Strength
计算机科学, 2020, 47(6A): 102-107. https://doi.org/10.11896/JsJkx.190900170
[2] 孔芳, 李奇之, 李帅.
在线影响力最大化研究综述
Survey on Online Influence Maximization
计算机科学, 2020, 47(5): 7-13. https://doi.org/10.11896/jsjkx.200200071
[3] 富坤, 仇倩, 赵晓梦, 高金辉.
基于节点演化分阶段优化的事件检测方法
Event Detection Method Based on Node Evolution Staged Optimization
计算机科学, 2020, 47(5): 96-102. https://doi.org/10.11896/jsjkx.190400072
[4] 李豪,崔新凯,高向川.
大规模MIMO室外无线光通信系统中基于分段高斯近似的最大似然盲检测算法
Maximum Likelihood Blind Detection Algorithm Based on Piecewise Gaussian Approximation for Massive MIMO Outdoor Wireless Optical Communication Systems
计算机科学, 2020, 47(3): 255-260. https://doi.org/10.11896/jsjkx.190200310
[5] 韩忠明, 郑晨烨, 段大高, 董健.
基于多信息融合表示学习的关联用户挖掘算法
Associated Users Mining Algorithm Based on Multi-information Fusion Representation Learning
计算机科学, 2019, 46(4): 77-82. https://doi.org/10.11896/j.issn.1002-137X.2019.04.012
[6] 徐方, 邓敏, 熊曾刚, 叶从欢, 徐宁.
移动社会网络中基于多维上下文匹配的数据转发算法
Data Forwarding Algorithm Based on Multidimensional Context Matching in Mobile Social Networks
计算机科学, 2019, 46(2): 81-87. https://doi.org/10.11896/j.issn.1002-137X.2019.02.013
[7] 金婷, 谭文安, 孙勇, 赵尧.
模糊多目标进化的社会团队形成方法
Social Team Formation Method Based on Fuzzy Multi-objective Evolution
计算机科学, 2019, 46(2): 315-320. https://doi.org/10.11896/j.issn.1002-137X.2019.02.048
[8] 胡庆成, 张勇, 邢春晓.
基于有重叠社区划分的社会网络影响最大化方法研究
K-clique Heuristic Algorithm for Influence Maximization in Social Network
计算机科学, 2018, 45(6): 32-35. https://doi.org/10.11896/j.issn.1002-137X.2018.06.005
[9] 张昱, 高克宁, 于戈.
一种融合节点属性信息的社会网络链接预测方法
Method of Link Prediction in Social Networks Using Node Attribute Information
计算机科学, 2018, 45(6): 41-45. https://doi.org/10.11896/j.issn.1002-137X.2018.06.007
[10] 张林姿, 贾传亮.
基于拓扑路径的网络演化传播机制研究
Study of Propagation Mechanism in Networks Based on Topological Path
计算机科学, 2018, 45(11A): 308-314.
[11] 珠杰,洪军建.
基于SDAs的人物关系抽取方法研究
Research on Method of Personal Relation Extraction under SDAs
计算机科学, 2017, 44(Z6): 141-145. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.033
[12] 刘林峰,严禹道,吴国新.
一种基于节点移动倾向检测的社会网络机会转发机制
Opportunistic Forwarding Mechanism Based on Node Movement Tendencies Detecting
计算机科学, 2017, 44(7): 74-78. https://doi.org/10.11896/j.issn.1002-137X.2017.07.013
[13] 王珍,韩忠明,李晋.
大规模数据下的社交网络结构洞节点发现算法研究
Research on Social Network Structural Holes Discovery Algorithm under Large-scale Data
计算机科学, 2017, 44(4): 188-192. https://doi.org/10.11896/j.issn.1002-137X.2017.04.041
[14] 张晓琳,张臣,张文超,张换香,于芳名.
D-VSSP:分布式社会网络隐私保护算法
D-VSSP:Distributed Social Network Privacy Preserving Algorithm
计算机科学, 2017, 44(2): 93-97. https://doi.org/10.11896/j.issn.1002-137X.2017.02.012
[15] 吕文渊,周丽华,廖仁建.
一种面向主题耦合的影响力最大化算法
Coupled Topic-oriented Influence Maximization Algorithm
计算机科学, 2017, 44(12): 28-32. https://doi.org/10.11896/j.issn.1002-137X.2017.12.005
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!