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

DOI10.1002/RSA.20744MaRDI QIDQ4642741zbMATH OpenOpenAlexFDO

Authors Nikolaos Fountoulakis, Mohammed Abdullah

Publication date 25 May 2018

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.4070, http://pure-oai.bham.ac.uk/ws/files/39723499/PrefPercFinal.pdf

zbMATH Keywords

bootstrap percolationcritical phenomenapreferential attachment graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

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 $rgeq2$ 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)gg{a}_c(t)$, complete infection occurs with high probability as $tightarrowinfty$, but when $a(t)ll{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)$.

Recommendations

• Bootstrap percolation in power-law random graphs
• Bootstrap percolation on \(G(n,p)\) revisited
• Spread of infection over P.A. random graphs with edge insertion
• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• Bootstrap percolation on the random graph \(G_{n,p}\)

Cited in

(8)

• A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
• Accelerated information dissemination on networks with local and global edges
• Bootstrap percolation on the stochastic block model
• Distance evolutions in growing preferential attachment graphs
• Bootstrap percolation in power-law random graphs
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• Spread of infection over P.A. random graphs with edge insertion
• Bootstrap percolation and the geometry of complex networks

This page was built for publication: A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4642741)