A large deviation approach to super-critical bootstrap percolation on the random graph G_n, p

DOI10.1016/J.SPA.2018.06.006MaRDI QIDQ2000133zbMATH OpenOpenAlexFDO

Authors Giovanni Luca Torrisi, M. Garetto, Emilio Leonardi

Publication date 28 June 2019

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

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

zbMATH Keywords

large deviationsrandom graphsbootstrap percolation

Mathematics Subject Classification ID

Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We consider the Erd"{o}s--R'{e}nyi random graph $G_{n,p}$ and we analyze the simple irreversible epidemic process on the graph, known in the literature as bootstrap percolation. We give a quantitative version of some results by Janson et al. (2012), providing a fine asymptotic analysis of the final size $A_n^{\ast }$ of active nodes, under a suitable super-critical regime. More specifically, we establish large deviation principles for the sequence of random variables ${fracn-A_n^{\ast }f(n)}_{ngeq1}$ with explicit rate functions and allowing the scaling function $f$ to vary in the widest possible range.

Recommendations

• Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on \(G(n,p)\) revisited
• Bootstrap percolation on the stochastic block model
• Bootstrap percolation on a graph with random and local connections

Cites work

• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• A simple model of global cascades on random networks
• An introduction to large deviations for random graphs
• Asymptotic final-size distribution for some chain-binomial processes
• Bootstrap percolation on a graph with random and local connections
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Epidemics and rumours in complex networks.
• Majority bootstrap percolation on \(G(n,p)\)
• On the behavior of some cellular automata related to bootstrap percolation
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Some large deviation results for sparse random graphs

Cited in

(3)

• Bootstrap percolation on a graph with random and local connections
• Large deviations for subcritical bootstrap percolation on the Erdős-Rényi graph
• Bootstrap percolation on the stochastic block model

This page was built for publication: A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)

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