The Average Distance in a Random Graph with Given Expected Degrees

TLDR

Random graph theory studies the small‑world phenomenon, and power‑law random graphs with degree distribution proportional to k^−β are of particular interest. The authors prove that for certain random‑graph families with given expected degrees, the average distance is almost surely of order log n / log d̃, where d̃ is the weighted average of the squared expected degrees. For β > 3 the average distance is log n / log d̃, whereas for 2 < β < 3 it is log log n while the diameter remains log n, with a dense core of size n^{c}/log log n containing almost all vertices within log log n.

Abstract

Random graph theory is used to examine the "small-world phenomenon"– any two strangers are connected through a short chain of mutual acquaintances. We will show that for certain families of random graphs with given expected degrees, the average distance is almost surely of order log _n_/ log_d̃_ where _d̃_ is the weighted average of the sum of squares of the expected degrees. Of particular interest are power law random graphs in which the number of vertices of degree _k_ is proportional to 1/_k_^β for some fixed exponent _β_. For the case of _β_ > 3, we prove that the average distance of the power law graphs is almost surely of order log _n_/ log _d̃_. However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 < β < 3 for which the power law random graphs have average distance almost surely of order log log _n_, but have diameter of order log _n_ (provided having some mild constraints for the average distance and maximum degree). In particular, these graphs contain a dense subgraph, that we call the core, having _n_^{<em>c</em>/ log log <em>n</em>} vertices. Almost all vertices are within distance log log _n_ of the core although there are vertices at distance log _n_ from the core.