Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (11): 3530-3539.DOI: 10.11772/j.issn.1001-9081.2023111659

• Advanced computing • Previous Articles     Next Articles

Efficient adaptive robustness optimization algorithm for complex networks

Jie HUANG1, Ruizi WU2, Junli LI1,3()   

  1. 1.College of Computer Science,Sichuan Normal University,Chengdu Sichuan 610101,China
    2.Institution of Fundamental and Frontier Sciences,University of Electronic Science and Technology of China,Chengdu Sichuan 611731,China
    3.Visual Computing and Virtual Reality Key Laboratory of Sichuan Province (Sichuan Normal University),Chengdu Sichuan 610066,China
  • Received:2023-11-29 Revised:2024-01-22 Accepted:2024-02-05 Online:2024-02-29 Published:2024-11-10
  • Contact: Junli LI
  • About author:HUANG Jie, born in 1998, M. S. candidate. Her research interests include complex networks, evolutionary algorithms, deep learning.
    WU Ruizi, born in 1998, Ph. D. candidate. His research interests include complex networks, deep learning, graph neural networks.

高效的自适应复杂网络鲁棒性优化算法

黄杰1, 武瑞梓2, 李均利1,3()   

  1. 1.四川师范大学 计算机科学学院,成都 610101
    2.电子科技大学 基础与前沿研究院,成都 611731
    3.可视化计算与虚拟现实四川省重点实验室(四川师范大学),成都 610066
  • 通讯作者: 李均利
  • 作者简介:黄杰(1998—),女,四川成都人,硕士研究生,主要研究方向:复杂网络、进化算法、深度学习
    武瑞梓(1998—),男,山东泰安人,博士研究生,主要研究方向:复杂网络、深度学习、图神经网络

Abstract:

Enhancing the robustness of complex networks is crucial for the networks to resist external attacks and cascading failures. Existing evolutionary algorithms have limitations in solving network structure optimization problems, especially in terms of convergence and optimization speed. In response to this challenge, a new adaptive complex network robustness optimization algorithm named SU-ANet (SUrrogate-assisted and Adaptive Network optimization algorithm) was proposed. To reduce the huge time overhead of robustness computation, a robustness predictor based on attention mechanism was constructed in SU-ANet as an offline surrogate model to replace the frequent robustness computation in local search operator. In the evolutionary process, the global and local information was considered comprehensively to avoid falling into local optimum and broaden the search space simultaneously. By designing crossover operators, each individual exchanges edges with the global optimum candidate solution and a randomly selected individual to balance the convergence and diversity of the algorithm. Additionally, a parameter self-adaptive mechanism was applied to adjust the operator execution probabilities automatically, thereby alleviating the uncertainty of the algorithm brought by the parameter design. Experimental results on both synthetic networks and real-world networks demonstrate that SU-ANet has better search capabilities and higher evolutionary efficiency.

Key words: complex network, evolutionary algorithm, parameter adaption, robustness, surrogate model

摘要:

提升复杂网络的鲁棒性对于网络抵御外部攻击和级联失效具有重要现实意义。现有进化算法在解决网络结构优化问题时存在局限,特别是在收敛性和优化速度方面有待提升。针对这一问题,提出一种新的自适应复杂网络鲁棒性优化算法SU-ANet (SUrrogate-assisted and Adaptive Network optimization algorithm)。为降低鲁棒性计算所带来的巨大时间开销,该算法构建了基于注意力机制的鲁棒性预测器作为离线代理模型,以代替局部搜索算子中频繁的鲁棒性计算;而在进化过程中,为避免陷入局部最优,同时拓宽解空间的搜索范围,算法全面考虑了全局和局部信息;另外,通过设计交叉算子,使每个个体与全局最优候选解和随机个体进行连边互换,以平衡算法的收敛性和多样性;此外,采用参数自适应机制自动调整算子的执行概率,以减少参数设计对算法性能带来的不确定性影响。在人工合成网络和真实网络上的实验结果表明,SU-ANet具有更好的搜索能力和更高的进化效率。

关键词: 复杂网络, 进化算法, 参数自适应, 鲁棒性, 代理模型

CLC Number: