🔬 condensed matter

The distribution of eccentricities in random regular graphs

This paper derives a closed-form analytical expression for the full distribution of eccentricities in random regular graphs, revealing non-trivial variations in node eccentricities despite uniform degrees and providing precise formulas for the mean, mode, and variance that serve as benchmarks for analyzing large sparse networks.

Original authors: Dor Lev-Ari, Ofer Biham, Eytan Katzav

Published 2026-07-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Dor Lev-Ari, Ofer Biham, Eytan Katzav

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast, invisible city where every person is a house, and every friendship is a road connecting them. In the world of science, this is called a "network." Some networks are messy, like a chaotic town where some people have a million friends and others have none. But there is a special, perfectly organized version of this city called a "Random Regular Graph." In this city, every single house has exactly the same number of roads leading out of it—say, three or five. It's a world of perfect equality, where no one is more connected than anyone else.

Scientists have long known that in these cities, the average distance between any two houses is surprisingly short. This is the "small-world" effect: even in a huge city, you can usually get from your front door to a stranger's across town in just a few steps. But there's a catch. While the average trip is short, the longest trip matters most. If you are sending a message, a virus, or a rumor, it doesn't matter how fast the average person gets it; it matters how long it takes to reach the very last, most isolated house. This maximum distance is called "eccentricity." The big question is: if every house has the exact same number of roads, do they all sit at the same distance from the edge of the world, or does the city's shape create some houses that are naturally more "peripheral" than others?

A team of physicists from the Hebrew University in Jerusalem decided to map this hidden landscape. They didn't just guess; they built a mathematical model to describe the entire distribution of these distances. They found that even in a city where everyone is equally connected, the "distance to the edge" isn't the same for everyone. Instead, it follows a very specific, predictable pattern that looks like a staircase.

Here is what they discovered. First, they derived a precise formula that predicts the probability of a house having a certain eccentricity. Think of it like a weather forecast, but instead of rain, it predicts how far a house is from the city limits. They found that this distribution follows a shape known as the Gumbel distribution (a fancy name for a specific type of bell curve that deals with extremes). The formula they created uses three main ingredients: the size of the city ( $N$ ), the number of roads per house ( $c$ ), and a few mathematical constants.

The most fascinating part of their discovery is how the "typical" distance behaves as the city grows. If you plot the most common distance against the size of the city, it doesn't rise smoothly like a ramp. Instead, it looks like a staircase. For a while, the most common distance stays at, say, 5 steps. Then, as the city gets just a little bigger, it suddenly jumps to 6 steps, stays there for a while, and then jumps to 7. The authors call this the "mode" of the distribution. They proved that this staircase step is always the nearest whole number to the "average" distance. So, if the math says the average distance is 5.8, the most common distance for almost everyone is 6.

