Advanced

Bootstrap Percolation on a Graph with Random and Local Connections

Turova, Tatyana LU and Vallier, Thomas (2015) In Journal of Statistical Physics 160(5). p.1249-1276
Abstract
Let be a superposition of the random graph and a one-dimensional lattice: the n vertices are set to be on a ring with fixed edges between the consecutive vertices, and with random independent edges given with probability p between any pair of vertices. Bootstrap percolation on a random graph is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least active neighbours become active as well. We study the size of the final active set in the limit when . The parameters of the model are n, the size of the initially active set and the probability of the edges in the graph. The bootstrap percolation process on... (More)
Let be a superposition of the random graph and a one-dimensional lattice: the n vertices are set to be on a ring with fixed edges between the consecutive vertices, and with random independent edges given with probability p between any pair of vertices. Bootstrap percolation on a random graph is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least active neighbours become active as well. We study the size of the final active set in the limit when . The parameters of the model are n, the size of the initially active set and the probability of the edges in the graph. The bootstrap percolation process on was studied earlier. Here we show that the addition of n local connections to the graph leads to a more narrow critical window for the phase transition, preserving however, the critical scaling of parameters known for the model on . We discover a range of parameters which yields percolation on but not on G(n,p). (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Bootstrap percolation, Random graph, Phase transition
in
Journal of Statistical Physics
volume
160
issue
5
pages
1249 - 1276
publisher
Springer
external identifiers
  • wos:000358744100007
  • scopus:84938416521
ISSN
1572-9613
DOI
10.1007/s10955-015-1294-x
language
English
LU publication?
yes
id
8ce56463-3f28-45ea-b94e-9abeefbbfb99 (old id 7975814)
date added to LUP
2015-09-24 17:16:02
date last changed
2017-04-09 03:48:10
@article{8ce56463-3f28-45ea-b94e-9abeefbbfb99,
  abstract     = {Let be a superposition of the random graph and a one-dimensional lattice: the n vertices are set to be on a ring with fixed edges between the consecutive vertices, and with random independent edges given with probability p between any pair of vertices. Bootstrap percolation on a random graph is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least active neighbours become active as well. We study the size of the final active set in the limit when . The parameters of the model are n, the size of the initially active set and the probability of the edges in the graph. The bootstrap percolation process on was studied earlier. Here we show that the addition of n local connections to the graph leads to a more narrow critical window for the phase transition, preserving however, the critical scaling of parameters known for the model on . We discover a range of parameters which yields percolation on but not on G(n,p).},
  author       = {Turova, Tatyana and Vallier, Thomas},
  issn         = {1572-9613},
  keyword      = {Bootstrap percolation,Random graph,Phase transition},
  language     = {eng},
  number       = {5},
  pages        = {1249--1276},
  publisher    = {Springer},
  series       = {Journal of Statistical Physics},
  title        = {Bootstrap Percolation on a Graph with Random and Local Connections},
  url          = {http://dx.doi.org/10.1007/s10955-015-1294-x},
  volume       = {160},
  year         = {2015},
}