郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880.
 引用本文: 郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880.
Zheng Wenping, Wu Zhikang, Yang Gui. A Novel Algorithm for Identifying Critical Nodes in Networks Based on Local Centrality[J]. Journal of Computer Research and Development, 2019, 56(9): 1872-1880.
 Citation: Zheng Wenping, Wu Zhikang, Yang Gui. A Novel Algorithm for Identifying Critical Nodes in Networks Based on Local Centrality[J]. Journal of Computer Research and Development, 2019, 56(9): 1872-1880.

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

• 摘要: 关键节点识别已经成为分析与理解复杂网络特性、结构、功能的有效方式.提出了一种基于节点中心性的关键节点识别算法框架(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.

/

• 分享
• 用微信扫码二维码

分享至好友和朋友圈