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 nlog 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 1kbeta 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 nlog d. However, many Internet, social, and citation networks are power law graphs…