Node Importance In Complex Networks

The rapid development of the computer, the Internet and the information technology make humanity more than ever before and more quickly obtain the necessary information and resources, meanwhile, which promote humanity to enter the information age.Networks are ubiquitous in nature. Identifying the most important nodes, or ranking the node importance by using the method of quantitative analysis in large scale networks are important problems in the complex networks.In this article, firstly, the metrics for node importance ranking in complex networks are reviewed, and the latest progresses in this field are summarized from two prospects:the network structure and the spreading dynamics. The merits, weaknesses and applicable conditions of different node importance ranking metrics are analyzed. Meanwhile,several important open problems are outlined as possible future directions. Finally,we propose several new methods to rank the node importance as following.Fristly, the k-shell decomposition for identifying influential nodes plays an important role in analyzing the spreading performance in complex networks, which generate lots of nodes with the smallest k-shell value. The spreading influences of these nodes cannot be distinguished by the K-shell decomposition method, as well as the degree and betweeness indices. In this section, by taking into account the k-shell information of the target node, we develop a new method to identify the node spreading ability with the minimum k-shell value. The experimental results for pretty good privacy and autonomous system networks show that the presented method could generate more accurate spreading list than the degree and betweeness indices.Secondly, identifying the node spreading influence in networks is an important task to optimally use the network structure and ensure the more efficient spreading in information. In this section, by taking into account the shortest distance between a target node and the node set with the highest k-shell value, we present an improved method to generate the ranking list to evaluate the node spreading influence. Comparing with the epidemic process results for four real networks and the Barab′asi-Albert network, the parameterless method could identify the node spreading influence more accurately than the ones generated by the degree k, closeness centrality, k-shell and mixed degree decomposition methods. This work would be helpful for deeply understanding the node importance of anetwork.Finally, most researchers use the degree or clustering coefficient to measure the node importance. However, the degree can only take into account the neighbor size, regardless the clustering property of the neighbors. The clustering coefficient could only measure the closeness among the neighbors and neglect the activity of the target node. In this section, we present a new method to measure the node importance by combining neighbor and clustering coefficient information. The network efficiency results, measured by removing the important nodes for the USAir network、 the Power grid of the western United States and Barab′asi-Albert networks show that the new method can more accurately evaluate the nodes’ importance than the degree, neighbor information and k-shell indices.In conclusion, ranking node importance in complex networks remains a challenge several fields. Various measures based on different topological structure have been proposed to describe a node importance. Indeed, different measures could manifest different network topology, which leads to different efficacy and applicability for ranking node importance in a network. The key issue is that the contribution of a node to the importance is not uniquely determined by the network topology but it is a result of the interplay between dynamics and network topology. Thus, our future research will focus on developing a universal and effective method to be complete in both respects for ranking node importance.