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

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

作　　者：邵玉 陈崚[1] 刘维[1] SHAO Yu;CHEN Ling;LIU Wei(College of Information Engineering,Yangzhou University,Yangzhou,Jiangsu 225000,China)

机构地区：[1]扬州大学信息工程学院,江苏扬州225000

出　　处：《计算机科学》2022年第2期204-215,共12页Computer Science

基　　金：国家自然科学基金(61379066,61702441,61070047,61379064,61472344,61402395,61602202);江苏省自然科学基金(BK20130452,BK2012672,BK2012128,BK20140492,BK20160428);江苏省教育厅自然科学基金(12KJB520019,13KJB520026,09KJB20013);江苏省研究生培养创新工程项目(CXZZ130173)。

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

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

分 类 号：O157.5[理学—数学] G206[理学—基础数学]