The average distances in random graphs 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 n/log (d) over tilde, where (d) over tilde 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(beta) for some fixed exponent beta. For the case of beta > 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 < beta < 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, which we call the core, having n(c/log log n) vertices. Almost all vertices are within distance log log n of the core although there are vertices at distance log n from the core.