Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering ›› 2021, Vol. 47 ›› Issue (8): 84-92. doi: 10.19678/j.issn.1000-3428.0058410

• Artificial Intelligence and Pattern Recognition • Previous Articles     Next Articles

Robustness Optimization Strategy Based on Community Structure for Complex Network

LIU Diyang1, ZHANG Zhen1, ZHANG Jin2   

  1. 1. Institute of Information Technology, PLA Strategic Support Force Information Engineering University, Zhengzhou 450000, China;
    2. Network Communication and Security Purple Mountain Laboratory, Nanjing 210000, China
  • Received:2020-05-25 Revised:2020-07-17 Published:2020-07-24

基于社区结构的复杂网络鲁棒性优化策略

刘迪洋1, 张震1, 张进2   

  1. 1. 解放军战略支援部队信息工程大学 信息技术研究所, 郑州 450000;
    2. 网络通信与安全紫金山实验室, 南京 210000
  • 作者简介:刘迪洋(1995-),男,硕士研究生,主研方向为复杂网络优化;张震,讲师、博士;张进,工程师、博士。
  • 基金资助:
    国家自然科学基金(61802429,61872382,61521003);国家重点研发计划(2017YFB0803201,2017YFB0803204)。

Abstract: To reduce the changes to the initial community structure of the networks during complex network robustness optimization, the influence of the edge rewiring strategy on network community structure is analyzed, and a robustness optimization strategy based on community structure for complex network is proposed. The strategy employs the Louvain algorithm to determine the complex network community structure, and uses the Simulated Annealing(SA) algorithm to improve the internal robustness of each community in the complex network. Then an improved Smart Rewiring strategy is used to enhance the robustness of connections between communities. On this basis, the Normalized Mutual Information(NMI) indicator is used to evaluate how much the community structure is retained during robustness optimization. Experimental results on BA, WS and WU-PowerGrid networks show that compared with Smart Rewiring strategy and MA strategy, the proposed strategy can improve the network robustness while retaining the initial community structure of the network as much as possible.

Key words: complex network, community structure, robustness optimization, Simulated Annealing(SA) algorithm, Normalized Mutual Information(NMI)

摘要: 为在复杂网络鲁棒性优化过程中尽可能保留网络初始社区结构,分析重连边策略对网络社区结构的影响,提出一种结合社区结构的复杂网络鲁棒性优化策略。采用Louvain算法确定复杂网络社区结构,利用模拟退火算法提升复杂网络中单个社区的内部鲁棒性,使用改进的智能重连边策略(Smart Rewiring)提升社区间的连接鲁棒性,并通过标准化互信息指标评价鲁棒性优化过程中社区结构的保留程度。在BA、WS和WU-PowerGrid网络中的实验结果表明,与Smart Rewiring和MA策略相比,该策略能在提升网络鲁棒性的同时尽可能保留网络初始社区结构。

关键词: 复杂网络, 社区结构, 鲁棒性优化, 模拟退火算法, 标准互信息

CLC Number: