Scale-Free Networks are Ultrasmall

Original · EN

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