复杂网络中经验路径负载分布的有限时间松弛现象

《Physica A: Statistical Mechanics and its Applications》：Finite-time relaxation of empirical path-load distributions in complex networks

　　摘要：在复杂网络中，重复使用最短路径会导致不同的实证路径负载分布，其整体不等性会趋向于与拓扑结构相关的稳定值。我们研究了在累积最短路径负载作用下的这些分布的有限时间形成过程，并在合成拓扑和实证拓扑中发现了类似反时间的有限窗口修正现象。将归一化的累积负载视为实证占据度量，有助于区分累积实证收敛与由拓扑结构引起的负载组织方式。在Erd?s–Rényi、Watts–Strogatz和Barabási–Albert网络集合中，通过尾部估计得到的稳定基尼系数与独立计算的介数中心和最短路径蒙特卡洛基准值一致，表明最终的路径负载目标是由路由规则和网络拓扑决定的。机制控制实验表明，在累积过程中普遍会出现数量级为一的有效指数，而最短路径组织则主要决定静态负载浓度、剩余预因子以及最终的负载与介数中心的相关性。通过基尼系数、归一化熵、归一化HHI指数和归一化Theil指数进行功能泛化，结合稳健性分析、模型比较和实证拓扑诊断，明确了所观察到的修正现象的有限时间范围。这些结果为区分基于路径的网络动态中的通用累积收敛效应与特定于拓扑的负载组织方式提供了机制分解框架。

引言：路由驱动的流量重分配是通信基础设施、交通系统、电网以及许多其他网络系统中的基本机制。当流量沿着最短或接近最短的路径传输时，负载不会在节点和链接之间均匀分布，而是那些结构上处于中心的节点往往会承担过大的传输流量。理解这种不平等现象是如何随时间形成的，对于评估拥堵风险、监测瞬时负载集中情况以及设计网络系统中的控制策略具有重要意义。众所周知，最短路径路由会引发与介数中心性密切相关的非均匀负载分布[1]、[2]、[3]。后续研究将这一视角扩展到加权网络和结构化网络，进一步强调了拓扑结构在决定负载浓度中的作用[4]。大量研究还探讨了复杂网络中的拥堵发生机制、路由容量以及流量优化问题[5]、[6]、[7]、[8]、[9]、[10]。与此同时，基于统计物理的方法也阐明了局部和全局路由规则如何影响拥堵阈值和传输效率[11]、[12]、[13]、[14]。最近的研究则继续关注具有拥堵感知能力、自适应能力、多层结构、非马尔可夫特性以及智能性的路由机制[15]、[16]、[17]、[18]、[19]、[20]、[21]。在最短路径渗透模型和路径渗透模型中，也研究了相关的基于路径的退化过程[22]、[23]。这些研究探讨了重复使用路径或移除路径如何引发连通性变化或资源消耗效应。而本文的模型则保持图拓扑结构不变，通过累积节点负载来实现负载增加，而不移除任何路径或边。两者的关联在于，微观层面的最短路径事件能够产生宏观层面的网络效应；不同之处在于，我们所观察的是有限时间内的负载不等性缓解现象，而非结构上的渗透现象。与静态负载分布和拥堵阈值相比，全球负载不等性的有限时间形成过程受到的关注相对较少。如果一个网络从均匀状态开始，然后不断受到源节点和目的节点需求的驱动，那么负载不等性曲线是如何趋向于由拓扑结构决定的稳定状态的？这种趋近是通过某个特征时间尺度实现的，还是通过一个没有单一指数松弛时间的广泛中间阶段实现的？当实证观测仅涵盖短暂的时间窗口而非完全稳定的运行状态时，这些问题尤为重要（见图1）。在没有单一特征时间尺度的系统中，常常会讨论类幂律型的松弛现象，包括在复杂结构上的异常扩散和随机游走现象[24]、[25]、[26]、[27]。然而，在累积最短路径负载作用下，即便源节点和目的节点的序列是独立采样的，且图拓扑结构保持不变，仍可能出现明显的代数残留项。因此，核心问题不仅在于是否能够观察到类幂律型的残留项，还在于究竟是何种机制产生了这种残留项，以及该现象中哪些部分真正依赖于拓扑结构。为了解答这个问题，我们将累积的负载向量视为一种实证路径负载分布，或者说是一种归一化的实证占据度量。这种表述方式将原本在单一松弛曲线中混为一谈的两种机制区分开来。累积实证收敛描述了重复采样路径如何使归一化负载曲线趋向于预期的路径负载目标，同时还会在非线性统计函数中产生类似反时间的有限时间修正现象。而由拓扑结构引起的负载组织则描述了最短路径结构如何决定目标负载曲线、负载浓度水平、剩余预因子、波动结构以及最终的负载与介数中心的相关性。这项工作的创新之处并不在于发现最短路径加载规则会带来与介数中心性相关的稳定负载分布，这其实是路由规则所预期的结果。其贡献在于分析了在有限的观测时间内，全局平衡和浓度函数是如何趋向于这种由拓扑结构决定的目标的，同时还将通用型有限样本收敛修正与特定于拓扑结构的静态负载组织区分开来。为此，本文将累积最短路径加载过程视为一种实证占据过程，将运算平台期的估算结果与独立的介数中心和最短路径蒙特卡洛模拟结果进行比较，同时通过机制控制、功能泛化测试、拟合窗口诊断、模型比较以及实证拓扑验证等方法，来确定有限时间路径负载松弛现象中哪些成分是累积实证收敛的通用结果，哪些成分则是由最短路径拓扑结构决定的。

