2015/04/02 by Emmanuel Jacob, Jacob, Emmanuel, Peter Morters +1 · 1 citation
Mathematics · #82B43 #90B15 #FOS: Mathematics #Primary 05C80 #Probability (math.PR) #math.PR #msc:05C80 #msc:60C05 #msc:82B43 #msc:90B15 #secondary 60C05
paper · pdf · doi:10.48550/arxiv.1504.00618
34 pages, 4 figures
arxiv created 2015/04/06 · arxiv updated 2015/04/08
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 τ of the degree distribution and the rate δd at which the connection probability decreases with the distance of two vertices. We show that the network is robust if τ<2+1/δ, but fails to be robust if τ>3. In the case of one-dimensional space we also show that the network is not robust if τ<2+1/(δ-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.