Research On Finding Vital Nodes On Complex Networks

The problem of identifying vital nodes in networks has important effects on social and economy lives and has been widely investigated during recent years.The importance of nodes is also called centrality of nodes and is a significant issue in network analysis area.This is not only because of its important theoretical research significance,but also because of its extensive practical value.It has many applications,for example,to control the outbreak of epidemics,to conduct advertisements for e-commercial products,to predict popular scientific publications,to control the spread of rumors and so on.There have been various algorithms for this problem,measurements from simply counting the number of neighbor nodes to complicated algorithm.Currently,the most commonly used and most classic algorithms for identifying vital nodes in networks are degree centrality,betweenness centrality,closeness centrality,and PageRank algorithm.Above which,PageRank algorithm has been widely used in practice and has been suc-cessfully used to rank websites in Google search engines.During the process of either PageRank algorithm or other random-walk-based centrality methods,a.random walker always selects next arriving node from its neighborhood randomly.But in real world,this selection is more likely to have "tendentiousness".For example,information spreads much more frequently between two closer friends.Thus,in this paper,we propose two novel vertex centrality methods which take this kind of "tendentiousness" into consideration,i.c.,DPRank centrality and ECP-Rank centrality.The main idea of DPRank centrality is that the random walker no longer selects the next node from the neighbor nodes randomly,but prefers to move to a neighbor node with greater degree(or out-degree for directed network,respectively)with foresight,so that the information can be spread rapidly.In other words,the tendency that the random walker moves from current node vi to its neighbor vj is proportional to degree(or out-degree)of the neighbor node vj.One can see that,DPRank centrality method takes not only the immediate neighbor around it but also second-order neighbor(i.e.,its neighbor's neighbors)into consideration.The main idea of ECP-Rank centrality is that,the random walker no longer selects the next node from the neighbor nodes randomly,but rather tends to reach the next neighbor node through "significant" edge.The significance of edges can be measured by "edge centrality indices" as follows:Jaccard index,Bridgeness index,Degree product index,Estrada index.Transition tendency of random walker from current node vi to its neighbor vj is proportional to significance of the edge eij.Both of the above methods are to re-evaluate the importance of vertices in complex networks by redefining new transition probability matrix.The eigen vector corresponding to the largest eigenvalue 1 of transpose matrix of transition probability matrix corresponds to the centrality score of each node in the network.DPRank centrality,ECP-Rank cen-trality and several classical vertex centrality methods are applied to real networks.By calculating the Kendall coefficients between the standard rankings obtained from the SIR spread model and results obtained from various centrality methods,the advantages of the two new methods of DPRank centrality and ECP-Rank centrality are verified.The innovation of this article:in the process of random walks,the transition tendency of random walker is taken into account.As far as we know,this is vertex centrality approach that combines node centrality with edge centrality firstly.From the aspect of experimental results,the results of DPR.ank algorithm and ECP-Rank algorithm are more accurate than results of other algorithms.