Bootstrap percolation and the geometry of complex networks

DOI10.1016/J.SPA.2015.08.005MaRDI QIDQ898407zbMATH OpenOpenAlexFDO

Authors Elisabetta Candellero, Nikolaos Fountoulakis

Publication date 8 December 2015

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

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

zbMATH Keywords

random geometric graphbootstrap percolationhyperbolic plane

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Percolation (82B43)

Abstract: On a geometric model for complex networks (introduced by Krioukov et al.) we investigate the bootstrap percolation process. This model consists of random geometric graphs on the hyperbolic plane having $N$ vertices, a dependent version of the Chung-Lu model. The process starts with infection rate $p=p(N)$. Each uninfected vertex with at least $mathbfrgeq1$ infected neighbors becomes infected, remaining so forever. We identify a function $p_c(N)=o(1)$ such that a.a.s. when $pgg{p}_c(N)$ the infection spreads to a positive fraction of vertices, whereas when $pll{p}_c(N)$ the process cannot evolve. Moreover, this behavior is "robust" under random deletions of edges.

Recommendations

• Bootstrap percolation on random geometric graphs (extended abstract)
• Bootstrap percolation on the random graph \(G_{n,p}\)
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Bootstrap percolation on geometric inhomogeneous random graphs
• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs

Cites work

• A Bound for the Diameter of Random Hyperbolic Graphs
• Bootstrap percolation in living neural networks
• Bootstrap percolation in power-law random graphs
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Collective dynamics of `small-world' networks
• Complex graphs and networks
• Connected components in random graphs with given expected degree sequences
• Emergence of Scaling in Random Networks
• Encores on cores
• On the largest component of a hyperbolic model of complex networks
• Random graphs and complex networks. Volume 1
• Random hyperbolic graphs: degree sequence and clustering (extended abstract)
• Remarks on bootstrap percolation in metric networks
• Statistical mechanics of complex networks
• Sudden emergence of a giant k-core in a random graph
• The average distances in random graphs with given expected degrees
• The phase transition in inhomogeneous random graphs

Cited in

(23)

• Law of large numbers for the largest component in a hyperbolic model of complex networks
• Bootstrap percolation on geometric inhomogeneous random graphs
• Scale-free percolation in continuous space: quenched degree and clustering coefficient
• Bootstrap percolation on random geometric graphs (extended abstract)
• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Cliques in hyperbolic random graphs
• Percolation of the loss of tension in an infinite triangular lattice.
• On the diameter of hyperbolic random graphs
• On the second largest component of random hyperbolic graphs
• Complex contagions on configuration model graphs with a power-law degree distribution
• Geometric inhomogeneous random graphs
• Percolation on random graphs with a fixed degree sequence
• Remarks on bootstrap percolation in metric networks
• Bootstrap percolation in random geometric graphs
• Cover and hitting times of hyperbolic random graphs
• Sub-tree counts on hyperbolic random geometric graphs
• Clustering in a hyperbolic model of complex networks
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• Sampling geometric inhomogeneous random graphs in linear time
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Penalising transmission to hubs in scale-free spatial random graphs
• Accelerated information dissemination on networks with local and global edges

This page was built for publication: Bootstrap percolation and the geometry of complex networks

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