2011/02/28 by Steffen Dereich, Christian Mönch, Dereich, Steffen +3
Mathematics · Physics and Astronomy · #90B15 #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Primary 05C80 #Probability (math.PR) #Secondary 60C05 #Stochastic processes and statistical mechanics #math.CO #math.PR #msc:05C80 #msc:60C05 #msc:90B15
paper · pdf · doi:10.48550/arxiv.1102.5680
16 pages
arxiv created 2011/02/28 · openalex publication_date 2011/02/28 · arxiv updated 2011/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that in preferential attachment models with power-law exponent τ∈(2,3) the distance between randomly chosen vertices in the giant component is asymptotically equal to (4+o(1)) (loglog N)/(-log (τ-2)), where N denotes the number of nodes. This is twice the value obtained for several types of configuration models with the same power-law exponent. The extra factor reveals the different structure of typical shortest paths in preferential attachment graphs.