计算机科学 ›› 2021, Vol. 48 ›› Issue (7): 130-136.doi: 10.11896/jsjkx.201000108
穆俊芳1,2, 郑文萍1,2, 王杰3, 梁吉业1,2
MU Jun-fang1,2, ZHENG Wen-ping1,2, WANG Jie3, LIANG Ji-ye1,2
摘要: 随着电力系统、交通系统、通信系统等基础设施网络的广泛使用,提高复杂网络的鲁棒性具有重要意义。重连机制是一种高效且简洁的方法,常用于提高网络的鲁棒性。基于0阶零模型的重连机制通过对边的随机删除和创建操作来提高网络的鲁棒性,其尽管保持了网络的边数,但会引起节点的度值发生变化,如基于香农熵的重连算法;基于1阶零模型的重连机制通过随机选择两条边进行换边操作来提高网络的鲁棒性,其尽管保持了网络的度分布,但随机选边难以准确找到合适的节点,增加了算法的时间成本,如基于最大连通分支的重连算法。因此,为了保持网络的度分布且快速提高网络的鲁棒性,提出了一种基于1阶零模型的快速重连算法(Fast Rewiring Mechanism based on 1-order Null Model,FRM)。FRM算法通过比较每条边的两个端点度值的差异为边加权,根据边的权重优先选择权重较大的两条边,并创建度值相似节点之间的连边来提高网络的鲁棒性。在3个真实网络数据上与4种代表性重连算法相比,对比实验结果表明,FRM算法在度中心性、介数中心性和Page-Rank中心性攻击下最大连通分支中的节点比例s(Q)、基于最大连通分支的鲁棒性指标R和基于香农熵的鲁棒性指标I(G)的表现都更好。
中图分类号:
[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 |
|