  It is commonly believed that scale-free networks are robust to massive
numbers of random node deletions. For example, Cohen et al. study scale-free
networks including some which approximate the measured degree distribution of
the Internet. Their results suggest that if each node in this network failed
independently with probability 0.99, the remaining network would continue to
have a giant component. In this paper, we show that a large and important
subclass of scale-free networks are not robust to massive numbers of random
node deletions for practical purposes. In particular, we study finite
scale-free networks which have minimum node degree of 1 and a power-law degree
distribution beginning with nodes of degree 1 (power-law networks). We show
that, in a power-law network approximating the Internet's reported
distribution, when the probability of deletion of each node is 0.5 only about
25% of the surviving nodes in the network remain connected in a giant
component, and the giant component does not persist beyond a critical failure
rate of 0.9. The new result is partially due to improved analytical
accommodation of the large number of degree-0 nodes that result after node
deletions. Our results apply to finite power-law networks with a wide range of
power-law exponents, including Internet-like networks. We give both analytical
and empirical evidence that such networks are not generally robust to massive
random node deletions.
