Scale-free networks are ultrasmall.

By R. Cohen, Shlomo Havlin. Physical Review Letters, 2002

787 citations recorded by the source corpus.

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.

Subfields: Geometry and Topology, Mathematical Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/f63ebd3d37a5b023fd82cfbe79713d28f979790d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Mathematical Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Characterization of complex networks: A survey of measurements (2005, background): “[55], Chung and Lu [56] and Cohen and Havlin [57].”
Synchronization in complex networks (2008, background): “Generally speaking, l is lower in SF networks than in ER networks due to the presence of hubs [109], and l is lower in SW networks than in regular lattices due to the presence of shortcuts.”
The Structure and Function of Complex Networks (2003, background): “164), and Cohen and Havlin [95] have given arguments that suggest that the actual variation may be slower even than this.”
Modeling interactome: scale-free or geometric? (2004, background): “... over all pairs of nodes in the network (West, 2001).) This network property also distinguishes different network models: for example, the diameter of Erd¨ os-R´ enyi random networks on nodes is proportional to , the network property often referred to as the small-world property; the diameters of”
DATA ANALYSIS IN PUBLIC SOCIAL NETWORKS (2012, background): “Key words: social networks 1 , big data 2 , scale-free networks 3 , data security 4 , graph theory 5”
Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence (2008, background): “These networks are thus ultra-small [29], and indeed both email message (#7) and software package (#21) networks fall further from the linear model than any others.”
Dynamical patterns of epidemic outbreaks in complex heterogeneous networks. (2004, neutral): “This implies that both sexually transmitted diseases and computer viruses may fit in this scenario, raising new questions and scrutiny on several epidemic models and strategies aimed at optimizing the deployment of immunization resources (Dezsoänd Baraba´si, 2002; Cohen and Havlin, 2003).”
Transcriptional Regulatory Networks in Saccharomyces cerevisiae (2009, background): “Although the small-world effect can be found in random networks, the diameters of scale-free networks are ultra-small [11].”
Analysis of topological characteristics of huge online social networking services (2007, background): “These networks also have distinguishing properties, such as vanishing epidemic threshold, ultra-small worldness, and robustness under random errors [11, 12, 13, 14].”