🎯 **有向圈抑制网络一致性**：研究表明，在有向网络中引入有向圈会降低网络的一致性收敛速度。文章通过理论分析和模拟实验，定量地刻画了有向圈对网络动力学的影响，为理解复杂网络中的信息传播和同步过程提供了新的视角。

🔗 **独立有向圈的抑制作用由最小入度决定**：当网络中存在多个不相交的有向圈时，其对网络一致性的抑制作用仅由具有最小节点入度的那个有向圈决定。这意味着，即使存在其他较大的有向圈，网络整体的收敛速度也主要受制于那个“最薄弱”的环。

🔄 **相交有向圈加剧一致性衰减**：与不相交的有向圈不同，当多个有向圈发生交叉或嵌套时，它们对网络一致性的抑制作用会叠加。研究发现，相交的有向圈越多，网络的收敛速度越慢，这表明网络结构的复杂性（如嵌套和交叉）会显著影响其动力学行为。

🚀 **应用前景广阔**：本研究的结果不仅深化了对复杂网络结构与动力学关系的理解，还为解决实际工程问题提供了理论依据。其研究成果有望应用于人工智能、无人机群编队、机器学习算法优化以及生物医学等多个领域，例如在脑网络同步、智能电网控制等方面具有潜在价值。

原创 周进等 2025-11-02 14:30 北京

有向圈削弱网络一致性

论文题目：Uncovertherelationbetweenconsensusandtopologyofdirectednetwork: the minimum node in-degree of directed cycles

论文 doi: https://doi.org/10.1109/TAC.2025.3561190

发表期刊：IEEE Transactions on Automatic Control

有向网络中节点之间的连边是单向的，其在现实世界中广泛存在，如物理系统，生物集群系统和智能电网等。有向圈 (DirectedCycles) 为有向网络中的节点和有向边组成的闭合回路，其打破了无标度网络的层级化特性，进而引发系统自激振荡、记忆效应或动态稳定性突变。例如，基因调控网络中的反馈环路、神经网络中的递归连接均依赖有向圈实现功能。

又如，为了提高候鸟的整体飞行速度，鸟类通常以 V 形飞行，而不会向后看以避免在它们的相互作用拓扑中形成有向圈。而有向无环网络是一种不包含有向圈的有向网络， 如有向链,有向星链和有向二叉树等。有向圈的研究起源于图论中的强连通分量分析, 但其在复杂网络中扮演的角色远超出结构分类。

扩散模型是基于线性系统和拉普拉斯矩阵的复杂网络模型，其可以用于描述网络中的扩散过程。考虑一个包含生成树的有向动态网络:

其中xi为第i个网络节点在t时刻的状态，i=1,2,…,n；bij为第i个节点和第j个节点之间的耦合强度，如果i与 j之间有连接，则bij=1，否则bij=0。在图论中，对于一个具有n个节点的图，它的拉普拉斯矩阵定义为：L=D-A，其中 A是邻接矩阵，表示网络中节点的连接关系； D为度矩阵， 是一个对角矩阵。因此， 定义网络中所有节点的状态为x=[x1, x2,, xn]，那么方程可以重写为

即为通常的扩散模型的动力学方程。扩散模型可以用于描述多种扩散现象，例如，热量从高温区域流向低温区域，最终达到热平衡的热扩散过程，或者信息从拥有信息的节点传播到没有信息的节点，直至全网络信息均匀分布的信息扩散过程，以及疾病从感染节点传播到健康节点的疾病扩散。

有向网络拉普拉斯矩阵 L具有一个特征值 0，对应的特征向量为1n=（1, …,1) ，剩下的n-1个特征值都具有正实部。定义 L 的所有特征值为， 那么显然。其中次小特征值的实部是衡量网络动力学的关键指标，可以用于分析网络的同步能力、网络的扩散速度、观点趋于一致的速度、网络鲁棒性的下界。

那么有向圈如何影响有向网络的一致性呢？为此我们通过向有向无环网络上增加有向边形成有向圈，使用拉普拉斯矩阵次小特征值的实部来研究有向圈对网络一致性收敛速率的影响。

通常, 为了获得有向网络的拉普拉斯矩阵 (Laplacian) 的特征方程, 需要提前给出网络节点的排序。然而, 由于这种传统的方法容错率较低，很难将其使用于复杂的高维网络上。因此,为了有效获得有向网络的特征方程，我们使用了流图引理。

