Research On Ranking Algorithm Of Vital Nodes Based On Local Information Of Network

Complex systems exist widely in nature,which could be abstracted as complex networks for analysis.Nodes that have great influence on network structure and function in complex networks are called vital nodes.Ranking the vital nodes in complex networks is not only helpful to better understand the mechanism of complex networks,but also has a wide range of practical application value.The information that characterizes the networks can be divided into global information and local information.The ranking algorithms based on global information need to know the whole topology structure of networks in advance,which have high time complexity,so not suitable for analysis of large networks.The algorithms based on local information with low complexity but have low ranking precision usually.This paper focuses on the vital nodes ranking algorithm which only makes use of the local information of the network and has high ranking accuracy.The main research contents are as follows:(1)This paper introduces the theoretical basis of vital nodes ranking algorithms,including the basic concepts of complex networks,classical algorithms and the indexes used to evaluate the importance of nodes.(2)The algorithm of ranking vital nodes based on Improved Structural Hole is proposed.By introducing the contribution weight of node to quantify the contribution of neighbor nodes,and then combining the theory of structural holes to obtain a new metric coefficient,the algorithm can estimate the importance of nodes.Experimental results on real data sets show that this algorithm has a high ranking accuracy for vital nodes and can be used to rank vital nodes effectively.(3)The algorithm of ranking vital nodes based on Truncated Random Walk is proposed.By abstracting the information flow in networks as label,and then counting the numbers of label each node received through Truncated Random walk process,the algorithm could estimate the importance of nodes.Simulation results illustrate the proposed algorithm is superior to multiple benchmark algorithms and has a high ranking accuracy.In this paper,two vital node ranking algorithms are proposed,which only make use of local information of the network and have high ranking accuracy.Our research will be helpful to complement the system of vital node ranking algorithm,and the research results can be applied to the practical fields,which have high practical application value.