Analytical results for the distribution of shortest path lengths in random networks

Abstract

We present two complementary analytical approaches for calculating the distribution of shortest path lengths in Erdos-Rényi networks, based on recursion equations for the shells around a reference node and for the paths originating from it. The results are in agreement with numerical simulations for a broad range of network sizes and connectivities. The average and standard deviation of the distribution are also obtained. In the case that the mean degree scales as $N^{\alpha }$ with the network size, the distribution becomes extremely narrow in the asymptotic limit, namely almost all pairs of nodes are equidistant, at distance $d=\lfloor 1/\alpha \rfloor$ from each other. The distribution of shortest path lengths between nodes of degree $m$ and the rest of the network is calculated. Its average is shown to be a monotonically decreasing function of $m$, providing an interesting relation between a local property and a global property of the network. The methodology presented here can be applied to more general classes of networks.

12 pages, 4 figures, accepted to EPL

References in corpus (1)

• Distance distribution in random graphs and application to networks exploration

Cited by in corpus (22)

• Distance distribution in configuration model networks
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• The distribution of shortest path lengths in subcritical Erdős-Rényi networks
• The distribution of shortest path lengths in a class of node duplication network models
• Distribution of shortest cycle lengths in random networks
• The distribution of path lengths of self avoiding walks on Erdős-Rényi 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
• 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 birth of geometry in exponential random 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
• A Pyramid Scheme Model Based on "Consumption Rebate" Frauds
• Statistics of remote regions of networks
• Resistance distance distribution in large sparse random graphs
• The effect of preferential node deletion on the structure of networks that evolve via preferential attachment