Distances in random graphs with finite variance degrees

Publisher Website
Google Scholar
Abstract
In this paper we study a random graph withNnodes, where nodejhas degreeDjand {Dj}are i.i.d. with ℙ(Dj≤x) =F(x). We assume that 1 −F(x) ≤cx−τ+1for some τ > 3 and some constantc> 0. This graph model is a variant of the so‐called configuration model, and includes heavy tail degrees with finite variance. The minimal number of edges between two arbitrary connected nodes, also known as the graph distance or the hopcount, is investigated whenN→ ∞. We prove that the graph distance grows like logνN, when the base of the logarithm equals ν = 𝔼[Dj(Dj− 1)]/𝔼[Dj] > 1. This confirms the heuristic argument of Newman, Strogatz, and Watts [Phys Rev E 64 (2002), 026118, 1–17]. In addition, the random fluctuations around this asymptotic mean logνNare characterized and shown to be uniformly bounded. In particular, we show convergence in distribution of the centered graph distance along exponentially growing subsequences. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005

This publication has 29 references indexed in Scilit: