Research On Important Nodes Identification Of Complex Network Based On Random Walk

Key node identification is an important research content of network science.It has important research significance in the fields of medicine,sociology,network security,power transportation,politics and economics.The theory and method based on the study of propagation dynamics can better understand the relationship and difference between the propagation behaviors on different networks.The study of key point identification is of great significance in different fields,such as finding the most influential people in the social network to control the spread of rumors,finding susceptible populations during disease transmission,effective prevention and control of diseases,finding key hubs in urban traffic systems and power systems for key maintenance,and reducing the risk of economic losses.Effectively evaluating and measuring the importance of nodes in a network usually uses the concepts and terminology of graph theory to abstract specific practical problems into graphs,get the topological properties of the network,and integrate multidisciplinary as the research direction,which has broad theoretical research and practical application value.In this paper,aiming at the destruction of network structure by removing nodes,we consider the combination of one-step random walk and removing nodes,removing nodes without removing edges,combining the average shortest path distance between network nodes and the information of neighbor nodes,calculating the change of network efficiency to measure the importance of nodes,and comprehensively considering local information and global information to identify key nodes.Based on the SIR propagation model and Kendall tau distance as the similarity evaluation index,the key nodes in the network are identified.The experiment shows that the method can effectively identify the key nodes.In this paper,the problem of random walk tendency is not considered in the key point identification method of equal probability stack random walk,and it is not suitable for the key point identification in the directed network.Using the similarity index of Jaccard nodes to construct the transition probability matrix,the research on the key point identification of unequal probability stack random walk in the undirected network is carried out.The method considers the random walk in the actual network The tendentiousness,more effective simulation of information dissemination in the network.By using the same data set of undirected network and comparative experiment method,it is proved that the key points in undirected network can be identified with high accuracy based on the unequal probability stack random walk method,which is superior to the equal probability stack random walk method.In addition,the importance index of nodes in directed network is redefined using extended Jaccard index combined with overlay random walk,and compared with classical PageRank algorithm and its improved algorithm.The algorithm solves the problem of identifying key nodes in directed networks.Four sets of comparative experiments are designed with three real datasets to demonstrate the validity and accuracy of the unequal probability overlay random walk method proposed in this paper for identifying key nodes in directed networks.