The Research Of Important Nodes Measuring Algorithm For Complicated Networks

Recently, the study on the algorithm of discovering important nodes in complex networks is becoming a research hotspot. It is very valuable to discover important nodes in complex networks for lots of areas, such as politics, medicine, society, information technology and so on. The effect of several important nodes on the networks is unbelievable. For example, information will be spread to the whole network in a very short time via a few important nodes. In addition, immunizing important nodes in the network can effectively control the spread of disease. In this thesis, we mainly focus on the research of the algorithm of discovering important nodes, and the main contens are as follows:1. Some classic algorithms are introduced, including Degree centrality, Betweeness centrality, Closeness centrality, Eigenvector centrality and PageRank algorithm. The advantages and disadvan-tages of these algorithms are discussed.2. According to the links between the adjacent nodes, a concept of “Contribution” and a new KSC algorithm based on the “Contribution” have been proposed in this work. A node in the real network links with some of its adjacent nodes more closely, and makes greater contribution to its neighbors. Unlike the classic algorithms where a node makes same contribution to its adjacent nodes, the consideration of different contributins is more reasonable. The KSC algorithm identifies influential nodes considering both their own properties and the contributions from their neighbors, and the property of a node is calculated by the K-Shell algorithm.3. Compared the KSC algorithm with several other classic algorithms, the simulation results on both real networks and computer-generated networks prove that the KSC algorithm can effectively identify the important nodes in the complex networks and is especially effective for the discovery of core nodes in the community.4. Extensive simulations are carried out simulating the effectiveness of the KSC algorithm in conjunction with the standard SIR spreading model. The KSC algorithm works well in the case of single infected node. Furthermore, immuning the important nodes discovered by the KSC algorithm will effectively control the spread of malicious information.