Percolation in a hierarchical random graph

2006/07/05 by Donald A. Dawson, Dawson, D. A., Luis G. Gorostiza +1
Mathematics · Physics and Astronomy · #60K35 #Complex Network Analysis Techniques #FOS: Mathematics #Opinion Dynamics and Social Influence #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.math/0607131

openalex publication_date 2006/07/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study asymptotic percolation as N→ ∞ in an infinite random graph \cal G_N embedded in the hierarchical group of order N, with connection probabilities depending on an ultrametric distance between vertices. \cal G_N is structured as a cascade of finite random subgraphs of (approximate) Erdös-Renyi type. We give a criterion for percolation, and show that percolation takes place along giant components of giant components at the previous level in the cascade of subgraphs for all consecutive hierarchical distances. The proof involves a hierarchy of random graphs with vertices having an internal structure and random connection probabilities.

Citations

• On the scaling of the chemical distance in long-range percolation models

Related

• Transience and recurrence of random walks on percolation clusters in an ultrametric space
• Percolation in an ultrametric space
• Percolation on dense random graphs with given degrees
• Clique percolation in random networks
• H-percolation with a random H