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

¹(山西大学计算机与信息技术学院 太原 030006); ²(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006); ³(山西大学大数据科学与产业研究院 太原 030006) (wpzheng@sxu.edu.cn)

出版日期: 2019-09-10


基金资助:山西省回国留学人员科研资助项目 (2017-014);山西省自然科学基金项目(201801D121123);国家自然科学基金项目(61572005)

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

Zheng Wenping^1,2,3, Wu Zhikang¹, Yang Gui¹

¹(School of Computer and Information Technology, Shanxi University, Taiyuan 030006); ²(Key Laboratory of Computational Intelligence & Chinese Information Processing (Shanxi University), Ministry of Education, Taiyuan 030006); ³(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

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

参考文献

相关文章 15

[1]	郑文萍,车晨浩,钱宇华,王杰. 一种基于标签传播的两阶段社区发现算法[J]. 计算机研究与发展, 2018, 55(9): 1959-1971.
[2]	潘伟丰,姜波,李兵,胡博,宋贝贝. 基于组合历史的交互式服务推荐方法[J]. 计算机研究与发展, 2018, 55(3): 613-628.
[3]	张雪松,贾彩燕. 一种基于频繁词集表示的新文本聚类方法[J]. 计算机研究与发展, 2018, 55(1): 102-112.
[4]	刘琳岚,张江,舒坚,郭凯,孟令冲. 基于多属性决策的机会传感器网络关键节点预测[J]. 计算机研究与发展, 2017, 54(9): 2021-2031.
[5]	陈俊宇,周刚,南煜,曾琦. 一种半监督的局部扩展式重叠社区发现方法[J]. 计算机研究与发展, 2016, 53(6): 1376-1388.
[6]	王莹,于海,朱志良. 基于软件节点重要性的集成测试序列生成方法[J]. 计算机研究与发展, 2016, 53(3): 517-530.
[7]	潘伟丰,李兵,周晓燕,何鹏. 基于错误传播网络的回归测试用例排序方法[J]. 计算机研究与发展, 2016, 53(3): 550-558.
[8]	李全刚,刘峤,秦志光. 基于主题模型的通信网络建模与仿真[J]. 计算机研究与发展, 2016, 53(1): 206-215.
[9]	刘志宏,曾勇,吴宏亮,马建峰. 复杂网络的影响可控性[J]. 计算机研究与发展, 2014, 51(12): 2788-2796.
[10]	葛 新, 赵 海, 张 君,. 网络度相关及其传播特征研究[J]. , 2013, 50(4): 741-749.
[11]	刘大有, 金 弟, 何东晓, 黄 晶, 杨建宁, 杨 博,. 复杂网络社区挖掘综述[J]. , 2013, 50(10): 2140-2154.
[12]	郭 迟, 王丽娜, 关怡萍, 张笑盈,. 一种基于动态偏好扫描的网络免疫策略[J]. , 2012, 49(4): 717-724.
[13]	邓小龙 王 柏 吴 斌 杨胜琦. 基于信息熵的复杂网络社团划分建模和验证[J]. , 2012, 49(4): 725-734.
[14]	郭 迟, 王丽娜, 李 玉, 周芙蓉,. 基于负荷-容量模型的网络相继故障研究[J]. , 2012, 49(12): 2529-2538.
[15]	姚益平 张颖星. 集群计算环境下基于复杂网络的社会学仿真负载划分优化算法[J]. , 2011, 48(9): 1759-1767.

PDF全文下载地址:

https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4003