A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • Mathematical and Algorithmic Sciences Lab, Huawei Technologies Ltd.

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

Details

Original languageEnglish
Number of pages41
JournalRandom Structures and Algorithms
Early online date15 Dec 2017
Publication statusE-pub ahead of print - 15 Dec 2017

Keywords

  • bootstrap percolation, critical phenomena, preferential attachment graphs