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

Mohammed Amin Abdullah, Nikolaos Fountoulakis

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
183 Downloads (Pure)

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 languageEnglish
Number of pages41
JournalRandom Structures and Algorithms
Early online date15 Dec 2017
DOIs
Publication statusE-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.

Cite this