Resilience of the Internet to Random Breakdowns

Abstract

A common property of many large networks, including the Internet, is that the connectivity of the various nodes follows a scale-free power-law distribution, $P(k){\phantom{\rule{0ex}{0ex}}=\phantom{\rule{0ex}{0ex}}ck}^{\ensuremath{-}\ensuremath{\alpha}}$. We study the stability of such networks with respect to crashes, such as random removal of sites. Our approach, based on percolation theory, leads to a general condition for the critical fraction of nodes, ${p}_{c}$, that needs to be removed before the network disintegrates. We show analytically and numerically that for $\ensuremath{\alpha}\ensuremath{\le}3$ the transition never takes place, unless the network is finite. In the special case of the physical structure of the Internet $(\ensuremath{\alpha}\ensuremath{\approx}2.5)$, we find that it is impressively robust, with ${p}_{c}>0.99$.