Universal scaling of distances in complex networks

Abstract

Universal scaling of distances between vertices of Erdos-Renyi random graphs, scale-free Barabasi-Albert models, science collaboration networks, biological networks, Internet Autonomous Systems and public transport networks are observed. A mean distance between two nodes of degrees k_i and k_j equals to <l_{ij}>=A-B log(k_i k_j). The scaling is valid over several decades. A simple theory for the appearance of this scaling is presented. Parameters A and B depend on the mean value of a node degree <k>_nn calculated for the nearest neighbors and on network clustering coefficients.

4 pages, 3 figures, 1 table

References in corpus (17)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Lethality and centrality in protein networks
• Assortative mixing in networks
• The architecture of complex weighted networks
• Evolution of networks
• Hierarchical Organization in Complex Networks
• Scale-Free Networks are Ultrasmall
• Betweenness Centrality in Large Complex Networks
• Weighted evolving networks: coupling topology and weights dynamics
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Fluctuations in network dynamics
• Optimal Paths in Disordered Complex Networks
• Community analysis in social networks
• Range-based attack on links in scale-free networks: are long-range links responsible for the small-world phenomenon?
• Metric structure of random networks

Cited by in corpus (21)

• Statistical analysis of 22 public transport networks in Poland
• Public transport networks: empirical analysis and modeling
• Nature of the epidemic threshold for the susceptible-infected-susceptible dynamics in networks
• Random walks on complex trees
• Exact solution of mean geodesic distance for Vicsek fractals
• Exact analytical solution of average path length for Apollonian networks
• The Workshop on Internet Topology (WIT) Report
• Collective versus hub activation of epidemic phases on networks
• Empirical analysis of the ship-transport network of China
• Fractal Boundaries of Complex Networks
• Fractal scale-free networks resistant to disease spread
• Average distance in a hierarchical scale-free network: an exact solution
• Robustness and fragility of the susceptible-infected-susceptible epidemic models on complex networks
• Degree-dependent intervertex separation in complex networks
• The rigorous solution for the average distance of a Sierpinski network
• When is a scale-free graph ultra-small?
• Phases of Small Worlds: A Mean Field Formulation
• Dynamical correlations and pairwise theory for the symbiotic contact process on networks
• Log-periodic oscillations due to discrete effects in complex networks
• Scaling of internode distances in weighted complex networks
• Universality classes in the time evolution of epidemic outbreaks on complex networks