Identification Of The Influential Spreaders In Complex Networks

The study of complex network is very helpful for people to understand the operation mechanism of complex system and the role of the individual during the operation process from macroscopic and microscopic.The propagation dynamics,as an important aspect of the complex network research,has received extensive attention in recent years.The spreading process over networks is everywhere in our life.In fact,identifying and making full use of the nodes with high influence in the network will help to control the direction of public opinion in the social network,promote the large-scale promotion of new products,and control the outbreak of epidemics in the contact network.At present,a large number of central indicators have been proposed to measure the spreading ability of nodes’ in complex networks.These indicators examine the importance of nodes in the network from different perspectives.Although they have advantages in some aspects,there are still some problems.On one hand,degree centrality and k-shell decomposition method are both simple algorithms which own low time complexity.However,they usually divide a network into coarse grain size,which is not consistent with the real situation.On the other hand,though the factors considered for closeness centrality,betweenness centrality and eigenvector centrality are more comprehensive,the running time of these algorithms is much higher,which is not suitable for large-scale network.Combining with current research status and existing problems,the main innovative work and research results are summarized as follows:1)To design classification neighbor algorithm.According to the removal order of nodes in the k-shell decomposition process,we classify the neighbors of nodes,and distinguish the contribution of neighbors to the spreading ability of nodes by assigning different weights to different categories of neighbors.It is believed that the node who owns more neighbors and whose neighbors are much closer to the core of the network is more important in the network.The classification neighbor algorithm is compared with the degree centrality algorithm,the k-shell decomposition algorithm and the mixed degree decomposition algorithm(MDD).The results show that,compared with the other three algorithms,the spreading ability ranking result of classification neighbor algorithm is much closer to that of the simulation based on SIR model.In addition,classification neighbor algorithm also has absolute advantages on ranking discrimination.In terms of time complexity,as classification neighbor algorithm is based on k-shell decomposition algorithm to classify nodes’ neighbors,it takes a little more time than k-shell decomposition algorithm when analyzing the same network.However,it has obvious advantages compared with MDD algorithm.2)To analyze and improve the gravity centrality algorithm.The original gravity centrality considers the k-shell value of the node as its "mass" and calculates the sum of the nodes’ influence on the reachable neighbors within the N steps.We attempt to use different centrality indicators as the "mass" of the nodes to investigate their performance.When degree is regarded as the node’s "mass",both the node’s degree and the sum of the gravitation from the focal node to its neighbors within N steps taking neighbors scale into consideration.In order to eliminate the excessive consideration,we try to use k-shell value as the focal node’s "mass" and degree as its neighbors’ "mass".The simulation experiments in 6 real networks and 4 BA scale-free networks show that in most cases,compared with the gravity centrality algorithm which uses other centrality indicators as the "mass" of the nodes,the performance of the mixed gravity centrality method we proposed is much better.