Bootstrap percolation with inhibition

DOI10.1002/RSA.20854MaRDI QIDQ5216182zbMATH OpenOpenAlexWikidataFDO

Authors Hafsteinn Einarsson, Johannes Lengler, Frank Mousset, Angelika Steger, Konstantinos Panagiotou

Publication date 14 February 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

bootstrap percolationinput normalizationrandom graphs

Mathematics Subject Classification ID

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

Abstract: Bootstrap percolation is a prominent framework for studying the spreading of activity on a graph. We begin with an initial set of active vertices. The process then proceeds in rounds, and further vertices become active as soon as they have a certain number of active neighbors. A recurring feature in bootstrap percolation theory is an `all-or-nothing' phenomenon: either the size of the starting set is so small that the process stops very soon, or it percolates (almost) completely. Motivated by several important phenomena observed in various types of real-world networks we propose in this work a variant of bootstrap percolation that exhibits a vastly different behavior. Our graphs have two types of vertices: some of them obstruct the diffusion, while the others facilitate it. We study the effect of this setting by analyzing the process on ErdH{o}s-R'enyi random graphs. Our main findings are two-fold. First we show that the presence of vertices hindering the diffusion does not result in a stable behavior: tiny changes in the size of the starting set can dramatically influence the size of the final active set. In particular, the process is non-monotone: a larger starting set can result in a smaller final set. In the second part of the paper we show that this phenomenom arises from the round-based approach: if we move to a continuous time model in which every edge draws its transmission time randomly, then we gain stability, and the process stops with an active set that contains a non-trivial constant fraction of all vertices. Moreover, we show that in the continuous time model percolation occurs significantly faster compared to the classical round-based model. Our findings are in line with empirical observations and demonstrate the importance of introducing various types of vertex behaviors in the mathematical model.

Recommendations

• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation and diffusion in random graphs with given vertex degrees
• Normalization phenomena in asynchronous networks
• Bootstrap percolation in directed inhomogeneous random graphs
• Bootstrap percolation on \(G(n,p)\) revisited

Cites work

• Bootstrap percolation in a polluted environment
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Bootstrap percolation on the random regular graph
• Contagious sets in random graphs
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1782874 (Why is no real title available?)
• Metastability effects in bootstrap percolation
• Normalization phenomena in asynchronous networks
• On the behavior of some cellular automata related to bootstrap percolation
• On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms
• Some Approximations to the Binomial Distribution Function
• The sharp threshold for bootstrap percolation in all dimensions

Cited in

(3)

• Normalization phenomena in asynchronous networks
• Bootstrap percolation in living neural networks
• Bootstrap percolation in random geometric graphs

This page was built for publication: Bootstrap percolation with inhibition

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