Metric structure of random networks

Abstract

We propose a consistent approach to the statistics of the shortest paths in random graphs with a given degree distribution. This approach goes further than a usual tree ansatz and rigorously accounts for loops in a network. We calculate the distribution of shortest-path lengths (intervertex distances) in these networks and a number of related characteristics for the networks with various degree distributions. We show that in the large network limit this extremely narrow intervertex distance distribution has a finite width while the mean intervertex distance grows with the size of a network. The size dependence of the mean intervertex distance is discussed in various situations.

24 pages, 5 figures

Cited by in corpus (55)

• Critical phenomena in complex networks
• Percolation on complex networks: Theory and application
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Bipartite Graphs as Models of Complex Networks
• Network Geometry
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• On Compact Routing for the Internet
• Compact Routing on Internet-Like Graphs
• Laplacian spectra of complex networks and random walks on them: Are scale-free architectures really important?
• Linking the Network Centrality Measures Closeness and Degree
• Entrainment of randomly coupled oscillator networks by a pacemaker
• Universal scaling of distances in complex networks
• Portraits of Complex Networks
• Exact Solution for the Time Evolution of Network Rewiring Models
• Exact analytical solution of average path length for Apollonian networks
• Organization of modular networks
• Generation of arbitrarily two-point correlated random networks
• Distance distribution in random graphs and application to networks exploration
• Complex network view of evolving manifolds
• Nonbacktracking expansion of finite graphs
• Average distance in a hierarchical scale-free network: an exact solution
• Analytical results for the distribution of shortest path lengths in random networks
• Degree-dependent intervertex separation in complex networks
• Distance distribution in configuration model networks
• Limited path entanglement percolation in quantum complex networks
• Navigating ultrasmall worlds in ultrashort time
• The distribution of shortest path lengths in a class of node duplication network models
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• Distribution of shortest cycle lengths in random networks
• On the Tomography of Networks and Multicast Trees
• Statistical analysis of articulation points in configuration model networks
• Analytical results for the distribution of shortest path lengths in directed random networks that grow by node duplication
• Correlations in interacting systems with a network topology
• Dynamics of condensation in growing complex networks
• Critical behavior and correlations on scale-free small-world networks. Application to network design
• Emergence of Robustness in Network of Networks
• Node-node distance distribution for growing networks
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• The rigorous solution for the average distance of a Sierpinski network
• Statistical analysis of edges and bredges in configuration model networks
• When is a scale-free graph ultra-small?
• Average distance in growing trees
• Phases of Small Worlds: A Mean Field Formulation
• Dependence of the average to-node distance on the node degree for random graphs and growing networks
• Distance Distribution in Extreme Modular Networks
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Log-periodic oscillations due to discrete effects in complex networks
• Condensation phase transition in nonlinear fitness networks
• Memory effect in growing trees
• Tsallis mapping in growing complex networks with fitness
• Unusual percolation in simple small-world networks
• Statistics of remote regions of networks
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment