A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs

DOI10.1214/17-AAP1324MaRDI QIDQ1650096zbMATH OpenOpenAlexWikidataFDO

Authors Nikolaos Fountoulakis, Mihyun Kang, Christoph Koch, Tamás Makai

Publication date 29 June 2018

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

Full work available at URL https://arxiv.org/abs/1609.08892, https://projecteuclid.org/euclid.aoap/1523433630

zbMATH Keywords

bootstrap percolationcritical phenomenainhomogeneous random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Processes in random environments (60K37) Phase transitions (general) in equilibrium statistical mechanics (82B26) Critical phenomena in equilibrium statistical mechanics (82B27)

Abstract: A bootstrap percolation process on a graph with infection threshold $rge1$ is a dissemination process that evolves in time steps. The process begins with a subset of infected vertices and in each subsequent step every uninfected vertex that has at least $r$ infected neighbours becomes infected and remains so forever. Critical phenomena in bootstrap percolation processes were originally observed by Aizenman and Lebowitz in the late 1980s as finite-volume phase transitions in $mathbb{Z}^d$ that are caused by the accumulation of small local islands of infected vertices. They were also observed in the case of dense (homogeneous) random graphs by Janson, L uczak, Turova and Valier (2012). In this paper, we consider the class of inhomogeneous random graphs known as the Chung-Lu model: each vertex is equipped with a positive weight and each pair of vertices appears as an edge with probability proportional to the product of the weights. In particular, we focus on the sparse regime, where the number of edges is proportional to the number of vertices. The main results of this paper determine those weight sequences for which a critical phenomenon occurs: there is a critical density of vertices that are infected at the beginning of the process, above which a small (sublinear) set of infected vertices creates an avalanche of infections that in turn leads to an outbreak. We show that this occurs essentially only when the tail of the weight distribution dominates a power law with exponent 3 and we determine the critical density in this case.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 6303024 (Why is no real title available?)
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Bootstrap percolation and kinetically constrained models on hyperbolic lattices
• Bootstrap percolation and the geometry of complex networks
• Bootstrap percolation in living neural networks
• Bootstrap percolation in power-law random graphs
• Bootstrap percolation in three dimensions
• Bootstrap percolation on Galton-Watson trees
• Bootstrap percolation on geometric inhomogeneous random graphs
• Bootstrap percolation on homogeneous trees has 2 phase transitions
• 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
• Metastability effects in bootstrap percolation
• Normalization phenomena in asynchronous networks
• On the behavior of some cellular automata related to bootstrap percolation
• Probability with Martingales
• Proof of Straley's argument for bootstrap percolation.
• Random disease on the square grid
• Remarks on bootstrap percolation in metric networks
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Stretched exponential fixation in stochastic Ising models at zero temperature
• Sudden emergence of a giant k-core in a random graph
• The Average Distance in a Random Graph with Given Expected Degrees
• The Spectra of Random Graphs with Given Expected Degrees
• The phase transition in inhomogeneous random graphs
• The sharp threshold for bootstrap percolation in all dimensions
• The threshold regime of finite volume bootstrap percolation.
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)

Cited in

(9)

• Bootstrap percolation on homogeneous trees has 2 phase transitions
• Bootstrap percolation in directed inhomogeneous random graphs
• A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
• Bootstrap percolation on the stochastic block model
• Bootstrap percolation in random geometric graphs
• Think globally, act locally: on the optimal seeding for nonsubmodular influence maximization
• A central limit theorem for diffusion in sparse random graphs
• Bootstrap percolation in power-law random graphs
• Bootstrap percolation in inhomogeneous random graphs

This page was built for publication: A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs

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