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

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.

Keywords

• social networks|influence propagation|likelihood maximization|independent cascade model|location of propagation source