Projects per year
Abstract
The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least r > 1 infected neighbours becomes infected and remains so forever.
Assume that initially a(t) vertices are randomly infected, where t is the total number of vertices of the graph. Suppose also that r < m, where 2m is the average degree. We determine a critical function a_c(t) such that when
a(t) >> a_c(t), complete infection occurs with high probability as t goes to infinity, but when a(t) << a_c (t), then with high probability the process evolves only for a bounded number of rounds and the final set of infected vertices is asymptotically equal to a(t).
Original language | English |
---|---|
Number of pages | 41 |
Journal | Random Structures and Algorithms |
Early online date | 15 Dec 2017 |
DOIs | |
Publication status | E-pub ahead of print - 15 Dec 2017 |
Keywords
- bootstrap percolation
- critical phenomena
- preferential attachment graphs
Fingerprint
Dive into the research topics of 'A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Inhomogeneity and generalised bootstrap percolation in stochastic networks
Engineering & Physical Science Research Council
1/09/13 → 31/08/15
Project: Research Councils