计算机科学 ›› 2021, Vol. 48 ›› Issue (7): 130-136.doi: 10.11896/jsjkx.201000108

• 数据库&大数据&数据科学 • 上一篇    下一篇

基于重连机制的复杂网络鲁棒性分析

穆俊芳1,2, 郑文萍1,2, 王杰3, 梁吉业1,2   

  1. 1 山西大学计算机与信息技术学院 太原030006
    2 计算智能与中文信息处理教育部重点实验室(山西大学) 太原030006
    3 山西财经大学信息学院 太原030006
  • 收稿日期:2020-10-19 修回日期:2021-04-09 出版日期:2021-07-15 发布日期:2021-07-02
  • 通讯作者: 郑文萍(wpzheng@sxu.edu.cn)
  • 基金资助:
    国家自然科学基金(62072292,62006145);山西省重点研发计划项目(201903D121162);山西省自然科学基金(201801D121123);山西省回国留学人员科研基金项目(2017-014);山西省1331工程项目

Robustness Analysis of Complex Network Based on Rewiring Mechanism

MU Jun-fang1,2, ZHENG Wen-ping1,2, WANG Jie3, LIANG Ji-ye1,2   

  1. 1 School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China
    2 Key Laboratory of Computation Intelligence and Chinese Information Processing,Shanxi University,Taiyuan 030006,China
    3 College of Information,Shanxi University of Finance and Economics,Taiyuan 030006,China
  • Received:2020-10-19 Revised:2021-04-09 Online:2021-07-15 Published:2021-07-02
  • About author:MU Jun-fang,born in 1991,candidate Ph.D,is a member of China Computer Federation.Her main research interests include complex network and bioinformatics,etc.(1379680219@qq.com)
    ZHENG Wen-ping,born in 1979,Ph.D,associate professor,Ph.D supervisor,is a member of China Computer Federation.Her main research interests include network science and bioinforma-tics,etc.
  • Supported by:
    National Natural Science Foundation of China (62072292,62006145),Projects of Key Research and Development Plan of Shanxi Province (201903D121162),Natural Science Foundation of Shanxi Province(201801D121123),Shanxi Scholarship Council of China(2017-014) and 1331 Engineering Project of Shanxi Province,China.

摘要: 随着电力系统、交通系统、通信系统等基础设施网络的广泛使用,提高复杂网络的鲁棒性具有重要意义。重连机制是一种高效且简洁的方法,常用于提高网络的鲁棒性。基于0阶零模型的重连机制通过对边的随机删除和创建操作来提高网络的鲁棒性,其尽管保持了网络的边数,但会引起节点的度值发生变化,如基于香农熵的重连算法;基于1阶零模型的重连机制通过随机选择两条边进行换边操作来提高网络的鲁棒性,其尽管保持了网络的度分布,但随机选边难以准确找到合适的节点,增加了算法的时间成本,如基于最大连通分支的重连算法。因此,为了保持网络的度分布且快速提高网络的鲁棒性,提出了一种基于1阶零模型的快速重连算法(Fast Rewiring Mechanism based on 1-order Null Model,FRM)。FRM算法通过比较每条边的两个端点度值的差异为边加权,根据边的权重优先选择权重较大的两条边,并创建度值相似节点之间的连边来提高网络的鲁棒性。在3个真实网络数据上与4种代表性重连算法相比,对比实验结果表明,FRM算法在度中心性、介数中心性和Page-Rank中心性攻击下最大连通分支中的节点比例s(Q)、基于最大连通分支的鲁棒性指标R和基于香农熵的鲁棒性指标I(G)的表现都更好。

关键词: 复杂网络, 鲁棒性, 香农熵, 重连机制, 最大连通分支

Abstract: With the widespread use of infrastructure networks such as power systems,transportation systems,and communication systems,it is of great significance to improve the robustness of complex networks.The rewiring mechanism is an efficient and simple method to improve the robustness of the network.The rewiring mechanism based on the 0-order null model improves the robustness of the network by randomly deleting and creating edges.Although the number of edges is maintained,the degree of nodes will change,such as the RM-ES algorithm.The rewiring mechanism based on the 1-order null model improves the robustness of the network by randomly selecting two edges for rewiring,although the degree distribution is maintained,it is difficult to find the appropriate nodes by random edge selection,which increases the running time of algorithms,such as the RM-LCC algorithm.Therefore,in order to maintain the degree distribution and improve the robustness of the network,this paper proposes a fast rewiring mechanism based on 1-order null model,called FRM.The FRM algorithm first weights the edges by degree for each edge,then selects two edges with the probability proportional to the weight of edge,finally,creates the edges between nodes with similar degree.We compare the FRM algorithm with other methods on real network data sets.The experimental results of three real network data show that FRM algorithm performs better than four representative rewiring algorithms under the attack of degree centrality,betweenness centrality and PageRank centrality with respect to the ratio of nodes in largest connected component s(Q),robustness index R and robustness index I(G).