引理: 对于一个n阶方阵Q以及其对应的流图(流图节点数为n，节点间连边权重为方阵中对应元素) G , Q 的行列式可以由以下表达式直接给出

其中ρ表示G的子图的数量, 每个子图都由n个节点的非接触圈组成。ni和 Gi分别是第i个子图中有向圈的个数以及圈中每条有向边的连接增益的乘积(i…1,ρ)。

该引理实际上是一种计算方阵行列式的方法, 其新颖之处在于将行列式与网络结构相关联。

一个n阶矩阵确定了一个n个节点的图，矩阵中的元素表示图中节点之间的边权重。因此，引理有效地将计算方阵行列式转换为计算对应流图的非接触回路的连接增益。只要知道网络的所有节点的入度和有向圈的分布，就很容易通过引理得到拉普拉斯矩阵的特征方程。例如，图1显示了一个三阶拉普拉斯矩阵及其相应的流图,以及所有类型的子图。

图 1 一个三阶拉普拉斯矩阵及其对应流图的子图

先前的研究结果表明在有向链上增加反向边可以导致有向圈的产生，因此网络的拉普拉斯特征多项式变为两项之和，进而导致收敛速率降低。更一般地, 我们关心的是添加多条边形成的有向圈对一般有向无环网络收敛速率的影响，即有向圈对有向网络动力学的影响。

一、一个有向圈：网络的主收敛速度由有向圈的最小节点入度决定

考虑在有向无环网络上增加 m 条有向边形成了一个 p 个节点的有向圈，整个网络节点可以划分为以下三种类型：

TypeI.A 圈上m 条有向边指向的m 个节点(具有入度𝑑𝑖+ 1 的节点数为𝑤𝑖)对应于图 2 的紫色节点

TypeI.B 圈上m 条有向边未指向的p-m 个节点(具有入度ℎ𝑗的节点数为𝑐𝑗) 对应于图 2 的绿色节点

TypeII圈外n-p 个节点(具有入度𝑔𝑘的节点数为𝑒𝑘) 对应于图 2 的蓝色节点

图 2 有向星链网络中出现有向圈时，节点的划分。有向星链为多条有向链通过一个节点耦合形成的有向网络。

进而可以推导拉普拉斯矩阵的特征方程

原始有向无环网络特征方程：

网络具有一个有向圈的特征方程：

整理后为

与原始网络特征方程相比，p 个特征值发生了改变，正好对应着有向圈上节点的数量。为了研究这 p 个改变的特征值，考虑以下多项式方程

该多项式方程有且仅有一个正实根 𝑥 = 𝑥₁ ∈ (0,1)。

方程的其他根的实部都要小于正实根 𝑥₁。

正实根𝑥1依赖于参数𝑐0, 𝑑𝑖, 𝑤𝑖, ℎ𝑗, 𝑐𝑗, 可以表示为 𝑥1(𝑐0, 𝑑𝑖, 𝑤𝑖, ℎ𝑗, 𝑐𝑗)，其随着𝑐0的增加而增大, 随着𝑑𝑖, 𝑤𝑖, ℎ𝑗, 𝑐𝑗的增加而减小。

考虑变换，其中h0为有向圈上节点的最小入度，即有向圈上所有节点入度的最小值，如图 3 所示那么方程

变为

其满足多项式方程的 3 个结论，进而可以得出p 个改变的特征值中的最小特征值λmin∈(h0-1, h0) , 其随着 c0的增加而减小，而随着 di, wi, cj, hj的增加而增大。此外, λ2=min{λmin, g2} 为新网络的收敛速率。当 h0=1时, λ2=λmin∈(0,1)是代数重数为 1 的最小非零实根，即收敛速率。

结论：网络的主收敛速度由有向圈的最小节点入度决定，并且具有最小入度的节点越多, 主收敛速度越小, 具有非最小入度的节点越多, 主收敛速度越大。

图 3：两个不相交有向圈最小入度

二、同理，可推导得到多个相交有向圈和多个不相交有向圈对有向网络一致性的影响。

多个相交有向圈下，网络的特征方程

多个不相交有向圈：网络的主收敛速度由具有最小节点入度的那个有向圈决定。

多个不相交有向圈下，网络的特征方程

多个相交有向圈：相交有向圈越多，主收敛速度越小。

