The distribution of eccentricities in random regular graphs
Abstract
We derive a closed-form analytical expression for the distribution of eccentricities (DoE) in random regular graphs (RRGs) that consist of N nodes of degree c. The DoE is given by the tail distribution P(E > ℓ) ≃ 1 − exp [ − exp ( − ( eb ℓ − μ)/β ) ], where the distance ℓ takes integer values, b = ln (c−1) is the shape parameter, β= (c−2)/c N is the scale parameter and μ= (c−2)/c N ln N is the location parameter. By providing the full distribution rather than a single characteristic length scale, we present a detailed view of the large-scale structure. In spite of the fact that the degrees of all the nodes are the same, their eccentricities exhibit non-trivial variations. We derive a closed-form expression for the mean eccentricity, which is given by ⟨ E ⟩ ≃ (ln N)/(ln (c−1)) + (ln ln N)/(ln (c−1)) − ( ln c − ln (c−2) )/( ln (c−1) ) + 1/2. We calculate the mode of the DoE, which exhibits a staircase profile as a function of the network size. Interestingly, the mode is given by Emode =Round ( ⟨ E ⟩ ), where Round( x ) is the nearest integer to x. We also calculate the variance Var(E) and show that it exhibits oscillations as a function of the network size N. The results presented in this paper may serve as benchmarks for algorithmic approaches to eccentricity calculations in large sparse networks. The eccentricities are important in practical applications such as broadcasting and global dissemination, where the network performance is determined by the longest delay times.
Versions
Related
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- Quantum random walks on d-regular graphs with Haar-random coin operators
- Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
- Moment Methods for Uniform Average Mixing on Strongly Regular Graphs
- Random Cellular Automata and deBruijn Graphs
BibTeX
@misc{levari2026distribution,
title = {{The distribution of eccentricities in random regular graphs}},
author = {Dor Lev-Ari and Ofer Biham and Eytan Katzav},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.14799},
eprint = {2607.14799},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.14799},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The distribution of eccentricities in random regular graphs
AU - Dor Lev-Ari
AU - Ofer Biham
AU - Eytan Katzav
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2607.14799
UR - https://arxiv.org/abs/2607.14799
AB - We derive a closed-form analytical expression for the distribution of eccentricities (DoE) in random regular graphs (RRGs) that consist of N nodes of degree c. The DoE is given by the tail distribution P(E > ℓ) ≃ 1 − exp [ − exp ( − ( e^b ℓ − μ)/β ) ], where the distance ℓ takes integer values, b = ln (c−1) is the shape parameter, β= (c−2)/c N is the scale parameter and μ= (c−2)/c N ln N is the location parameter. By providing the full distribution rather than a single characteristic length scale, we present a detailed view of the large-scale structure. In spite of the fact that the degrees of all the nodes are the same, their eccentricities exhibit non-trivial variations. We derive a closed-form expression for the mean eccentricity, which is given by ⟨ E ⟩ ≃ (ln N)/(ln (c−1)) + (ln ln N)/(ln (c−1)) − ( ln c − ln (c−2) )/( ln (c−1) ) + 1/2. We calculate the mode of the DoE, which exhibits a staircase profile as a function of the network size. Interestingly, the mode is given by E_mode =Round ( ⟨ E ⟩ ), where Round( x ) is the nearest integer to x. We also calculate the variance Var(E) and show that it exhibits oscillations as a function of the network size N. The results presented in this paper may serve as benchmarks for algorithmic approaches to eccentricity calculations in large sparse networks. The eccentricities are important in practical applications such as broadcasting and global dissemination, where the network performance is determined by the longest delay times.
ER -