Bootstrap percolation and diffusion in random graphs with given vertex degrees
type: Item
instance of: scholarly article
title: Bootstrap percolation and diffusion in random graphs with given vertex degrees
zbMATH Open document ID: 1215.05152
author: Hamed Amini
published in: The Electronic Journal of Combinatorics
publication date: 2010-03-26T00:00:00Z
full work available at URL: https://eudml.org/doc/231997
full work available at URL: v17i1r25.html
review text: Summary: We consider diffusion in random graphs with given vertex degrees. Our diffusion model can be viewed as a variant of a cellular automaton growth process: assume that each node can be in one of the two possible states, inactive or active. The parameters of the model are two given functions \(\theta: \mathbb{N}\to\mathbb{N}\) and \(\alpha: \mathbb{N}\to[0, 1]\). At the beginning of the process., each node \(v\) of degree \(d\), becomes active with probability \(\alpha(d_v)\) independently of the other vertices. Presence of the active vertices triggers a percolation process: if a node \(v\) is active, it remains active forever. And if it is inactive, it will become active when at least \(\theta(d_v)\) of its neighbors are active. In the case where \(\alpha(d)=\alpha\) and \(\theta(d)= 0\), for each \(d\in\mathbb{N}\), our diffusion model is equivalent to what is called bootstrap percolation. The main result of this paper is a theorem which enables us to find the final proportion of the active vertices in the asymptotic case, i.e., when \(n\to\infty\). This is done via analysis of the process on the multigraph counterpart of the graph model.
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 5687007
MaRDI profile type: Publication
Recommended article: Bootstrap Percolation on Degenerate Graphs
Recommended article: Bootstrap percolation in power-law random graphs
Recommended article: Bootstrap percolation on the random graph \(G_{n,p}\)
Recommended article: Bootstrap percolation on the random regular graph
Recommended article: Bootstrap percolation in directed inhomogeneous random graphs
Recommended article: Bootstrap percolation on a graph with random and local connections
Recommended article: Bootstrap percolation in random \(k\)-uniform hypergraphs
Recommended article: Bootstrap percolation on geometric inhomogeneous random graphs
Recommended article: On percolation in random graphs with given vertex degrees
Recommended article: BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
description: scientific article