Research On The Traceability Algorithm Of Virus Spread On Complex Network

There are various detrimental propagation processes in complex networks such as rumors,contagion and cascading failures,etc.More efficient immunization strategies can be taken if people are able to locate sources promptly.Recently,more and more researchers raise concern about the source identification in complex networks and they have made some progress.However,there are still many theoretical issues need to be resolved.We make a research on identifying sources by means of network science,probability statistics and evolutionary computation etc.,the results are as follows:(1)We propose an algorithm for identifying sources of random walk-based epidemic spreading in networks.Considering different source in the set of infection sources transmit the virus to terminal nodes with different prior probabilities,we use two methods to approximate the prior probability,the single-step transition probability matrix and the first passage time,to get the estimator of multiple infection sources.We demonstrate the efficiency of the estimator on complex network models and real networks,respectively,and simulation results show that when the network is sparse or heterogeneous,multiple sources can be identified accurately or only a few error steps from the real sources set.Furthermore,the first passage time based approach is better than the single-step transition probability matrix based approach.(2)We propose a multivariate Gaussian distribution based algorithm for identifying the infection source on a multi-layer network.Firstly,for a tree-type multi-layer network,we put forward a multivariate Gaussian distribution based method to locate the source.Then,the shortest path tree is utilized to simulate the diffusion spanning tree and extends the algorithm to general multi-layer networks.Finally,we make some research on the impact of network topology and the distribution of virus propagation delay on the accuracy of our estimator.It turns out that our method performs well on multiple occasions.(3)We study the impact of observer placement strategies on the efficiency of the multivariate Gaussian distribution based algorithm for identifying infection sources.We adopt two strategies to filter observers: one is to use a centrality based method to select observers and the other is to optimize the coverage by using particle swarm optimization to select the set of observers that make the coverage larger.The result reveals that,compared to other centrality based placement strategies,K-shell based strategy can improve the efficient of the algorithm in various situations.However,the placement strategies based on optimizing coverage performs well in uniform networks.