Scale-Free Networks Are Ultrasmall

We study the diameter, or the mean distance between sites, in a scale-free network, having N sites and degree distribution p(k)∝k^-λ, 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∼ln⁡N, we show, using analytical arguments, that scale-free networks with 2<λ<3 have a much smaller diameter, behaving as d∼ln⁡ln⁡N. For λ=3, our analysis yields d∼ln⁡N/ln⁡ln⁡N, as obtained by Bollobas and Riordan, while for λ>3, d∼ln⁡N. We also show that, for any λ>2, one can construct a deterministic scale-free network with d∼ln⁡ln⁡N, which is the lowest possible diameter.