Research On Multiple Diffusion Sources Identification In Complex Networks

It has long been a significant but difficult problem to identify propagation sources based on limited knowledge of network structures and the varying states of network nodes.In the past few years,researchers have proposed a series of methods to identify diffusion sources in networks.These methods mainly focus on the identification of a single diffusion source in tree networks,however the topologies of real world networks are far more complex than trees.Moreover,due to the spatiotemporal complexity and the uncertainty of the propagation process,there often exit multiple diffusion sources in the actual propagation.However,only a few of existing methods are proposed for identifying multiple diffusion sources.In order to solve the above problems,the paper studies the problem of multiple source identification on general networks,the main work of the full text is as follows:1.A multi-source identification algorithm based on SI model is proposed.Firstly,from the perspective of spreading time,the problem of multi-source identification under the SI model is transformed into finding k nodes in the network that can minimize the sum of all partition spreading times and the objective function of the problem is abstracted.Then the KST algorithm is proposed to minimize the objective function in an iterative manner to achieve the identification of multiple sources.Experimental results show that KST algorithm can get relatively higher identification accuracy.At the same time,we also propose the effective spreading time to estimate the propagation time between any two nodes in the network and the effective spreading time can further optimize the identification accuracy of the KST algorithm.Finally,a heuristic algorithm that can estimate the number of diffusion sources is proposed to solve the problem that the number of diffusion sources is difficult to know in advance.2.Based on the KST algorithm,the multi-source identification algorithm under the SIR propagation model is proposed which is called WP-KST algorithm.Firstly,aiming at the problem that the recovery nodes cannot correctly distinguish from the susceptible nodes under the SIR model,a weight propagation algorithm is proposed to realize the detection of recovery nodes.The simulation experiment proves that the weight propagation algorithm can detect the recovery nodes in the network well and fill in the missing information.Then we use the KST algorithm to identify the multi-source on the extended infection network which is consist of infected nodes,recovery nodes and the edges between these nodes.The experimental results show that the WP-KST algorithm can solve the multi-source identification problem under SIR model well and have higher detection accuracy.3.The source identification problem under the sensor observation is studied.Assuming that the propagation follows the SI model,a single-source detection algorithm based sensor observation is first proposed which is called RDPC algorithm.The RDPC algorithm first uses the back-propagation algorithm to screen out possible source nodes in the network.Then for each possible source node,we detect the linear correlation between its spreading times to all infected sensors and the relative infection times recorded by the infected sensors.The node with the largest linear correlation is regarded as the diffusion source.The experiments verify that the RDPC algorithm has a higher detection accuracy.In addition,through a simple partitioning idea,the RDPC algorithm is extended to multi-source identification problems under the sensor observation.Experimental results show that the extended RDPC algorithm can solve the multi-source identification problem under the sensor observation well.