Distances in random graphs with finite variance degrees

Journal article (2005)

Authors

RW van Hofstad Old - EWI Ch. Applied Probability<2004
G. Hooghiemstra Applied Probability - EEMCS
P.F.A. Van Mieghem Network Architectures and Services - EEMCS
Research Group
Old - EWI Ch. Applied Probability<2004
More Info
expand_more

Published Date

2005

Language

Undefined/Unknown

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Research Group

Old - EWI Ch. Applied Probability<2004

Abstract

In this paper we study a random graph with N nodes, where node j has degree Dj and {Dj} are i.i.d. with (Dj x) = F(x). We assume that 1 - F(x) cx-+1 for some > 3 and some constant c > 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 when N . 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 N are 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