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) proportional, variant k(-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 approximately ln(N, we show, using analytical arguments, that scale-free networks with 2<lambda<3 have a much smaller diameter, behaving as d approximately ln(ln(N. For lambda=3, our analysis yields d approximately ln(N/ln(ln(N, as obtained by Bollobas and Riordan, while for lambda>3, d approximately ln(N. We also show that, for any lambda>2, one can construct a deterministic scale-free network with d approximately ln(ln(N, which is the lowest possible diameter.
Cohen
Reuven
R
Minerva Center and Department of Physics, Bar-Ilan University, Ramat-Gan, Israel. cohenr@shoshi.ph.biu.ac.il
Havlin
Shlomo
S
D002468:Cell Physiological Phenomena; D008962:Models, Theoretical; D016571:Neural Networks, Computer; D012944:Social Support; D018406:Virus Physiological Phenomena