Abstract
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.
Keywords
PhysicsLambdaCombinatoricsDegree (music)Quantum mechanicsMathematics
Affiliated Institutions
Related Publications
Scaling Theory of Localization: Absence of Quantum Diffusion in Two Dimensions
Arguments are presented that the $T=0$ conductance $G$ of a disordered electronic system depends on its length scale $L$ in a universal manner. Asymptotic forms are obtained for...
Localization and absorption of waves in a weakly dissipative disordered medium
The effect of a small imaginary part ${\ensuremath{\epsilon}}_{2}$ to the dielectric constant on the propagation of waves in a disordered medium near the Anderson localization t...
The impact of antenna diversity on the capacity of wireless communication systems
For a broad class of interference-dominated wireless systems including mobile, personal communications, and wireless PBX/LAN networks, the authors show that a significant increa...
Planck 2018 results. VI. Cosmological parameters
We present cosmological parameter results from the final full-mission Planck\nmeasurements of the CMB anisotropies. We find good consistency with the\nstandard spatially-flat 6-...
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
This paper proves best known guarantees for exact reconstruction of a sparse signal f from few non-adaptive universal linear measurements. We consider Fourier measurements (rand...
Publication Info
- Year
- 2003
- Type
- article
- Volume
- 90
- Issue
- 5
- Pages
- 058701-058701
- Citations
- 799
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
799
OpenAlex
Cite This
Reuven Cohen,
Shlomo Havlin
(2003).
Scale-Free Networks Are Ultrasmall.
Physical Review Letters
, 90
(5)
, 058701-058701.
https://doi.org/10.1103/physrevlett.90.058701
Identifiers
- DOI
- 10.1103/physrevlett.90.058701