A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs
Research output: Contribution to journal › Article › peer-review
Colleges, School and Institutes
- Mathematical and Algorithmic Sciences Lab, Huawei Technologies Ltd.
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).
|Number of pages||41|
|Journal||Random Structures and Algorithms|
|Early online date||15 Dec 2017|
|Publication status||E-pub ahead of print - 15 Dec 2017|
- bootstrap percolation, critical phenomena, preferential attachment graphs