• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

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

郑文萍, 吴志康, 杨贵

郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880. DOI: 10.7544/issn1000-1239.2019.20180831
引用本文: 郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880. DOI: 10.7544/issn1000-1239.2019.20180831
shu
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. DOI: 10.7544/issn1000-1239.2019.20180831
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. DOI: 10.7544/issn1000-1239.2019.20180831
shu
郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880. CSTR: 32373.14.issn1000-1239.2019.20180831
引用本文: 郑文萍, 吴志康, 杨贵. 一种基于局部中心性的网络关键节点识别算法[J]. 计算机研究与发展, 2019, 56(9): 1872-1880. CSTR: 32373.14.issn1000-1239.2019.20180831
shu
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. CSTR: 32373.14.issn1000-1239.2019.20180831
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. CSTR: 32373.14.issn1000-1239.2019.20180831
shu

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

  • 1(山西大学计算机与信息技术学院 太原 030006)

  • 2(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006)

  • 3(山西大学大数据科学与产业研究院 太原 030006) (wpzheng@sxu.edu.cn)

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

  • 中图分类号: TP181

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

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

Funds: 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.
    • HTML全文
    • 参考文献(0)
    • 相关文章
    • 施引文献(126)

  • 期刊类型引用(58)

    1. 史晓蒙，吕晓鹏，魏健康，王凌. 基于算法组合的端边云任务处理方法. 价值工程. 2024(36): 108-112 . 百度学术
    2. 谢虎，陈志伟，郭文鑫，赵瑞锋，刘洋. 基于边缘计算的电动汽车换电电池冗余度建模分析. 计量学报. 2023(05): 758-764 . 百度学术
    3. 魏兴慎，高鹏，吕卓，曹永健，周剑，屈志昊. 基于自适应交互反馈的电力终端信任度评估机制. 计算机应用. 2023(06): 1878-1883 . 百度学术
    4. 梅晶，戴龙宝，童钊，邓昕，王嘉珂. 资源约束下基于Lyapunov优化的自适应卸载算法. 计算机工程. 2023(07): 34-46 . 百度学术
    5. 谢虎，陈志伟，郭文鑫，赵瑞锋，刘洋. 基于边缘计算的电动汽车换电电池冗余度建模分析. 电源学报. 2023(04): 159-166 . 百度学术
    6. 赵金凤. 边缘计算场景下的即插即用关键技术及应用研究. 制造业自动化. 2023(11): 22-25 . 百度学术
    7. 邵梁，何星舟，尚俊娜. 边缘计算中利用改进型遗传算法的任务卸载策略. 计算机应用与软件. 2023(11): 48-57 . 百度学术
    8. 刘荆欣，王妍，韩笑，夏长清，宋宝燕. 基于Stackelberg博弈的边缘云资源定价机制研究. 计算机科学与探索. 2022(01): 153-162 . 百度学术
    9. 李媛. 基于边缘计算的在线学习资源压缩存储方法研究. 宁夏师范学院学报. 2022(01): 76-83 . 百度学术
    10. 李大鹏，李立新，杨清波，刘金波，张杰，刘东. 云边协同的调控云数据质量优化. 电力系统及其自动化学报. 2022(03): 11-19 . 百度学术
    11. 邹一荣，张洁琪，吴慎. 基于5G+MEC的多校区智慧校园协同生态建设. 信息通信技术. 2022(01): 28-33 . 百度学术
    12. 陈成，徐军，房董葵. 基于边缘计算的物联网数据安全处理模型. 信息技术. 2022(04): 137-142 . 百度学术
    13. 卞志勇，牛利平. 基于多径环境下的非同步OFDM网络定位技术. 计算机与现代化. 2022(04): 86-91 . 百度学术
    14. 宁黄江，郭翔宇，安健，刘芮汐. 工业互联网公共服务平台信任架构建设探究. 工业技术创新. 2022(02): 97-103 . 百度学术
    15. 张泽维，李陶深，杨林峰. 多目标优化的SWIPT-MEC任务分级卸载架构与优化算法. 广西大学学报(自然科学版). 2022(02): 487-497 . 百度学术
    16. 尼俊红，臧云. 基于MEC的计算资源分配方案研究. 信息与电脑(理论版). 2022(10): 84-89 . 百度学术
    17. 熊小峰，黄淳岚，乐光学，戴亚盛，杨晓慧，杨忠明. 边缘计算中基于综合信任评价的任务卸载策略. 电子学报. 2022(09): 2134-2145 . 百度学术
    18. 栾奇麒，程力涵，李春鹏，蒋峰，宋庆武. 基于智能边缘计算的物联接入网关容错机制研究. 电子设计工程. 2022(23): 90-93+98 . 百度学术
    19. 陈璐，汤红波，游伟，柏溢. 移动边缘计算安全防御研究. 网络与信息安全学报. 2021(01): 130-142 . 百度学术
    20. 胡金磊，朱泽锋，林孝斌，黎阳羊，刘剑，沈若瑾. 变电站无人机机巡边缘计算框架设计及资源调度方法. 高电压技术. 2021(02): 425-433 . 百度学术
    21. 周舟，袁余俊明，李方敏. 云数据中心服务器能耗建模及量化计算. 湖南大学学报(自然科学版). 2021(04): 36-44 . 百度学术
    22. 刘昕林，邓巍，黄萍. 基于QoS的无线网络空间信息资源优化调度模型. 自动化与仪器仪表. 2021(04): 67-70 . 百度学术
    23. 范颖，沈建京. 动态队列下入侵肿瘤生长优化和BPNN的云计算任务调度新方法. 计算机应用与软件. 2021(07): 281-288 . 百度学术
    24. 由新红，张志轩，李帅，张鹏平. 山东低压配电物联网数据采集及应用分析. 山东电力技术. 2021(08): 25-30+48 . 百度学术
    25. 李知艺，宋克轩. 基于云边协同计算的主动配电网调度研究评述. 浙江电力. 2021(06): 15-21 . 百度学术
    26. 诸茂华，关月芝，温玉波，刘绮姮. 边缘计算在优化远岛观测数据传输中的应用研究. 海洋开发与管理. 2021(06): 87-92 . 百度学术
    27. 赵国生，王甜甜，王健. 一种边缘设备动态信任度的评估模型. 计算机工程与科学. 2021(09): 1574-1583 . 百度学术
    28. 聂清彬，陈飞旭，秦美峰，曹耀钦. 基于QoS云计算任务调度优化. 重庆大学学报. 2021(09): 109-116 . 百度学术
    29. 徐琴，谢东亮，邓秋菊. 基于区块链技术的边缘计算资源最优分配方法. 现代电子技术. 2021(23): 22-26 . 百度学术
    30. 温瑶，陆晶晶，卢华，谢人超. 融合区块链的算力网络信任评估与保障方案研究. 南京邮电大学学报(自然科学版). 2021(04): 99-106 . 百度学术
    31. 柳晨. 金属结构机械加工自动化控制系统设计及实践. 世界有色金属. 2020(01): 28-29 . 百度学术
    32. 郭丹丹，王菲. 云计算环境下海量通信信息无损加密方法研究. 通信电源技术. 2020(04): 50-51 . 百度学术
    33. 白昱阳，黄彦浩，陈思远，张俊，李柏青，王飞跃. 云边智能:电力系统运行控制的边缘计算方法及其应用现状与展望. 自动化学报. 2020(03): 397-410 . 百度学术
    34. 乐光学，戴亚盛，杨晓慧，刘建华，游真旭，朱友康. 边缘计算可信协同服务策略建模. 计算机研究与发展. 2020(05): 1080-1102 . 本站查看
    35. 陈孝文，王保强. 基于平行坐标系的主数据流转监控方法研究. 计算机产品与流通. 2020(08): 108 . 百度学术
    36. 杜瑞忠，许琨琪，田俊峰. 基于图论的边缘计算信任评估优化模型. 工程科学与技术. 2020(03): 150-158 . 百度学术
    37. 曾俊义. 基于多层移动边缘计算的应用系统内容交付效率提升. 自动化技术与应用. 2020(06): 38-41 . 百度学术
    38. 齐平，王福成，徐佳，李学俊. 移动边缘计算环境下基于信任模型的可靠多重计算卸载策略. 计算机集成制造系统. 2020(06): 1616-1627 . 百度学术
    39. 鄢晶，高天露，张俊，王旭. 边云链协同技术在能源互联网数据管理中的应用及展望. 华电技术. 2020(08): 41-47 . 百度学术
    40. 石文玉，张蕊. 边云协同计算中安全感知的工作流任务调度策略. 长春师范大学学报. 2020(08): 35-41 . 百度学术
    41. 张伟. 边缘计算的任务迁移机制研究. 软件导刊. 2020(09): 48-53 . 百度学术
    42. 闫戈，吴婷，杨诚，汪浩，谭艾迪. 基于边缘计算的舰炮故障预测系统设计. 计算机测量与控制. 2020(12): 17-20+26 . 百度学术
    43. 朱友康，乐光学，杨晓慧，刘建生. 边缘计算迁移研究综述. 电信科学. 2019(04): 74-94 . 百度学术
    44. 戴亚盛，游真旭，朱友康，杨晓慧. 无线Mesh网络协同节点信誉评价建模. 软件导刊. 2019(04): 158-162 . 百度学术
    45. 危泽华，曾玲玲. 基于Stackelberg博弈论的边缘计算卸载决策方法. 数学的实践与认识. 2019(11): 91-100 . 百度学术
    46. 仇公望，詹景坤，吕殿君，王小辉. 基于边缘计算的航天器电气系统设计. 电子测试. 2019(13): 12-15 . 百度学术
    47. 简琤峰，裘科意，张美玉. 一种面向边缘计算QoE的服务组合及调度方法. 小型微型计算机系统. 2019(07): 1397-1403 . 百度学术
    48. 宁振宇，张锋巍，施巍松. 基于边缘计算的可信执行环境研究. 计算机研究与发展. 2019(07): 1441-1453 . 本站查看
    49. 吴宏杰，沈华祥，凌华靖，傅启明，陆卫忠，付保川. 基于边缘计算的建筑设备状态感知模型与应用. 计算机工程与应用. 2019(18): 263-270 . 百度学术
    50. 袁培燕，蔡云云. 移动边缘计算中一种贪心策略的内容卸载方案. 计算机应用. 2019(09): 2664-2668 . 百度学术
    51. 肖文华，刘必欣，刘巍，程钢，王跃华. 面向恶劣环境的边缘计算综述. 指挥与控制学报. 2019(03): 181-190 . 百度学术
    52. 简琤峰，陈家炜，张美玉. 面向边缘计算的改进混沌蝙蝠群协同调度算法. 小型微型计算机系统. 2019(11): 2424-2430 . 百度学术
    53. 乐光学，戴亚盛，杨晓慧，朱友康，游真旭，刘建生. 边缘计算多约束可信协同任务迁移策略. 电信科学. 2019(11): 36-50 . 百度学术
    54. 魏坚，余涛，赵子杰，陆剑峰，王舜禹. 机加工行业工业云边缘设备功能及应用. 自动化仪表. 2019(11): 1-5 . 百度学术
    55. 胡应鑫. 基于多目标粒子群的边缘云资源调度策略. 电信技术. 2019(12): 137-140 . 百度学术
    56. 朱茗，汪京培. 边缘计算模式下服务网络安全可靠问题研究. 电子产品可靠性与环境试验. 2019(S1): 77-81 . 百度学术
    57. 郭玉华，贾宝军，侯乐，程筱彪，徐雷. 基于RSD的边缘数据中心构建方法研究. 信息通信技术. 2018(05): 16-21 . 百度学术
    58. 张立婷，李世超，郑东梁，石硕，曾鹏. 工业无线通信技术讲座 第七十一讲 基于边缘计算的智能油田系统构建. 仪器仪表标准化与计量. 2018(05): 8-11 . 百度学术

    其他类型引用(68)

    • 资源附件(0)
计量
  • 文章访问数:  1430
  • HTML全文浏览量:  3
  • PDF下载量:  703
  • 被引次数: 126
出版历程
  • 发布日期:  2019-08-31

目录

摘要
HTML全文
    参考文献(0)
    相关文章
    施引文献(126)
    资源附件(0)

    /

    返回文章
    返回
    邮件订阅 RSS
    微信订阅号<br/>（实时资讯）

    微信订阅号
    （实时资讯）

    微信服务号<br/>（同步网站）

    微信服务号
    （同步网站）

    微信视频号<br/>（视频分享）

    微信视频号
    （视频分享）

    CCF<br/>（扫码入会）

    CCF
    （扫码入会）

    版权所有 © 《计算机研究与发展》编辑部

    本系统由北京仁和汇智信息技术有限公司开发  百度统计