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

DOI10.1016/J.SPA.2018.06.006zbMATH Open1415.60120arXiv1802.01847OpenAlexW2963241967MaRDI QIDQ2000133FDOQ2000133

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)

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.

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

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

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)

Cites Work

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

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)