Journal
PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
Volume 99, Issue 25, Pages 15879-15882Publisher
NATL ACAD SCIENCES
DOI: 10.1073/pnas.252631999
Keywords
-
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available