Distance distribution in configuration model networks

Abstract

We present analytical results for the distribution of shortest path lengths between random pairs of nodes in configuration model networks. The results, which are based on recursion equations, are shown to be in good agreement with numerical simulations for networks with degenerate, binomial and power-law degree distributions. The mean, mode and variance of the distribution of shortest path lengths are also evaluated. These results provide expressions for central measures and dispersion measures of the distribution of shortest path lengths in terms of moments of the degree distribution, illuminating the connection between the two distributions.

arXiv comment28 pages, 7 figures. Accepted for publication in Phys. Rev. E

References in corpus (16)

• Statistical mechanics of complex networks
• Epidemic spreading in scale-free networks
• Epidemic processes in complex networks
• Random graphs with arbitrary degree distributions and their applications
• Scale-Free Networks are Ultrasmall
• The phase transition in inhomogeneous random graphs
• Average path length in random networks
• Average path length in uncorrelated random networks with hidden variables
• Betweenness centrality correlation in social networks
• Percolation of localized attack on complex networks
• Structure of shells in complex networks
• Metric structure of random networks
• Distance distribution in random graphs and application to networks exploration
• Fractal Boundaries of Complex Networks
• Analytical results for the distribution of shortest path lengths in random networks
• On the Tomography of Networks and Multicast Trees

Cited by in corpus (22)

• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• 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
• 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
• The distribution of first hitting times of random walks on Erdős-Rényi networks
• Highly Clustered Complex Networks in the Configuration Model: Random Regular Small-World Network
• The distribution of first hitting times of random walks on directed Erdős-Rényi networks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• The birth of geometry in exponential random graphs
• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• Statistical analysis of edges and bredges in configuration model networks
• The distribution of first hitting times of non-backtracking random walks on Erdős-Rényi networks
• Concurrency and reachability in tree-like temporal networks
• Phases of Small Worlds: A Mean Field Formulation
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• Distance Distribution in Extreme Modular Networks
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment
• Resistance distance distribution in large sparse random graphs
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks