Research On Mining Algorithms Of Key Nodes In Complex Networks

The heterogeneous nature of real complex networks leads to nodes playing far different roles in structure and function.Therefore,mining the key nodes of complex networks is very significant and attracts increasing attentions from disciplines of network science and computer science.It helps us to control the outbreak of epidemics,advertise for e-commercial products accurately,predict the popularity of scientific publications,and more.Key nodes,called the most influential spreaders for spreading dynamics processes on complex networks,refer to nodes that can greatly spread disease,information,etc.It is universal to mine the key nodes in accordance with the properties of topological structure.Based on the global,local,and global-local properties of the network,combined with the characteristics of spreading dynamics,this thesis aims to study the algorithms of key nodes mining on real complex networks.The main work of this thesis is stated as follows.(1)Centrality algorithms proposed based on global properties are deficient to correctly mine the key nodes.Because they are not susceptible to the influence of the neighbors.To incorporate the properties of neighbors,we proposed an Iterative Resource Allocation(IRA)algorithm of which the resource to nodes are allocated based on its neighbors’ properties.After iterations,the resource amount on each node will be stable and the final resources of nodes are used to rank the key nodes.The IRA algorithm requires other centralities as its input to run,such as Degree Centrality,Closeness Centrality and so on.The experiment results show that the accuracy of the traditional centrality algorithms is remarkably enhanced by IRA algorithm.With further research,we found that the spreading influence of the node is also affected by the infection status of the neighbors.By considering this idea,we proposed an Improved Iterative Resource Allocation(IIRA)algorithm based on propagation features of nodes.Compared with the original IRA algorithm,the accuracy of IIRA algorithm on key nodes mining has been greatly improved.In addition,the idea of resource allocation is not only suitable for undirected network,but also applicable to directed network.Thus we proposed an Iterative PageRank Resource Allocation(IPRA)algorithm based on the IRA for key nodes mining on directed network.The accuracy of the IPRA algorithm has been significantly improved compared with the PageRank algorithm.(2)Traditional Eigenvector Centrality assumes that the influence of a node depends not only on the number of its neighbors,but also on the influence of each neighbor.That is to say,the influence of a node is the linear superposition of all the influence of its connected nodes.However,this assumption ignores the heterogeneity of local structures between different nodes.Inspired by this idea,we proposed an Eigen-Centrality based on the Differences and Similarities of local structure(ECDS)to mine the key nodes on complex network.The difference and similarity of ECDS algorithm depend on the Jaccard similarity between two random nodes.ECDS algorithm can be described as an eigenvalue problem in essence.Here,by setting a tunable parameter to adjust the weight of difference and similarity among structures in the algorithm,we can adjust the influence of difference and similarity of the accuracy of ECDS algorithm.Based on the experiments in four different real networks,the accuracy of ECDS algorithm is superior to the benchmark algorithms in obtaining the optimal value.(3)The existing algorithms of key nodes mining mainly take into account the nodes’ global or local properties of the network separately.However,the spreading influence of a node is affected by both global and local properties.If we remove a node,there is a threshold difference on epidemic outbreak between the residual network and the original network.We think that the threshold difference can represent the global property of the deleted node in the network.And the degree information of a node represent its local properties in the network.Otherwise,we can obtain the more accurate epidemic outbreak threshold of the Susceptible-Infected-Recovered(SIR)model by using the message passing theory.In view of these ideas,we proposed a Comprehensive Influence(CI)algorithm based on the global-local properties to mine the key nodes.The weight of the global properties and local properties in the CI algorithm is adjusted by a tunable parameter.Through the experiments in nine empirical networks with different structures,it is found that the parameters are focused around a specific value when the accuracy of the CI algorithm achieves the optimal value.Meanwhile,the accuracy of the CI algorithm is superior to the benchmark algorithms.This suggests that the CI algorithm has universality and can be applied to key nodes mining on most real networks with different structures.