ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2019, Vol. 56 ›› Issue (9): 1872-1880.doi: 10.7544/issn1000-1239.2019.20180831

Previous Articles     Next Articles

A Novel Algorithm for Identifying Critical Nodes in Networks Based on Local Centrality

Zheng Wenping1,2,3, Wu Zhikang1, Yang Gui1   

  1. 1(School of Computer and Information Technology, Shanxi University, Taiyuan 030006); 2(Key Laboratory of Computational Intelligence & Chinese Information Processing (Shanxi University), Ministry of Education, Taiyuan 030006); 3(Research Institute of Big Data Science and Industry, Shanxi University, Taiyuan 030006)
  • Online:2019-09-10
  • Supported by: 
    This work was supported by the Research Project of Shanxi Scholarship Council of China (2017-014), the Natural Science Foundation of Shanxi (201801D121123), and the National Natural Science Foundation of China (61572005).

Abstract: Identifying critical nodes in a network is important to understand the connectivity property and dynamic characteristic of the network. Critical node problem has wide applications in field of social network, terrorist network, immunization network, etc. The removal of critical nodes might degrade network connectivity significantly. An algorithm, named as GCNP (greedy algorithm for critical node problem), is proposed based on the centrality of nodes. Firstly, GCNP selects nodes according to a kind of centrality measure, such as degree, betweenness, LocalRank, and so on, to obtain a vertex cover of the interesting network. A residual graph is obtained after deleting the vertex cover set from the network. Since the size of selected vertex cover set is always larger than the preset size of critical node set. Then, GCNP would choose nodes greedily from the vertex cover to add back to the residual network iteratively, until the number of deleted nodes satisfies preset size of critical node set. The node whose replacement would lead to minimum increment of the pairwise connectivity in the residual graph would be put back first. A centrality measure LNC (local neighbor centrality) based on local topological characteristics is defined to select nodes of initial vertex cover. Experimental results on 16 artificial networks and 9 real networks show that the proposed algorithm framework GCNP could improve the performance of some classical centrality measures for identifying critical nodes in a complex network. And the proposed centrality measure LNC is more effective in evaluating the importance of nodes than degree centrality, LocalRank centrality, K-Shell centrality and local degree sum centrality.

Key words: critical nodes, complex network, network connectivity, vertex cover, local centrality

CLC Number: