Bootstrap percolation in inhomogeneous random graphs

DOI10.1017/APR.2023.21MaRDI QIDQ6119933zbMATH OpenOpenAlexFDO

Authors Hamed Amini, Nikolaos Fountoulakis, Konstantinos Panagiotou

Publication date 20 February 2024

Published in Advances in Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

bootstrap percolationrandom graphssharp threshold

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: A bootstrap percolation process on a graph G is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round every uninfected node which has at least r infected neighbours becomes infected and remains so forever. The parameter r > 1 is fixed. We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank 1. Assuming that initially every vertex is infected independently with probability p > 0, we provide a law of large numbers for the number of vertices that will have been infected by the end of the process. We also focus on a special case of such random graphs which exhibit a power-law degree distribution with exponent in (2,3). The first two authors have shown the existence of a critical function a_c(n) such that a_c(n)=o(n) with the following property. Let n be the number of vertices of the underlying random graph and let a(n) be the number of the vertices that are initially infected. Assume that a set of a(n) vertices is chosen randomly and becomes externally infected. If a(n) << a_c(n), then the process does not evolve at all, with high probability as n grows, whereas if a(n)>> a_c(n), then with high probability the final set of infected vertices is linear. Using the techniques of the previous theorem, we give the precise asymptotic fraction of vertices which will be eventually infected when a(n) >> a_c (n) but a(n) = o(n). Note that this corresponds to the case where p approaches 0.

Recommendations

• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• Bootstrap percolation in power-law random graphs
• Discontinuous bootstrap percolation in power-law random graphs
• Bootstrap percolation in directed inhomogeneous random graphs
• Bootstrap percolation on \(G(n,p)\) revisited

Cites work

• A Brief History of Generative Models for Power Law and Lognormal Distributions
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Bootstrap percolation and kinetically constrained models on hyperbolic lattices
• Bootstrap percolation in directed inhomogeneous random graphs
• Bootstrap percolation in living neural networks
• Bootstrap percolation in power-law random graphs
• Bootstrap percolation in three dimensions
• Bootstrap percolation on homogeneous trees has 2 phase transitions
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the hypercube
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• Connected components in random graphs with given expected degree sequences
• Differential equations for random processes and random graphs
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• scientific article; zbMATH DE number 3410334 (Why is no real title available?)
• Inhomogeneous financial networks and contagious links
• Managing Default Contagion in Inhomogeneous Financial Networks
• Remarks on bootstrap percolation in metric networks
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Statistical mechanics of complex networks
• Stretched exponential fixation in stochastic Ising models at zero temperature
• The Average Distance in a Random Graph with Given Expected Degrees
• The phase transition in inhomogeneous random graphs
• The sharp threshold for bootstrap percolation in all dimensions
• The Spectra of Random Graphs with Given Expected Degrees
• The threshold regime of finite volume bootstrap percolation.
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)

Cited in

(2)

• Central limit theorems for price-mediated contagion in stochastic financial networks
• Fire sales, default cascades and complex financial networks

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

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