章节节选：网络集合
我们研究了三种典型的网络集合：Erd?s–Rényi网络、Watts–Strogatz网络和Barabási–Albert网络。在主要的比较中，网络的大小固定为N=200，各网络集合的平均度数也大致相同。Erd?s–Rényi网络是根据连接概率p=kavg/(N?1)生成的，Watts–Strogatz网络则是根据重连概率β和kavg个最近邻环连接方式生成的，而Barabási–Albert网络则是根据附着参数m=kavg/2生成的。对于每一个网络实例，我们都会提取出其向由拓扑结构决定的稳定目标逐渐靠拢的有限时间松弛过程。图3总结了累积最短路径负载聚集现象及其稳定目标验证的主要特征。从零负载开始，基尼系数会迅速上升，随后趋向于一个非零的、与拓扑结构相关的数值。Barabási–Albert网络达到的稳定不等性程度最高，这与枢纽节点对路径流量的集中控制有关，而Erd?s–Rényi网络和Watts–Strogatz网络则达到较低的稳定水平。剩余项ΔG(t)=|G(t)?G∞|则呈现出一个近似线性的中间区域。

针对实证网络结构的纯拓扑测试
接下来，我们考察当将累积最短路径加载过程应用于实证网络结构时，是否会出现相同的有限时间诊断现象。我们选择了城市道路网络、电网拓扑结构以及通信网络作为研究对象。每个图都仅考虑其最大的连通分量，并将其视为无向且无权重的图。我们采用了相同的累积最短路径负载聚集规则、平台期估算方法以及拟合流程，无需针对不同拓扑结构进行特殊调整。

数据集

关于看似遵循某种标度规律的机制分解视角
这些研究结果为累积路径负载动态中的有限时间松弛现象提供了一种机制分解视角。累积最短路径加载会在一个有限的中间时间窗口内产生类似幂律型的剩余衰减现象，但只有将实证收敛机制与由拓扑结构决定的稳定目标区分开来，这种剩余项才有意义。仅凭单一的松弛曲线是无法判断该现象是否反映了某种特定于拓扑结构的普适标度规律。

结论
我们研究了复杂网络中实证路径负载分布的有限时间形成过程，即累积最短路径负载聚集现象。研究结果表明，全局负载函数中出现的类似代数型的修正现象以及与拓扑结构相关的稳定浓度，其实是同一过程的两个相关但不同的方面。有限时间修正主要与累积实证收敛现象有关，而路由规则和网络拓扑结构则决定了系统的稳定状态。

CRediT作者贡献声明
张坤：撰写——原始草稿、可视化、验证、软件工具、方法论、研究设计、形式分析、数据整理、概念构建。高华宇：资源提供。任天柱：项目管理。吴浩：撰写——审阅与编辑。曾冠文：撰写——审阅与编辑。

利益冲突声明
作者声明不存在任何可能影响本文研究成果的已知财务利益或个人关系。

张坤|高华宇|任天柱|吴浩|曾冠文
中国北京，北京航天系统工程研究所