Percolation on preferential attachment models

Electronic Journal of Probability, vol. 31, pp. 1–30

Abstract

We study the percolation phase transition on preferential attachment models, in which vertices enter with m edges and attach proportionally to their degree plus δ. We identify the critical percolation threshold as πc=δ 2(m(m+δ)+ m(m−1)(m+δ)(m+1+δ)) for δ positive and πc=0 for non-positive values of δ. Therefore the giant component is robust for δ∈(−m,0], while it is not for δ>0. Our proof for the critical percolation threshold consists of three main steps. First, we show that preferential attachment graphs are large-set expanders, enabling us to verify the conditions outlined by Alimohammadi, Borgs, and Saberi (2023). Within their conditions, the proportion of vertices in the largest connected component in a sequence converges to the survival probability of percolation on the local limit. In particular, the critical percolation threshold for both the graph and its local limit are identical. Second, we identify 1∕πc as the spectral norm of the mean offspring operator of the Pólya point tree, the local limit of preferential attachment models. Lastly, we prove that the critical percolation threshold for the Pólya point tree is the inverse of the spectral norm of the mean offspring operator. For positive δ, we use super-martingales to prove sub-criticality and apply spine decomposition theory to demonstrate super-criticality, completing the third step of the proof. For δ≤0 and any π>0 instead, we prove that the percolated Pólya point tree dominates a supercritical branching process, proving that the critical percolation threshold equals 0.

Authors 3

1. Rajat Subhra Hazra Aachen

   Leiden University

   Affiliation as printed

   University of Leiden

2. Remco van der Hofstad

   Eindhoven University of Technology

   Affiliation as printed

   Eindhoven University of Technology, The Netherlands

3. Rounak Ray

   Brown University

   Affiliation as printed

   Brown University