Enhancing network robustness against targeted and random attacks using a memetic algorithm

¹ Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, Xidian University Xi'an 710071 China

^(a) neouma@mail.xidian.edu.cn
neouma@163.com (corresponding author)

Received: 10 February 2015
Accepted: 23 July 2015

Abstract

In the past decades, there has been much interest in the elasticity of infrastructures to targeted and random attacks. In the recent work by Schneider C. M. et al., Proc. Natl. Acad. Sci. U.S.A., 108 (2011) 3838, the authors proposed an effective measure (namely R, here we label it as R_t to represent the measure for targeted attacks) to evaluate network robustness against targeted node attacks. Using a greedy algorithm, they found that the optimal structure is an onion-like one. However, real systems are often under threats of both targeted attacks and random failures. So, enhancing networks robustness against both targeted and random attacks is of great importance. In this paper, we first design a random-robustness index . We find that the onion-like networks destroyed the original strong ability of BA networks in resisting random attacks. Moreover, the structure of an R_r-optimized network is found to be different from that of an onion-like network. To design robust scale-free networks (RSF) which are resistant to both targeted and random attacks (TRA) without changing the degree distribution, a memetic algorithm (MA) is proposed, labeled as . In the experiments, both synthetic scale-free networks and real-world networks are used to validate the performance of . The results show that has a great ability in searching for the most robust network structure that is resistant to both targeted and random attacks.