一种基于局部中心性的网络关键节点识别算法

作者：郑文萍; 吴志康; 杨贵

来源：计算机研究与发展, 2019, 56(09): 1872-1880.

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

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

• 单位
  山西大学