Bootstrap percolation on geometric inhomogeneous random graphs

DOI10.4230/LIPICS.ICALP.2016.147zbMATH Open1388.68234arXiv1603.02057OpenAlexW2963695164MaRDI QIDQ4598290FDOQ4598290

Authors: Christoph Koch, Johannes Lengler 

Publication date: 19 December 2017

Abstract: Geometric inhomogeneous random graphs (GIRGs) are a model for scale-free networks with underlying geometry. We study bootstrap percolation on these graphs, which is a process modelling the spread of an infection of vertices starting within a (small) local region. We show that the process exhibits a phase transition in terms of the initial infection rate in this region. We determine the speed of the process in the supercritical case, up to lower order terms, and show that its evolution is fundamentally influenced by the underlying geometry. For vertices with given position and expected degree, we determine the infection time up to lower order terms. Finally, we show how this knowledge can be used to contain the infection locally by removing relatively few edges from the graph. This is the first time that the role of geometry on bootstrap percolation is analysed mathematically for geometric scale-free networks.

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

Recommendations

• Bootstrap percolation and the geometry of complex networks
• Bootstrap percolation in directed inhomogeneous random graphs
• Bootstrap percolation on random geometric graphs (extended abstract)
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Bootstrap percolation in power-law random graphs

zbMATH Keywords

bootstrap percolationscale-free networkgeometric inhomogeneous random graphslocalised infection processmetastability threshold

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10)

Cited In (27)

• Scale-free percolation mixing time
• Cliques in high-dimensional geometric inhomogeneous random graphs
• Bootstrap percolation on random geometric graphs (extended abstract)
• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• Majority rule cellular automata
• BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
• Bootstrap percolation and the geometry of complex networks
• Bootstrap percolation in directed inhomogeneous random graphs
• On the second largest component of random hyperbolic graphs
• Spectral gap of random hyperbolic graphs and related parameters
• Geometric inhomogeneous random graphs
• Bootstrap percolation on the product of the two-dimensional lattice with a Hamming square
• Bootstrap percolation in random geometric graphs
• Remarks on bootstrap percolation in metric networks
• Cover and hitting times of hyperbolic random graphs
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Bootstrap Percolation on Degenerate Graphs
• Color War: Cellular Automata with Majority-Rule
• Polluted bootstrap percolation with threshold two in all dimensions
• Sampling geometric inhomogeneous random graphs in linear time
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• Greedy routing and the algorithmic small-world phenomenon
• Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs
• Bootstrap percolation on the random regular graph
• Penalising transmission to hubs in scale-free spatial random graphs
• Greed is good for deterministic scale-free networks
• Accelerated information dissemination on networks with local and global edges

This page was built for publication: Bootstrap percolation on geometric inhomogeneous random graphs

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