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 dN, we show, using analytical arguments, that scale-free networks with 23, dN. We also show that, for any >2, one can construct a deterministic scale-free network with dlnN, which is the lowest possible diameter.