14 Citations (SciVal)
136 Downloads (Pure)

Abstract

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+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+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.
Original languageEnglish
Pages (from-to)1680-1722
Number of pages35
JournalAnnals of Probability
Volume45
Issue number3
Early online date15 May 2017
DOIs
Publication statusPublished - 31 May 2017

Fingerprint

Dive into the research topics of 'Robustness of scale-free spatial networks'. Together they form a unique fingerprint.

Cite this