Scale-Free Networks Are Ultrasmall
Top Cited Papers
- 4 February 2003
- journal article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 90 (5) , 058701
- https://doi.org/10.1103/physrevlett.90.058701
Abstract
We study the diameter, or the mean distance between sites, in a scale-free network, having N sites and degree distribution p(k) proportional, variant k(-lambda), i.e., the probability of having k links outgoing from a site. In contrast to the diameter of regular random networks or small-world networks, which is known to be d approximately ln(N, we show, using analytical arguments, that scale-free networks with 23, d approximately ln(N. We also show that, for any lambda>2, one can construct a deterministic scale-free network with d approximately ln(ln(N, which is the lowest possible diameter.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- The average distances in random graphs with given expected degreesProceedings of the National Academy of Sciences, 2002
- Universal Behavior of Load Distribution in Scale-Free NetworksPhysical Review Letters, 2001
- Search in power-law networksPhysical Review E, 2001
- Extremal properties of random treesPhysical Review E, 2001
- Random graphs with arbitrary degree distributions and their applicationsPhysical Review E, 2001
- Bose-Einstein Condensation in Complex NetworksPhysical Review Letters, 2001
- Size-dependent degree distribution of a scale-free growing networkPhysical Review E, 2001
- Resilience of the Internet to Random BreakdownsPhysical Review Letters, 2000
- Graph structure in the WebComputer Networks, 2000
- The Size of the Giant Component of a Random Graph with a Given Degree SequenceCombinatorics, Probability and Computing, 1998