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)\ensuremath{\propto}{k}^{\ensuremath{-}\ensuremath{\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\ensuremath{\sim}\mathrm{ln}N$, we show, using analytical arguments, that scale-free networks with $2<\ensuremath{\lambda}<3$ have a much smaller diameter, behaving as $d\ensuremath{\sim}\mathrm{ln}\mathrm{ln}N$. For $\ensuremath{\lambda}=3$, our analysis yields $d\ensuremath{\sim}\mathrm{ln}N/\mathrm{ln}\mathrm{ln}N$, as obtained by Bollobas…