13 - Optimization of the network structure

Summary

In this chapter we present results for the robustness of complex networks under multiple waves of simultaneous targeted attacks in which the highest degree nodes are removed and random attacks (or failures), in which fractions p_t and p_r, respectively, of the nodes are removed until the network collapses [TPC⁺05]. It is shown that the network design, which optimizes network robustness, has a bimodal degree distribution, with a fraction r of the nodes having degree k₂ = (
k‪ − 1 + r)/r and the remainder of the nodes having degree k₁ = 1, where 
k‪ is the average degree of all the nodes. The optimal value of r approaches p_t/p_r for p_t/p_r ≪ 1.

Introduction

The resilience of real-world networks to random attacks or to attacks targeted at the highest degree nodes is of much interest [AJB00, CEbH00, CEbH01, CNSW00, Pax97, PSS05, VSS04]. Many real-world networks are robust to random attacks but vulnerable to targeted attacks on the most important nodes. It is important to understand how to design networks that are optimally robust against both types of attacks, with examples being terrorist attacks on physical networks and attacks by hackers on computer networks. In Chapter 10 we considered the case in which there was only one type of attack on a given network, that is, the network was subject to either a random attack or to a targeted attack but not subject to different types of attack simultaneously, which is a more realistic scenario.