Scale-Free Networks Are Ultrasmall

Reuven Cohen and Shlomo Havlin
Phys. Rev. Lett. 90, 058701 – Published 4 February 2003

Abstract

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 dlnN, we show, using analytical arguments, that scale-free networks with 2<λ<3 have a much smaller diameter, behaving as dlnlnN. For λ=3, our analysis yields dlnN/lnlnN, as obtained by Bollobas and Riordan, while for λ>3, dlnN. We also show that, for any λ>2, one can construct a deterministic scale-free network with dlnlnN, which is the lowest possible diameter.

  • Figure
  • Received 1 July 2002

DOI:https://doi.org/10.1103/PhysRevLett.90.058701

©2003 American Physical Society

Authors & Affiliations

Reuven Cohen* and Shlomo Havlin

  • Minerva Center and Department of Physics, Bar-Ilan University, Ramat-Gan, Israel

  • *Email address: cohenr@shoshi.ph.biu.ac.il

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 90, Iss. 5 — 7 February 2003

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×