The average distances in random graphs with given expected degrees

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, which we call the core, having nc/log log nvertices. Almost all vertices are within distance log log n of the core although there are vertices at distance log n from the core.