Important Nodes Identification In Complex Networks Based On Scale-free And Small-World

Many complex systems in the real world can be modeled with complex networks,such as social systems,the Internet,and so on.In real complex systems,there are often some special elements that can affect the operation of the system to a greater extent.After modeling this complex system with a complex network,these special elements are important nodes in the network.Important nodes can affect the structure and function of the network to a greater extent than other nodes in the network.Therefore,identifying important nodes has important theoretical and practical significance,such as helping people to control the outbreak of epidemics and conducting advertisements for e-commercial products.However,up to now,there is still no precise and uniform definition of the importance of nodes,so existing research can identify important nodes from different points,such as the location,authority and influence of nodes.In addition,research on directed networks is still rare.Most algorithms for directed networks is extended from algorithms for undirected networks by a slight extension or directly apply the algorithm suit for undirected network after undirecting the network,but they are not necessarily applicable to directed networks.At present,there are already mature researches and reliable conclusions for the macro topology of complex networks,such as scale-free property and small-world property.These conclusions can provide guiding ideas for identifying important nodes.In the framework of random walk,this paper first proposes three algorithms based on scale-free characteristics and small world characteristics: Scalefree Rank algorithm,Smallworld Rank algorithm and Topology Rank algorithm.Secondly,through experimental verification,this paper gives the recommendation that which one is more recommended among the three algorithms.These proposed algorithms are applied to the SIR simulation experiment on the real network,and the spreading range and spreading speed are used to verify the accuracy of the algorithm.In addition to this,the robustness of the algorithm is also verified.The performance of the algorithm is illustrated by comparison with the existing five classical algorithms.The experimental results show that the Scalefree Rank algorithm is superior to the Page Rank algorithm and the Leader Rank algorithm in both accuracy and robustness,but the accuracy is lower than the degree centrality,K-core decomposition and HITS algorithm;the Smallworld Rank algorithm and the Topology Rank algorithm are excellent in accuracy,better than the other five algorithms,but they are more sensitive to the edge-decoding noise in the individual network,so the robustness is slightly worse.Finally,through the horizontal comparison experiments of these three algorithms,the accuracy of the Smallworld Rank algorithm and the Topology Rank algorithm are almost the same,but it is far superior to the Scalefree Rank algorithm.In addition,the Topology Rank algorithm is more robust,so this paper recommends using the Topology Rank algorithm to identify important nodes in the network.Combined with the current points of node's importance and the definition of important nodes,the Topology Rank algorithm has better interpretability.The scale-free feature embodies the authority of the node;the small world property can reflect the node's ability to propagate.The Topology Rank algorithm considers both at the same time.The experimental results show that the algorithm has good performance and has good guiding significance for many realistic activities.