Abstract
We study the diameter, or the mean distance between sites, in a scale-free network, having sites and degree distribution , i.e., the probability of having links outgoing from a site. In contrast to the diameter of regular random networks or small-world networks, which is known to be , we show, using analytical arguments, that scale-free networks with have a much smaller diameter, behaving as . For , our analysis yields , as obtained by Bollobas and Riordan, while for , . We also show that, for any , one can construct a deterministic scale-free network with , which is the lowest possible diameter.
- Received 1 July 2002
DOI:https://doi.org/10.1103/PhysRevLett.90.058701
©2003 American Physical Society