A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs. Issue 3 (15th December 2017) - Amin Abdullah, Mohammed; Fountoulakis, Nikolaos
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 ≥ 2 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 2 m 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 → ∞, 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 ) .