Research On Algorithm Of Important Node Discovery For Complex Networks

The problems in the field of complex networks have been lasted for several decades that have become hot research topics in many application areas. Complex network is an effective tool and mean to analyze a variety of complex systems, such as the nature and human society, which is widely recognized. With the promotions of many scholars at home and abroad, the related research has infiltrated into computer science, economics, management, life science, sociology, physics, or even multiple domains such as linguistics, literature and art. There is one kind of special nodes called ‘ important node ’ exist in complex networks, and they can influence the network structure and function even more significant than the rest of nodes within the network. At the same time, identifying the key nodes in complex networks has very important theoretical significance and application value to optimize the network structure, enhance network robustness and control information transmission dynamics,etc. Along with the rapid development of network science, therefore, the discovery of important nodes has been caused extensive concern of the world insight.The traditional recognition algorithms of the important nodes are degree centrality, betweenness centrality, closeness centrality and K-shell decomposition, etc.The degree centrality of one node only considers the most local properties;betweenness and closeness centrality are two global assessment, and they are difficult to spread to large-scale networks due to their complex calculation; K-shell decomposition determines the monophyletic core node by using the node location information, however, its distinguish strength was poor to rank the nodes in the same shell. These methods are relatively simple and are able to assess the importance of nodes to a certain extent. However, due to a lack of comprehensive review of the multi-dimensional characteristics of nodes, it will cause the assess results for each algorithm are not ideal.To identify the important nodes in complex networks more effective, we put forward two important nodes detection algorithm in this paper. One algorithm is basedon the ‘ K-shell influence matrix ’( Ks IM) and the other one is based on ‘ the integrated characteristic of three-dimensional ’( NI3). KsIM algorithm focuses on the topological hierarchy of networks, and characterizes the local dependency strength between neighborhood nodes by K-shell properties. Then, the node importance evaluation matrix is defined with nodes global efficiency. KsIM broke the limits of conventional methods which depict the node importance contribution with degree,and provided a new quantitative standard for the node importance contribution. NI3 algorithm is based on the analysis of three dimensional characteristics of transverse,longitudinal and layered, then, we define Width, Depth and Strength index. The Width refers to the direct neighbors of nodes, the Depth emphasizes the critical distance the influence can reach, and the Strength describes the intensity one node can affects other nodes within network. At last, we integrated the three dimensions as a quantitative index to express the importance of a node in complex network. The performance of this two proposed algorithms in this paper are both validated by SIR simulation experiments.SIR model can well simulate the spreading process of information and viruses,and it can be seen as the right-hand man to understand the related spreading mechanisms and to theoretically analysis this process. Using SIR simulation model and various evaluation standards, such as Kendall correlation coefficient, the imprecision rate and correlated heat, we examine KsIM and NI3 on several real network of different topological structures. And the experimental results show that the Ks IM and NI3 are effective, and the accuracy and the robustness for different topological structure of complex networks are better than traditional algorithms.The structure arrangement for this paper is as follows: the first chapter is introduction and introduces the research background, present situation and the significance of key nodes identification in complex network, and show the importance of our research; the second chapter and the third chapter respectively introduces the related important algorithms and the main algorithm evaluation criteria; then, we introduce especially two algorithms based on ‘ K-shell influence matrix ’( KsIM)and based on ‘ the integrated characteristic of three-dimensional ’( NI3) respectively;and in the fifth chapter, we gives the detailed processes of experimental verification;Finally, summarizes the full paper and prospects the research direction in the future.