A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs. Issue 3 (15th December 2017)

• Record Type: Journal Article
• Authors: Amin Abdullah, Mohammed; Fountoulakis, Nikolaos
• Is Part Of: Random structures & algorithms. Volume 52:Issue 3(2018)
• Page Start: 379
• Page End: 418
• Publication Date: 2017-12-15
• Subjects: bootstrap percolation -- critical phenomena -- preferential attachment graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20744
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ) .