图 4：两个相交有向圈的最小入度

三、模拟结果

以两类有向网络为例来验证有向圈对有向网络一致性的抑制作用, 特别是相交圈和不相交圈的抑制效果。 图 5(I)展示了固定其他参数，λmin随着圈上具有最小入度h₀的节点数的增加而降低, 随着圈上具有最大节点入度 hmax的节点数的增加而增大。此外，λmin随着相交圈数的增加而降低 (见图 5(II))。图 7 为有向链和有向星链的节点达到一致的模拟图，从中可以看出, 有向圈减弱了这些有向网络的同步性能(同步时间变长), 并在同步过程中节点会形成同步簇。两个不相交的有向圈引起的抑制性是由节点数多的有向圈决定的, 而多个相交的有向圈进一步加强了对网络一致性的抑制作用。

图 5:（I）圈上具有最小入度的节点越多，收敛率越小 (II)相交圈越多，收敛率越小

图 6: 对于有向链：圈上最小入度节点(入度为 1 的节点)越多，也即反向边覆盖范围越广，相交圈越多意味着交叉的反向边越多。

图 7 ： 对于有向链网络: 具有 60 个节点的有向链网络随时间t的一致性模拟, 其中e_i=x_i-x₁,x_i是节点i的状态 (1≤i≤60): (a) 一个单独的有向链; (b) 具有一个节点数为 15 的有向圈的有向链; (c) 具有两个节点数分别为 15 和 22 的不相交有向圈的有向链; (d) 具有两个节点数分别为 15 和 22 的相交有向圈的有向链. 有向星链：具有 121 个节点的有向星链网络随时间 t的一致性模拟, 其包含三条链, 每条链上具有40个节点 (1≤i≤121): (a) 一个单独的有向星链; (b) 具有一个节点数为 9 的有向圈的有向星链，这个有向圈位于其中一条链上; (c) 具有两个节点数分别为 48 和 9 的不相交有向圈的有向星链, 这里大圈的节点在每条链上都分布着 16 个节点, 而小圈的节点分布在其中一条链上;(d) 具有四个节点数分别为 48,9,9 和 9 的不相交有向圈的有向星链, 这里大圈的节点在每条链上都分布着 16 个节点, 而三个小圈的节点分布在三条不同链上。

图 8：有向星链中，两个不相交有向圈和相交有向圈。不相交有向圈对网络一致性的抑制作用仅由“大圈”决定，而相交有向圈会进一步抑制有向网络的一致性。

有向圈为节点间的定向耦合, 高阶结构则为节点间的多体耦合, 这两种结构与传统孤立的点边结构存在显著区别。传统点边结构通常由节点个体属性或局部连接决定, 系统鲁棒性依赖单点或单边。而有向圈和高阶结构为网络模块结构 (ModularStructures)，更贴近真实系统的多维度交互和动态复杂性，弥补了传统点边模型在表达和分析上的局限性。从网络点和边到有向圈和高阶结构的研究如同从“字母”到“单词”的跃迁。有向圈和高阶结构赋予网络更丰富的语义, 使其能描述复杂系统的涌现行为与适应性。例如，社交网络中传统边仅能表示两人互动，而超边可刻画“微信群”的群体决策行为，有向圈则可解释谣言传播中的回声室效应。因此，研究网络的“模块化”结构可以推动网络科学从还原论向整体论范式转变。

本项工作不仅为含有向圈的复杂网络一致性提供了新的判断准则，预期在工程控制、生物医学、人工智能、机器学习与算法优化等领域有着广泛的应用前景，譬如脑网络、无人机群的编队、智能电网、意见动力学（“回声室效应”）等方面提供了新的手段。本项研究将进一步向高阶有向圈（如超图中的有向环结构）推广。

推荐阅读

1. 吴俊团队原创：复杂网络瓦解问题研究进展与展望

2. 网络瓦解的三大问题都是什么？｜附42篇文献阅读清单

3. 自然 · 物理评论：从网络鲁棒性到网络瓦解问题

4. 系统科学前沿十讲：探究复杂世界演变背后的规则（二）

5. 集智学园精品课程免费开放，解锁系统科学与 AI 新世界

6. 高考分数只是张入场券，你的科研冒险在这里启航！

点击“阅读原文”，报名读书会

阅读原文

跳转微信打开