关键词: 图健壮性, 图谱, 网络弹性, 随机故障, 恶意攻击, 网络拓扑

Abstract: Random failures and targeted attacks may cause links or nodes in the network failure, which in turn can cause significant disruption to the availability of network services. Designing a network topology to provide acceptable levels of service in the face of these challenges can save both lives and money. Therefore, this paper proposes a heuristic algorithm based on iterative computing to optimize the network topology, which adds links to given graphs to improve the average efficiency function of the network and enhance network resilience. The algorithm is used in three kinds of complex networks to maximize the average efficiency of a network via adding a set of links. Then, non-improved and improved graphs are evaluated by applying random failure and centrality-based attacks to examine their resilience. The results show that compared with other optimization algorithms, the proposed heuristic algorithm yields the best network resilience against such attacks among the studied robustness metrics.

Key words: graph robustness, spectral graph theory, network resilience, random failures, targeted attacks, network topology