🔬 condensed matter

The distribution of eccentricities in random regular graphs

本文推导出了随机正则图中离心率全分布的闭式解析表达式，揭示了尽管度数均匀但节点离心率仍存在非平凡的变化，并提供了用于分析大型稀疏网络的均值、众数和方差的精确公式，以此作为基准。

原作者： Dor Lev-Ari, Ofer Biham, Eytan Katzav

发布于 2026-07-17

📖 1 分钟阅读☕ 轻松阅读

原作者： Dor Lev-Ari, Ofer Biham, Eytan Katzav

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一座宏大而无形的城市，在那里，每一个人都是一栋房子，每一段友谊都是连接他们的道路。在科学世界中，这被称为“网络”。有些网络是混乱的，就像一个混乱的小镇，有些人拥有百万好友，而有些人却孑然一身。但在这样一个世界里，存在着一个特别的、完美有序的版本，叫做“随机正则图”（Random Regular Graph）。在这座城市里，每一栋房子通向外部的道路数量完全相同——比如，都是三条或五条。这是一个完美的平等世界，没有人比其他人拥有更多的连接。

科学家们早已知道，在这些城市中，两点之间的平均距离出奇地短。这就是“小世界”效应：即使是在一个巨大的城市里，你通常也只需要几步就能从自家门口走到城另一端的陌生人家中。但这里有一个陷阱。虽然“平均”行程很短，但“最长”的行程才是最重要的。如果你在传递一条消息、一种病毒或一个传闻，重要的不是平均每个人接收的速度有多快，而是它到达最后一名最孤立的人需要多久。这个最大距离被称为“离心率”（eccentricity）。一个大问题是：如果每栋房子拥有的道路数量完全相同，那么它们是否都处于距离世界边缘相同的距离，还是说城市的形状创造了一些天然更“外围”的房子？

来自耶路撒冷希伯来大学的一个物理学家团队决定绘制这张隐藏的地形图。他们不仅是在猜测，而是建立了一个数学模型来描述整个距离分布。他们发现，即使在每个人连接数都完全相等的城市里，“到边缘的距离”也不是每个人都一样的。相反，它遵循一种非常特定、可预测的模式，看起来像是一个阶梯。

以下是他们的发现。首先，他们推导出了一个精确的公式，可以预测一栋房子具有某种离心率的概率。这就像是一份天气预报，只不过预报的不是降雨，而是房子距离城市边界有多远。他们发现，这种分布遵循一种被称为 Gumbel 分布的形式（这是描述极端情况的一种特定类型的钟形曲线的专业名称）。他们创建的公式使用了三个主要成分：城市规模（ $N$ ）、每栋房子的道路数（ $c$ ）以及一些数学常数。

最令人着迷的部分是，随着城市规模的增长，“典型”距离是如何变化的。如果你将最常见的距离对城市规模进行绘图，它不会像斜坡一样平滑上升。相反，它看起来像一个阶梯。在一段时间内，最常见的距离会保持在 5 步；然后，随着城市稍微变大，它会突然跳到 6 步，停留一段时间，然后再跳到 7 步。作者们称这个现象为“众数”（mode）。他们证明了这种阶梯步进始终是“平均”距离的最接近的整数。所以，如果数学计算出的平均距离是 5.8，那么几乎所有人的最常见距离就是 6。

他们还观察了这些距离的变化程度。在一个平滑、连续的世界里，你可能会认为变化量微乎其微。但由于城市中的距离是以整数步数来计数的（你不能走 5.5 步），所以随着城市规模的增长，这种变化会像心跳一样上下波动。当城市即将从距离 5 跳跃到 6 时，这种变化会达到顶峰，因为有些房子还停留在 5，而另一些已经达到了 6。在这些“临界点”，变化量约为 0.25，这是在一半房子处于一个距离、另一半处于下一个距离的“抛硬币”情景下的最大可能值。

研究人员通过运行计算机模拟这些城市（创建了数千个不同规模的网络）来测试他们的数学模型。他们发现，随着城市规模变大，他们的公式与计算机结果完美契合。例如，在一个每栋房子有 5 条道路（ $c=5$ ）的城市中，当城市规模约为 160 户时，几乎所有人距离边缘都是 5 步。但一旦城市规模增长到 440 户，几乎所有人突然就变成了 6 步之遥。

为什么这很重要？想象你是一名快递员、广播员或是一种病毒。你并不关心平均交付时间；你关心的是最坏的情况。一条消息到达最遥远的那栋房子需要多长时间？这篇论文为我们提供了一个精确的工具，可以用它来计算任何每个人都有相同连接数的网络的“最坏情况延迟”。事实证明，即使是在一个完美的公平网络中，空间的几何结构也会创造出一个自然的“边缘”，而到这个边缘的距离以一种非常特定的、步进式的方式增长。作者们指出，他们的公式可以作为一种基准，用于检查计算机算法在处理巨大的稀疏网络时计算这些距离的效果如何。简而言之，他们向我们展示了，即使在一个完美的平等世界里，通往边缘的地图也是有节奏的，而那个节奏就是阶梯。