They also looked at how much these distances vary. In a smooth, continuous world, you might expect the variation to be tiny. But because distances in a city are counted in whole steps (you can't walk 5.5 steps), the variation wiggles up and down like a heartbeat as the city grows. When the city is just about to jump from a distance of 5 to 6, the variation hits a peak because some houses are stuck at 5 while others have already reached 6. At these "tipping points," the variation is about 0.25, which is the maximum possible for a coin-flip scenario where half the houses are at one distance and half are at the next.

The researchers tested their math by running computer simulations of these cities, creating thousands of networks with different sizes. They found that their formulas matched the computer results almost perfectly, especially as the cities got larger. For example, in a city where every house has 5 roads ( $c=5$ ), when the city has about 160 houses, almost everyone is 5 steps from the edge. But once the city grows to 440 houses, almost everyone is suddenly 6 steps away.

Why does this matter? Imagine you are a delivery driver, a broadcaster, or a virus. You don't care about the average delivery time; you care about the worst-case scenario. How long does it take for a message to reach the absolute farthest house? This paper gives us a precise tool to calculate that worst-case delay for any network where everyone has the same number of connections. It turns out that even in a perfectly fair network, the geometry of the space creates a natural "edge," and the distance to that edge grows in a very specific, step-by-step way. The authors suggest that their formulas can serve as a benchmark for checking how well computer algorithms work when they try to calculate these distances in huge, sparse networks. In short, they've shown us that even in a world of perfect equality, the map to the edge has a rhythm, and that rhythm is a staircase.

Technical Summary: The Distribution of Eccentricities in Random Regular Graphs

Problem Statement
Random Regular Graphs (RRGs), where every node possesses an identical degree $c$ , are a fundamental ensemble in network theory. While the local structure of these graphs is defined by the uniform degree distribution, their large-scale structure is characterized by the distribution of shortest path lengths (DSPL) and node eccentricities. The eccentricity of a node is defined as the maximum distance from that node to any other node in the network. Although the degrees of all nodes in an RRG are identical, the eccentricities exhibit non-trivial variations. The paper addresses the lack of a closed-form analytical expression for the full distribution of these eccentricities (DoE), noting that existing literature often focuses on single characteristic length scales (such as the mean or diameter) rather than the complete statistical distribution. Understanding the DoE is critical for practical applications like broadcasting and global dissemination, where network performance is dictated by worst-case delay times (maximum eccentricity).

Methodology
The authors employ methods from extreme value theory to derive the DoE for RRGs consisting of $N$ nodes of degree $c \ge 3$ . The derivation proceeds through the following steps:

Foundation in DSPL: The study utilizes the known closed-form analytical expression for the tail of the DSPL, $P(L > \ell)$ , which follows a discrete Gompertz distribution.
Extreme Value Theory Application: Treating the eccentricity of a node as the maximum of $N-1$ distances to other nodes, the authors model the DoE. Assuming weak correlations between distances in sufficiently large networks, the cumulative distribution of the maximum is approximated using the tail distribution of the underlying DSPL.
Analytical Derivation: By substituting the DSPL tail into the extreme value framework, the authors derive a closed-form expression for the tail distribution of eccentricities, $P(E > \ell)$ .
Statistical Moments: Using the tail-sum formula and the Euler-Maclaurin summation technique, the authors derive closed-form expressions for the mean eccentricity $\langle E \rangle$ , the mode $E_{\text{mode}}$ , and the variance $\text{Var}(E)$ .
Validation: The analytical results are validated against computer simulations of RRGs generated via a stub-matching procedure followed by an edge-switching process to eliminate self-loops and multiple edges. Simulations were averaged over 1,000 network instances for various sizes $N$ and degrees $c$ .

Key Contributions and Results

Closed-Form Distribution: The primary contribution is the derivation of the tail distribution of eccentricities:
$P(E > \ell) \simeq 1 - \exp\left[ -\exp\left( -\frac{e^{b\ell} - \mu}{\beta} \right) \right]$
where $b = \ln(c-1)$ is the shape parameter, $\beta = \frac{c-2}{c}N$ is the scale parameter, and $\mu = \frac{c-2}{c}N \ln N$ is the location parameter. This distribution resembles a Gumbel distribution but features an exponential term in the argument rather than a linear one.
Mean Eccentricity: A closed-form expression for the mean eccentricity is derived:
$\langle E \rangle \simeq \frac{\ln N}{\ln(c-1)} + \frac{\ln \ln N}{\ln(c-1)} - \frac{\ln c - \ln(c-2)}{\ln(c-1)} + \frac{1}{2} + O\left(\frac{1}{\ln N}\right)$
The authors note that while simulation results lock into integer values, the analytical expression provides a smoothed contour that elucidates the scaling behavior.
Mode and Staircase Profile: The mode of the DoE, $E_{\text{mode}}$ , is found to exhibit a staircase profile as a function of network size $N$ . The authors demonstrate that the mode is simply the nearest integer to the mean: $E_{\text{mode}} = \text{Round}(\langle E \rangle)$ . The transition points between integer values of the mode are determined using the Lambert $W$ function.
Variance and Oscillations: The variance $\text{Var}(E)$ is calculated and shown to exhibit oscillations as a function of $N$ . These oscillations arise from the discrete nature of the eccentricity. The variance peaks near the step edges where the mode shifts from $\ell$ to $\ell+1$ , reaching a maximum value of approximately $1/4$ when the distribution is effectively binary ( $P(E=\ell) \approx P(E=\ell+1) \approx 1/2$ ).
Finite-Size Effects: The analytical results show excellent agreement with simulations for large $N$ . Discrepancies observed in smaller networks are attributed to finite-size effects, particularly near the transition points of the tail distribution.

Significance
The paper claims that providing the full distribution of eccentricities, rather than just a single characteristic length scale, offers a detailed view of the large-scale structure of RRGs. The derived analytical expressions serve as benchmarks for algorithmic approaches to eccentricity calculations in large sparse networks. The results highlight that even in networks with uniform degrees, eccentricities vary significantly, and these variations are captured by the derived distribution. The work confirms that the DoE is a narrow distribution, implying that the difference between the network diameter (maximum eccentricity) and radius (minimum eccentricity) is of order 1. The authors conclude that these findings are relevant for practical applications where network performance is determined by longest delay times, such as in broadcasting and global dissemination protocols.

More like this