Vulnerability of robust preferential attachment networks

Abstract

Scale-free networks with small power law exponent are known to be robust, meaning that their qualitative topological structure cannot be altered by random removal of even a large proportion of nodes. By contrast, it has been argued in the science literature that such networks are highly vulnerable to a targeted attack, and removing a small number of key nodes in the network will dramatically change the topological structure. Here we analyse a class of preferential attachment networks in the robust regime and prove four main results supporting this claim: After removal of an arbitrarily small proportion $\varepsilon>0$ of the oldest nodes (1) the asymptotic degree distribution has exponential instead of power law tails; (2) the largest degree in the network drops from being of the order of a power of the network size $n$ to being just logarithmic in $n$; (3) the typical distances in the network increase from order $\log\log n$ to order $\log n$; and (4) the network becomes vulnerable to random removal of nodes. Importantly, all our results explicitly quantify the dependence on the proportion $\varepsilon$ of removed vertices. For example, we show that the critical proportion of nodes that have to be retained for survival of the giant component undergoes a steep increase as $\varepsilon$ moves away from zero, and a comparison of this result with similar ones for other networks reveals the existence of two different universality classes of robust network models. The key technique in our proofs is a local approximation of the network by a branching random walk with two killing boundaries, and an understanding of the particle genealogies in this process, which enters into estimates for the spectral radius of an associated operator.