Robustness of scale-free spatial networks. (English) Zbl 1367.05194
Summary: A growing family of random graphs is called robust if it retains a giant component after percolation with arbitrary positive retention probability. We study robustness for graphs, in which new vertices are given a spatial position on the \(d\)-dimensional torus and are connected to existing vertices with a probability favouring short spatial distances and high degrees. In this model of a scale-free network with clustering, we can independently tune the power law exponent \(\tau\) of the degree distribution and the rate \(-\delta d\) at which the connection probability decreases with the distance of two vertices. We show that the network is robust if \(\tau<2+\frac{1}{\delta}\), but fails to be robust if \(\tau>3\). In the case of one-dimensional space, we also show that the network is not robust if \(\tau>2+\frac{1}{\delta-1}\). This implies that robustness of a scale-free network depends not only on its power-law exponent but also on its clustering features. Other than the classical models of scale-free networks, our model is not locally tree-like, and hence we need to develop novel methods for its study, including, for example, a surprising application of the BK-inequality.
MSC:
05C80 | Random graphs (graph-theoretic aspects) |
05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
05C75 | Structural characterization of families of graphs |
60C05 | Combinatorial probability |
90B15 | Stochastic network models in operations research |