Robustness of scale-free spatial networks

DOI10.1214/16-AOP1098zbMATH Open1367.05194arXiv1504.00618OpenAlexW2963048821MaRDI QIDQ2012248FDOQ2012248

Authors: Emmanuel Jacob, Peter Mörters 

Publication date: 28 July 2017

Published in: The Annals of Probability (Search for Journal in Brave)

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 $au$ of the degree distribution and the rate $deltad$ at which the connection probability decreases with the distance of two vertices. We show that the network is robust if $au<2+1/delta$, but fails to be robust if $au>3$. In the case of one-dimensional space we also show that the network is not robust if $au<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.

Full work available at URL: https://arxiv.org/abs/1504.00618

Recommendations

• Robustness of spatial preferential attachment networks
• Percolation phase transition in weight-dependent random connection models
• Vulnerability of robust preferential attachment networks
• A spatial preferential attachment model with local clustering
• Scale-free percolation in continuous space: quenched degree and clustering coefficient

zbMATH Keywords

clusteringphase transitionrobustnesscontinuum percolationpreferential attachmentscale-free networkspatial networkgiant componentpower-lawgeometric random graphBK-inequalitydisjoint occurrenceBarabási-Albert model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05) Structural characterization of families of graphs (05C75) Stochastic network models in operations research (90B15)

Cited In (20)

• Robustness of spatial preferential attachment networks
• Scale-free percolation in continuous space: quenched degree and clustering coefficient
• Distance evolutions in growing preferential attachment graphs
• Tomography and stability of complex networks
• The age-dependent random connection model
• Inhomogeneous long-range percolation in the weak decay regime
• Distances and large deviations in the spatial preferential attachment model
• Percolation phase transition in weight-dependent random connection models
• Bypass rewiring and extreme robustness of Eulerian networks
• Vulnerability of robust preferential attachment networks
• Chemical distance in geometric random graphs with long edges and scale-free degree distribution
• Assortativity and Bidegree Distributions on Bernoulli Random Graph Superpositions
• Transience versus recurrence for scale-free spatial networks
• Assortativity and bidegree distributions on Bernoulli random graph superpositions
• Rumors spread slowly in a small-world spatial network
• Spatial Gibbs random graphs
• The effect of avoiding known infected neighbors on the persistence of a recurring infection process
• Robustness of networks with assortative dependence groups
• The contact process with dynamic edges on \(\mathbb{Z}\)
• Clustering and percolation on superpositions of Bernoulli random graphs

This page was built for publication: Robustness of scale-free spatial networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012248)