Research On Vital Nodes Identification And Propagation Source Location In Complex Networks

The majority of the spreading phenomena in the real world can be abstracted as the dynamic propagation processes on complex networks.The research in this area can help us better understand the propagation phenomenon,and further better control the spreading process on networks.The spreading controlling on networks is one of the strategic tasks in the "National Cyberspace Security Strategy",and the effective solutions are one of the urgent problems.Vital nodes identification and propagation source location are the important ways to control the spreading process on networks.The main research directions in vital nodes identification includes node importance ranking and influence maximization.Improving both of the accuracy and the efficiency are the urgent problems in vital nodes identification.The methods of propagation source location are mainly divided into single source location method and multi-source location method.Improving the accuracy,the efficiency and the ability to deal with the sparse observation phenomenon are the urgent problems in propagation source location.The research works in this paper involve vital nodes identification and propagation source location.The current research status are reviewed,and further,we mainly focus on studying the node importance ranking method in vital nodes identification and the single source location method in propagation source location.For node importance ranking,an Extended Local K-Shell Sum(ELKSS)centrality is presented,for the first time,in this paper.Firstly,with K-Shell method decomposing a network,we define a Local K-Shell Sum(LKSS)by calculating the sum of the K-Shell(KS)indices of the neighbors within 2-hops of a given node.Secondly,we extend the LKSS,and propose the ELKSS centrality,its computational complexity is O(m+n(k)~2).On 8 real networks with different sizes,the ELKSS is compared with other 6 classical methods on 3 different performance evaluation metrics,including resolution,accuracy and relevance.For resolution,we define a new metric which not only clearly reflect the ability of node ranking methods to distinguish the influence of nodes,but also the inner even degree of a ranking result.The experimental results show that the ELKSS centrality is superior to the other 6 classical ranking methods in all the three evaluation metrics.For propagation source location,with the Susceptible-Infected(SI)model as propagation mechanism,and from the view of observation rationality of network snapshot,for the first time,we study the single-source location method by utilizing the hierarchical relationship and the observation characteristics formed by the nodes with different states.So far,there is no such work that studies the propagation source location from the view of observation rationality of network snapshot.First,on the tree with a fixed root,we define a Rationality Observation Value(ROV)by utilizing the hierarchical relationship and the observation characteristics formed by the nodes with different states.The ROV is to quantify the observation rationality of the tree.Second,for general tree graph,with each infected node as root,we build spanning tree and calculate its corresponding ROV.Then,we select the tree with the maximal ROV from all spanning trees,and the root corresponding to this tree is the propagation source.Last,for arbitrary network,by assuming that the spreading on network is diffused in the breadth first way,and with each infected node as root,we build breadth first spanning tree.Then,we calculate the ROV of all spanning trees and select the one with the maximal ROV,the root corresponding to this tree is the propagation source.Further,we propose a novel Propagation Centrality(PC)algorithm to locate the propagation source.The computational complexity of PC is O(n3).We prove that PC is a precise locator on infinite line graph.On a series of synthetic networks and real networks,PC is compared with other 5 classical propagation source location methods.The experimental results show that the accuracy of PC is superior to the other 5 classical methods.More importantly,the PC algorithm is insensitive to the sparse observation phenomenon in network snapshots,which makes PC more suitable for real circumstances.