Efficient Algorithm for the Identification of Node Significance in Complex Network
Yirun Ruan, Jun Tang, Yanli Hu, Haoran Wang, Liang Bai
Abstract
Identifying vital nodes is a significant issue for the study of network robustness, epidemic controlling and targeted destruction of networks. Previous studies on weak ties theory recovered that ties with weak strength usually act as the important bridges that connect different clusters and play important role in maintaining the network connectivity. In this paper, we quantify the strength of links based on local information of the network topology, and design a simple yet effective method to evaluate nodes' importance in terms of the number of their connections and overlap of their neighbors. Experimental analyses on synthetic and real networks demonstrate that the proposed algorithm identifies vital nodes leading to faster network collapse in target destruction than some well-known methods.