Bootstrap percolation on geometric inhomogeneous random graphs

DOI10.4230/LIPICS.ICALP.2016.147MaRDI QIDQ4598290zbMATH OpenOpenAlexFDO

Authors Christoph Koch, Johannes Lengler

Publication date 19 December 2017

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

zbMATH Keywords

bootstrap percolationgeometric inhomogeneous random graphslocalised infection processmetastability thresholdscale-free network

Mathematics Subject Classification ID

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

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.

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

Cited in

(28)

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

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)