技术摘要：随机正则图中的离心率分布

问题陈述
随机正则图（RRGs）中每个节点的度数均为相同的 $c$ ，这类图是网络理论中的一个基本集合。虽然这些图的局部结构由均匀的度分布定义，但其大规模结构则由最短路径长度分布（DSPL）和节点离心率（eccentricity）所表征。节点的离心率定义为该节点到网络中任何其他节点的最大距离。尽管 RRG 中所有节点的度数都相同，但其离心率却表现出非平凡的变化。本文旨在解决离心率全分布（DoE）缺乏闭式解析表达式的问题，并指出现有文献通常侧重于单一特征长度尺度（如平均值或直径），而非完整的统计分布。理解 DoE 对于广播和全局传播等实际应用至关重要，因为这些应用中的网络性能受限于最坏情况下的延迟时间（最大离心率）。

方法论
作者采用极值理论的方法，推导了由 $N$ 个节点和度数 $c \ge 3$ 组成的 RRG 的 DoE。推导过程如下：

基于 DSPL 的基础： 本研究利用了已知的最短路径长度分布尾部 $P(L > \ell)$ 的闭式解析表达式，该分布遵循离散 Gompertz 分布。
极值理论的应用： 将节点的离心率视为到其他 $N-1$ 个节点距离的最大值，作者对 DoE 进行建模。假设在足够大的网络中，各距离之间存在弱相关性，则最大值的累积分布可以通过底层 DSPL 的尾部分布进行近似。
解析推导： 通过将 DSPL 尾部代入极值框架，作者推导出了离心率尾部分布的闭式表达式 $P(E > \ell)$ 。
统计矩： 利用尾部求和公式和 Euler-Maclaurin 求和技术，作者推导出了平均离心率 $\langle E \rangle$ 、众数 $E_{\text{mode}}$ 和方差 $\text{Var}(E)$ 的闭式表达式。
验证： 作者通过通过 stub-matching 程序生成 RRG，并随后通过边交换过程消除自环和多重边，以此进行计算机模拟，从而验证解析结果。模拟是在不同规模 $N$ 和度数 $c$ 下，对 1,000 个网络实例进行的平均处理。

主要贡献与结果

闭式分布： 主要贡献是推导出了离心率的尾部分布：
$P(E > \ell) \simeq 1 - \exp\left[ -\exp\left( -\frac{e^{b\ell} - \mu}{\beta} \right) \right]$
其中 $b = \ln(c-1)$ 是形状参数， $\beta = \frac{c-2}{c}N$ 是尺度参数， $\mu = \frac{c-2}{c}N \ln N$ 是位置参数。该分布类似于 Gumbel 分布，但其参数项中包含的是指数项而非线性项。
平均离心率： 推导出了平均离心率的闭式表达式：
$\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)$
作者指出，虽然模拟结果会锁定在整数值上，但解析表达式提供了一个平滑的轮廓，能够阐明其标度行为。
众数与阶梯状轮廓： 研究发现，DoE 的众数 $E_{\text{mode}}$ 随网络规模 $N$ 呈现出阶梯状轮廓。作者证明了众数即为平均值的最近整数： $E_{\text{mode}} = \text{Round}(\langle E \rangle)$ 。众数整数值之间的转换点是通过 Lambert $W$ 函数确定的。
方差与振荡： 计算了方差 $\text{Var}(E)$ ，并显示其随 $N$ 呈现出振荡现象。这些振荡源于离心率的离散性质。方差在众数从 $\ell$ 转向 $\ell+1$ 的步进边缘附近达到峰值，当分布实际上是二元的（即 $P(E=\ell) \approx P(E=\ell+1) \approx 1/2$ ）时，其最大值约为 $1/4$ 。
有限尺寸效应： 解析结果与大 $N$ 情况下的模拟结果高度吻合。在较小规模的网络中观察到的差异归因于有限尺寸效应，特别是在尾部分布的转换点附近。

意义
本文声称，提供离心率的全分布而非仅仅是一个单一的特征长度尺度，可以为 RRG 的大规模结构提供更详尽的视图。推导出的解析表达式可作为大型稀疏网络中离心率计算算法的基准。结果强调，即使在度数均匀的网络中，离心率也会发生显著变化，而这些变化可以通过推导出的分布来捕捉。这项工作证实了 DoE 是一个窄分布，这意味着网络直径（最大离心率）与半径（最小离心率）之间的差异仅为 $O(1)$ 阶。作者总结道，这些发现对于由最长延迟时间决定的实际应用（如广播和全局传播协议）具有重要意义。

类似论文