• 中国精品科技期刊
  • 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)
    • 相关文章
    • 施引文献(40)

  • 期刊类型引用(17)

    1. 刘建设. 基于深度学习的通信网关键节点自动识别方法. 自动化技术与应用. 2024(03): 104-107 . 百度学术
    2. 韩奕，孙百兵，王军国，杜彦辉. 基于关键节点识别算法的重点人分析. 北京航空航天大学学报. 2024(07): 2074-2082 . 百度学术
    3. 许钦钧，徐龙琴，刘双印，赵学华. 一种基于网络拓扑的关键节点挖掘算法. 仲恺农业工程学院学报. 2023(02): 21-30 . 百度学术
    4. 李姣军，杨川，杨凡，喻涛，杜源昌，陈征骥. 面向M2M通信的网络分层与窗口控制接入策略. 重庆理工大学学报(自然科学). 2023(08): 245-254 . 百度学术
    5. 许钦钧，徐龙琴，刘双印，赵学华. 基于飞蛾扑火算法的关键节点挖掘方法. 计算机应用研究. 2023(09): 2713-2719+2728 . 百度学术
    6. 陈端兵，杨志杰，曾卓，傅彦，周俊临，赵俊严. 基于子图特征的节点排序算法. 计算机科学. 2023(S2): 443-449 . 百度学术
    7. 刘琳岚，谭镇阳，舒坚. 基于图神经网络的机会网络节点重要度评估方法. 计算机研究与发展. 2022(04): 834-851 . 本站查看
    8. 卢玉华，高文俊，张伟. 基于边缘计算技术的终端设备远程部署节点智能识别研究. 计算技术与自动化. 2022(01): 175-179 . 百度学术
    9. 郝志刚，秦丽. 基于多属性综合评价的食品安全标准引用网络重要节点发现方法. 计算机应用. 2022(04): 1178-1185 . 百度学术
    10. 吴誉兰，舒建文. 异构集群中密集型大数据负载网络调度仿真. 计算机仿真. 2022(04): 445-449 . 百度学术
    11. 赖强，张宏昊. Analysis of identification methods of key nodes in transportation network. Chinese Physics B. 2022(06): 898-905 . 百度学术
    12. 刘海姣，马慧芳，赵琪琪，李志欣. 融合用户兴趣偏好与影响力的目标社区发现. 计算机研究与发展. 2021(01): 70-82 . 本站查看
    13. 石丽娟，孙钦明. 灰色系统理论下复杂网络可靠性度量挖掘方法. 计算机仿真. 2021(02): 287-290+325 . 百度学术
    14. 杨旭华，熊帅. 利用网络表征学习辨识复杂网络节点影响力. 小型微型计算机系统. 2021(02): 418-423 . 百度学术
    15. 游倩婧，郑巍，刘方利. 基于重叠盒覆盖算法的节点重要度评估. 计算机应用研究. 2021(11): 3354-3358 . 百度学术
    16. 朱敬成，刘辉，王伦文，吴涛. 基于网络拓扑重合度的关键节点识别方法. 计算机应用研究. 2021(12): 3581-3585 . 百度学术
    17. 李青，徐子闻. 基于集成降噪自编码的网络入侵多模式匹配算法设计. 广西大学学报(自然科学版). 2020(03): 530-537 . 百度学术

    其他类型引用(23)

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

目录

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

    /

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

    微信订阅号
    （实时资讯）

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

    微信服务号
    （同步网站）

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

    微信视频号
    （视频分享）

    CCF<br/>（扫码入会）

    CCF
    （扫码入会）

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

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