Research On Ranking The Influence Of Nodes On Complex Networks And Its Application

The interaction between the structure and behavior of a network makes the importance of nodes in the network structure and function be largely different.For different network functions,the criteria to identify important nodes are diverse.For the spreading processes in complex networks,such as the spreading of disease,information,behavior and failure,the nodes which can promote the diffusion of spreading to a large range or the nodes which can minimize the spreading range are the most important nodes.These nodes are called the most influential spreaders.Identifying the most influential nodes is critical to control the spreading process with limited resources,such as promoting the market sell and preventing the outbreaks of epidemics and the diffusion of rumors.Centrality measures are usually used to rank the importance of nodes in the network.In this dissertation,we study on the methods of ranking the influence of nodes and identifying influential spreaders in real-world complex networks.Our study is based on the centrality measures,network structure analysis and spreading dynamics.The ?-shell decomposition method is widely used to identify the core of a network and identify the most influential spreaders.We research on how it acts in different real-world networks.From large simulation results we find that,contrary to previous research results,not in all networks the core nodes identified by the ?-shell method are the most influential nodes.In some networks,the core nodes have very low spreading efficiency.To uncover the reason for the failure of the ?-shell method to identify the most influential spreaders,we analyze the local and global structure of different networks.From the link patterns of the network shell structure,we discover that the network core identified by the ?-shell method may be a fake core,which we call core-like group.We propose a link entropy to locate the core-like groups throughout the network.Our contribution lies in discovering that the core-like groups will result in the invalidation of the ?-shell method in identifying influential spreaders and proposing the entropy method to locate the corelike groups,which is significant for works that use the ?-shell method to identify network core and influential spreaders.To overcome the negative impact of the core-like group,which leads to the failure of the ?-shell decomposition method in identifying the core structure,we research on how to accurately identify the most influential spreaders in a spreading process.By extracting and comparing the true core and core-like group,we discover that the core-like group has a local structure that is similar to a clique.To quantify the structure differences between the true core and core-like group,we define a diffusion importance of edge to reflect the potential influence of the edge in a spreading process.By setting a threshold value,we propose that edges with a diffusion importance under the threshold are redundant links in the network.These redundant links contribute little in the spreading process but lead to form the core-like groups.Then by filtering out the redundant links in the network and implementing the ?-shell method on the residual graph,we obtain a new coreness which is much more accurate than the classical coreness in predicting the influence of nodes.This result makes great contribution for understanding the local structure of networks,and provides a new way to accurately identify influential spreaders.The discovery of redundant links is also useful for network based applications such as centrality,community detection and network control.The accuracy of ranking measures relates much to the local structure of the network.Considering that the location importance of a node not only depends on its own centrality,but may also relate to its neighbors' centrality,we propose a new measure to rank the influence of nodes,which is called the neighborhood centrality,and focus on the range of neighborhood,attenuation factor and spreading probability.We discover a saturation effect in considering the neighborhood of a node.Taking the 2-step neighborhood into calculation will balance the ranking accuracy and the needed information of network structure the best.This new measure can predict the influence of nodes in a spreading process more accurately than the degree and coreness centrality.Lastly,we research on how to quantify the diffusion importance of an edge by its local structure,and design a new network decomposition method.We find that the diffusion importance of an edge has a non-linear correlation with the local structure of the nodes on its both ends.We define a weight to quantify the diffusion importance of an edge and the network is turned into a weighted and directed network.According to the weighted centrality,we design a s-shell decomposition method based on the weighted edges.Results show that this method can decompose the network into shell structure more precisely but still has a low computational complexity.The weighted coreness outperforms degree and coreness in ranking the influence of nodes.