Key words: Complex network, Largest connected component, Rewiring mechanism, Robustness, Shannon entropy

中图分类号: 

  • TP181
[1]BOCCALETTIA S,LATORAB V,MORENOD Y,et al.Com-plex networks:structure and dynamics[J].Physics Reports,2006,424(4/5):175-308.
[2]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256.
[3]YANG D,LIAO X,SHEN H,et al.Dynamic node immunization for restraint of harmful information diffusion in social networks[J].Physica A:Statistical Mechanics and its Applications,2018,503(1):640-649.
[4]ARENAS A,ALBERT D G,KURTHS J,et al.Synchronization in complex networks[J].Physics Reports,2008,469(3):93-153.
[5]WANG J,LIANG J Y,ZHENG W P,et al.A graph clustering method for detecting protein complexes[J].Journal of Compu-ter Research and Development,2015,52(8):1784-1793.
[6]ZHENG W P,CHE C H,QIAN Y H,et al.A graph clustering algorithm based on paths between nodes in complex networks[J].Chinese Journal of Computer,2018,492(15):1958-1966.
[7]WANG Z Q,LIANG J Y,LI R,et al.An approach to cold-start link prediction:Establishing connections between non-topological and topological information[J].IEEE Transaction on Knowledge and Data Engineering,2016,28:2857-2870.
[8]LIU Z H.Dynamics on complex networks[J].Scientia SinicaPhysica,Mechanica & Astronomica,2020(50):010501.
[9]NEWMAN M E J.Networks:An Introduction[M].Oxford Unversity Press,2010.
[10]WANG X F,LI X,CHENG G R.Network science:An introduction[M].Higher Education Press,2012.
[11]SAFAEI F,YEGANLOO H,AKBAR R.Robustness on topo-logy reconfiguration of complex networks:An entropic approach[J].Mathematics and Computers in Simulation,2020(170):379-409.
[12]HERRMANN H J,SCHNEIDER C M,MOREIRA A A,et al.Onion-like network topology enhances robustness against malicious attacks[J].Journal of Statistical Mechanics:Theory and Experiment,2011(2011):01027.
[13]SCHNEIDER C M,MOREIRA A A,ANDRADE J S,et al.Miti-gation of malicious attacks on networks[J].Proceedings of the National Academy of Sciences,2011(108):3838-3841.
[14]LOUZADA V H P,DAOLIO F,HANS J,et al.Smart rewiring for network robustness[J].IO:Theory eJournal,2013(1):150-159.
[15]BAI L,XIAO Y D,HOU L L,et al.Smart rewiring:Improving network robustness faster[J].Chinese Physics Letters,2015(32):078901.
[16]MIEGHEM P V,WANG H,GE X S,et al.Influence of assortativity and degree-preserving rewiring on the spectra of networks [J].The European Physical Journal B,2010(76):643-652.
[17]ROSSI R A,AHMED N K.The network data repository with interactive graph analytics and visualization[C]//Twenty-Ninth AAAI Conference on Artificial Intelligence.AAAI Press,2015:4292-4293.
[18]JEONG H,MASON S P,BARABASI A L,et al.Oltvai,Lethality and centrality in protein networks[J].Nature,2001(411):41-42.
[19]JOY M P,BROCK A L,INGBER D E,et al.High-betweenness proteins in the yeast protein interaction network[J].Journal of Biomedicine and Biotechnology,2005(2):96-103.
[20]BONACICH P.Power and Centrality:A family of measures[J].American Journal of Sociology,1987 (92):1170-1182.
[1] 郑文萍, 刘美麟, 杨贵.
一种基于节点稳定性和邻域相似性的社区发现算法
Community Detection Algorithm Based on Node Stability and Neighbor Similarity
计算机科学, 2022, 49(9): 83-91. https://doi.org/10.11896/jsjkx.220400146
[2] 周慧, 施皓晨, 屠要峰, 黄圣君.
基于主动采样的深度鲁棒神经网络学习
Robust Deep Neural Network Learning Based on Active Sampling
计算机科学, 2022, 49(7): 164-169. https://doi.org/10.11896/jsjkx.210600044
[3] 杨波, 李远彪.
数据科学与大数据技术课程体系的复杂网络分析
Complex Network Analysis on Curriculum System of Data Science and Big Data Technology
计算机科学, 2022, 49(6A): 680-685. https://doi.org/10.11896/jsjkx.210800123
[4] 闫萌, 林英, 聂志深, 曹一凡, 皮欢, 张兰.
一种提高联邦学习模型鲁棒性的训练方法
Training Method to Improve Robustness of Federated Learning
计算机科学, 2022, 49(6A): 496-501. https://doi.org/10.11896/jsjkx.210400298
[5] 何茜, 贺可太, 王金山, 林绅文, 杨菁林, 冯玉超.
比特币实体交易模式分析
Analysis of Bitcoin Entity Transaction Patterns
计算机科学, 2022, 49(6A): 502-507. https://doi.org/10.11896/jsjkx.210600178
[6] 王本钰, 顾益军, 彭舒凡, 郑棣文.
融合动态距离和随机竞争学习的社区发现算法
Community Detection Algorithm Based on Dynamic Distance and Stochastic Competitive Learning
计算机科学, 2022, 49(5): 170-178. https://doi.org/10.11896/jsjkx.210300206
[7] 陈世聪, 袁得嵛, 黄淑华, 杨明.
基于结构深度网络嵌入模型的节点标签分类算法
Node Label Classification Algorithm Based on Structural Depth Network Embedding Model
计算机科学, 2022, 49(3): 105-112. https://doi.org/10.11896/jsjkx.201000177
[8] 赵学磊, 季新生, 刘树新, 李英乐, 李海涛.
基于路径连接强度的有向网络链路预测方法
Link Prediction Method for Directed Networks Based on Path Connection Strength
计算机科学, 2022, 49(2): 216-222. https://doi.org/10.11896/jsjkx.210100107
[9] 张程瑞, 陈俊杰, 郭浩.
静息态人脑功能超网络模型鲁棒性对比分析
Comparative Analysis of Robustness of Resting Human Brain Functional Hypernetwork Model
计算机科学, 2022, 49(2): 241-247. https://doi.org/10.11896/jsjkx.201200067
[10] 李家文, 郭炳晖, 杨小博, 郑志明.
基于信息传播的致病基因识别研究
Disease Genes Recognition Based on Information Propagation
计算机科学, 2022, 49(1): 264-270. https://doi.org/10.11896/jsjkx.201100129
[11] 胡军, 王雨桐, 何欣蔚, 武晖栋, 李慧嘉.
基于复杂网络的全球航空网络结构分析与应用
Analysis and Application of Global Aviation Network Structure Based on Complex Network
计算机科学, 2021, 48(6A): 321-325. https://doi.org/10.11896/jsjkx.200900112
[12] 王学光, 张爱新, 窦炳琳.
复杂网络上的非线性负载容量模型
Non-linear Load Capacity Model of Complex Networks
计算机科学, 2021, 48(6): 282-287. https://doi.org/10.11896/jsjkx.200700040
[13] 马媛媛, 韩华, 瞿倩倩.
基于节点亲密度的重要性评估算法
Importance Evaluation Algorithm Based on Node Intimate Degree
计算机科学, 2021, 48(5): 140-146. https://doi.org/10.11896/jsjkx.200300184
[14] 殷子樵, 郭炳晖, 马双鸽, 米志龙, 孙怡帆, 郑志明.
群智体系网络结构的自治调节:从生物调控网络结构谈起
Autonomous Structural Adjustment of Crowd Intelligence Network: Begin from Structure of Biological Regulatory Network
计算机科学, 2021, 48(5): 184-189. https://doi.org/10.11896/jsjkx.210200161
[15] 刘胜久, 李天瑞, 谢鹏, 刘佳.
带权图的多重分形度量
Measure for Multi-fractals of Weighted Graphs
计算机科学, 2021, 48(3): 136-143. https://doi.org/10.11896/jsjkx.200700159
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!