ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (9): 1872-1880.doi: 10.7544/issn1000-1239.2019.20180831

• 人工智能 • 上一篇    下一篇


郑文萍1,2,3, 吴志康1, 杨贵1   

  1. 1(山西大学计算机与信息技术学院 太原 030006); 2(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006); 3(山西大学大数据科学与产业研究院 太原 030006) (
  • 出版日期: 2019-09-10
  • 基金资助: 
    山西省回国留学人员科研资助项目 (2017-014);山西省自然科学基金项目(201801D121123);国家自然科学基金项目(61572005)

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).

摘要: 关键节点识别已经成为分析与理解复杂网络特性、结构、功能的有效方式.提出了一种基于节点中心性的关键节点识别算法框架(greedy algorithm for critical node problem, GCNP),根据某种中心性指标选择一个网络的初始点覆盖集;从网络中删除该点覆盖集,迭代选择点覆盖集中使原网络连通节点对增加最小的节点向原网络回添,直至点覆盖集中节点满足用户给定的待删除关键节点数.为了更好地选择初始的节点覆盖集,提出了一种基于局部拓扑信息的节点中心性度量指标(local neighbor centrality, LNC).在16个人工网络和9个真实网络上的实验结果表明:与单独使用各中心性指标相比,采用GCNP算法框架可以提高算法性能.此外,所提的节点中心性度量指标LNC较度中心性(degree centrality, DC)、LocalRank中心性、K壳中心性(K-Shell, KS)、 局部度和中心性(local degree sum centrality, LDS)能更准确地评估节点的重要性.

关键词: 关键节点, 复杂网络, 网络连通性, 点覆盖集, 局部中心性

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