Bootstrap Percolation on a Graph with Random and Local Connections
(2015) In Journal of Statistical Physics 160(5). p.12491276 Abstract
 Let be a superposition of the random graph and a onedimensional 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 onedimensional 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:
http://lup.lub.lu.se/record/7975814
 author
 Turova, Tatyana ^{LU} and Vallier, Thomas
 organization
 publishing date
 2015
 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
 15729613
 DOI
 10.1007/s109550151294x
 language
 English
 LU publication?
 yes
 id
 8ce564633f2845eab94e9abeefbbfb99 (old id 7975814)
 date added to LUP
 20150924 17:16:02
 date last changed
 20170409 03:48:10
@article{8ce564633f2845eab94e9abeefbbfb99, abstract = {Let be a superposition of the random graph and a onedimensional 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 = {15729613}, keyword = {Bootstrap percolation,Random graph,Phase transition}, language = {eng}, number = {5}, pages = {12491276}, 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/s109550151294x}, volume = {160}, year = {2015}, }