The mean and variance of the distribution of shortest path lengths of random regular graphs

Abstract

The distribution of shortest path lengths (DSPL) of random networks provides useful information on their large scale structure. In the special case of random regular graphs (RRGs), which consist of $N$ nodes of degree $c\ge 3$, the DSPL, denoted by $P(L=\ell )$, follows a discrete Gompertz distribution. Using the discrete Laplace transform we derive a closed-form expression for the moment generating function of the DSPL of RRGs. From the moment generating function we obtain closed-form expressions for the mean and variance of the DSPL. More specifically, we find that the mean distance between pairs of distinct nodes is given by $⟨L⟩=\frac{\ln N}{\ln (c-1)}+\frac{1}{2}-\frac{\ln c-\ln (c-2)+\gamma }{\ln (c-1)}+\mathcal{O}\left(\frac{\ln N}{N}\right)$, where $\gamma$ is the Euler-Mascheroni constant. While the leading term is known, this result includes a novel correction term, which yields very good agreement with the results obtained from direct numerical evaluation of $⟨L⟩$ via the tail-sum formula and with the results obtained from computer simulations. However, it does not account for an oscillatory behavior of $⟨L⟩$ as a function of $c$ or $N$. These oscillations are negligible in sparse networks but detectable in dense networks. We also derive an expression for the variance $\mathrm{Var}(L)$ of the DSPL, which captures the overall dependence of the variance on $c$ but does not account for the oscillations. The oscillations are due to the discrete nature of the shell structure around a random node. They reflect the profile of the filling of new shells as $N$ is increased. The results for the mean and variance are compared to the corresponding results obtained in other types of random networks. The relation between the mean distance and the diameter is discussed.

25 pages, 7 figures

References in corpus (7)

• Structural Transitions in Dense Networks
• Distance distribution in random graphs and application to networks exploration
• The cavity method at zero temperature
• The distribution of shortest path lengths in a class of node duplication network models
• Distribution of shortest cycle lengths in random networks
• Phases of Small Worlds: A Mean Field Formulation
• Distance Distribution in Extreme Modular Networks

Cited by in corpus (8)

• Analytical results for the distribution of first-passage times of random walks on random regular graphs
• Soft modes in vector spin glass models on sparse random graphs
• The distribution of shortest path lengths on trees of a given size in subcritical Erdos-Renyi networks
• A Gaussian integral that counts regular graphs
• Larger holes as narrower degree distributions in complex networks
• Statistics of remote regions of networks
• Integer Traffic Assignment Problem: Algorithms and Insights on Random Graphs
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks