The Average Distance in a Random Graph with Given Expected Degrees

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 ₙ_/ logd̃_ 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 ₖ_ is proportional to 1/ₖ_β 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 ₙ_/ log d̃_. However, many Internet, social, and citation networks are power law graphs with exponents in the range 2 c/ log log n vertices. Almost all vertices are within distance log log ₙ_ of the core although there are vertices at distance log ₙ_ from the core.