反向连边在大型分层网络中的影响

曹浩森 ,  胡斌斌 ,  莫小雨 ,  陈都鑫 ,  高建喜 ,  袁烨 ,  陈关荣 ,  Tamás Vicsek ,  管晓宏 ,  张海涛

工程（英文） ›› 2024, Vol. 36 ›› Issue (5) : 258 -267.

PDF (4416KB)
工程（英文） ›› 2024, Vol. 36 ›› Issue (5) : 258 -267. DOI: 10.1016/j.eng.2023.06.011
研究论文

反向连边在大型分层网络中的影响

作者信息 +

The Immense Impact of Reverse Edges on Large Hierarchical Networks

Author information +
文章历史 +
PDF (4521K)

摘要

分层网络经常出现在生物集群、基因网络和人造系统中，如多机器人网络、无人系统网络、智能电网、风力发电场网络等。大型有向分层网络的结构通常会受到反向连边的重大影响，即连接低层级与高层级节点的逆层次结构连边，比如鸟群中掉队个体的叫声或社会群体中低级别个体回馈到较高级别个体的意见。这项研究揭示了对于大多数真实背景的大规模分层网络，大部分反向连边不会影响整个网络的同步过程；同步过程仅沿特定路径受到这些反向连边中一小部分的影响。更令人惊讶的是，单个有效的反向连边可以使大型分层网络的同步速度减慢超过60%。这类边造成的影响并不取决于网络本身的大小，而仅取决于反向连边涉及的子网络的平均入度。绝大多数活跃的反向连边都会对分层网络的信息流产生某种形式的“集束”效应，从而减慢同步过程。这一发现将会增进对自然界、社会和工程中广泛存在的分层网络中反向连边作用的理解，并有助于精确调控这些网络的同步节奏。本文的研究还提出了一种能有效攻击分层网络的方法，即向其中添加恶意的反向连边，同时通过筛选出特定的一小部分易受攻击的节点为保护网络提供指导。

Abstract

Hierarchical networks are frequently encountered in animal groups, gene networks, and artificial engineering systems such as multiple robots, unmanned vehicle systems, smart grids, wind farm networks, and so forth. The structure of a large directed hierarchical network is often strongly influenced by reverse edges from lower- to higher-level nodes, such as lagging birds’ howl in a flock or the opinions of lower-level individuals feeding back to higher-level ones in a social group. This study reveals that, for most large-scale real hierarchical networks, the majority of the reverse edges do not affect the synchronization process of the entire network; the synchronization process is influenced only by a small part of these reverse edges along specific paths. More surprisingly, a single effective reverse edge can slow down the synchronization of a huge hierarchical network by over 60%. The effect of such edges depends not on the network size but only on the average in-degree of the involved subnetwork. The overwhelming majority of active reverse edges turn out to have some kind of “bunching” effect on the information flows of hierarchical networks, which slows down synchronization processes. This finding refines the current understanding of the role of reverse edges in many natural, social, and engineering hierarchical networks, which might be beneficial for precisely tuning the synchronization rhythms of these networks. Our study also proposes an effective way to attack a hierarchical network by adding a malicious reverse edge to it and provides some guidance for protecting a network by screening out the specific small proportion of vulnerable nodes.

关键词

同步性 / 大型分层网络 / 反向连边 / 信息流 / 复杂网络

Key words

Synchronizability / Large hierarchical networks / Reverse edges / Information flows / Complex networks

Highlight

● Propose an efficient algorithm to screen out active reverse edges.

● Quantitively analyze the impact of reverse edge on network synchronization

● A physical model is given to explain the impact machanism

● The algorithm and mechanism are verified by experiments of USVs groups.

引用本文

引用格式 ▾
曹浩森,胡斌斌,莫小雨,陈都鑫,高建喜,袁烨,陈关荣,Tamás Vicsek,管晓宏,张海涛. 反向连边在大型分层网络中的影响[J]. 工程（英文）, 2024, 36(5): 258-267 DOI:10.1016/j.eng.2023.06.011

登录浏览全文

4963

注册一个新账户 忘记密码

1 引言

同步是复杂网络中必不可少的协调行为，通常在物理学、生物学、生态学和气候学等领域遇到[1‒4]。也就是说，所有网络节点都对感兴趣的某些特征达成一致意见，如位置、速度、倾向等，或者周期性地以相同的节奏、相位和振幅移动。同步现象具有生物进化上的优势，成员通过群体保护和生存、配偶选择以及觅食等形式获得利益[5]。典型例子包括有组织的鱼群避开捕食者的攻击[6‒7]和格式化的鸟群节省动能[8]。在智能电力网络中经常遇到的典型同步过程是匹配不同的发电机以获得统一的频率和角度。事实上，对于分布式发电系统来说，高效的电网同步仍然是一个具有挑战性的问题。自主协调的无线传感器、爆发性放电神经元、节拍匹配的化学振子以及频率锁定的发电机等都可以观察到丰富的自发同步现象。

类比于其他形式的集体现象，同步强烈依赖于底层交互网络的拓扑特性[9]。由于网络同步的重要意义，近些年有大量工作[10‒13]借助生物实验、真实网络数据、统计物理学理论以及数学/系统科学分析工具，探索了智能体之间的拓扑连接和网络同步性之间的关系。到目前为止，由于分层网络在自然界中的广泛存在，人们普遍认为，分层网络的同步受到从较低级节点到较高级节点的额外反向连边的明显减速或抑制作用（一种示例的网络分层见附录A中的图S1）。例如，昼夜生物钟使用相互交织的转录反馈环路（或反向连边）作为同步生物过程的分子机制。夜晚复合物基因的负反向连边（即自调节）构成了生物钟的夜晚循环，它抑制了清晨基因[14]。然而，我们的研究证明了绝大多数额外的反向连边根本不能影响同步节奏，利用反向连边调控同步仍具有理论难度。更有趣的是，一个庞大网络的同步速度可能被仅仅一条越过两个节点的反向连边大幅减速超过60%。例如，在现代电力系统中，同步的中断可能导致发电机的故障和电网的停电，正如1996年西部美国网络[15]、2003年意大利-瑞士网络[16]和2003年北美网络[17]中观察到的那样，进而导致电网的连锁灾难性失效。在这些大规模停电期间，观察到了巨大的反向功率流和过度的相角不同步，这些都被认为是上述系统崩溃的关键因素[17]。本研究的目的是探讨反向连边在丰富的自然、社会和工程分层网络中的作用。我们的调查提供了一些结论用来分析如何定量调节同步节奏，反之，也能指导保护分层网络免受自下而上的额外连边而遭受攻击。

为了揭示反向连边的作用，我们忽略了分层网络的环路，而是专注于有向无环网络。分层网络通常用来描述不同系统之间的因果或层次关系；相应地，层次结构有许多种定义[18‒19]。例如，迁徙鸟群的领导者-跟随者结构[20‒22]在V形飞行时形成了分层通信网络[23]。智能电网中的发电站、变电站、负载等不同层次的组成部分形成一个网络，其中有向功率或信息流连接着网络组件。此外，在多载具编队中，只有少数车辆是有人驾驶员，充当领导者，而其余的是无人驾驶的跟随者。每辆无人驾驶车辆通过板载传感器（如摄像头）跟随其前方的车辆，因此通信网络形成了一个分层网络[24]。

分层网络的典型拓扑结构包括链、树、网格和更一般的单根分层图。广泛存在的生物分层网络示例包括迁徙鸟群[20‒23]、哺乳动物群体[25]，甚至微生物酵母调控网络和基因本体论（GO）[26‒27]。此外，还有丰富的工业和工程分层网络，如供水网络[28]、风力发电场[29]、智能电网[30]、低级程序优化中的指令调度[31]、无人驾驶车辆编队[32]、组合电路[33]、编译器设计[34]、数据流编程语言[35]和高效搜索算法[36]。文献中甚至包含了从生物学[37‒39]、神经科学[40]、遗传学[41]到经济学[42]等领域的大规模分层网络实例。

分层网络的性能和特性受到额外反向连边的影响，有时候这些影响会显著影响整个网络的动态。在社交网络中，从较低级别的个体到领导者的反馈意见有利于优化群体决策或民主。在电力网络中，通过添加链接产生的冗余循环对于保护脆弱节点及增强网络连接性和稳健性是实用的。但另一方面，在所谓的Braess悖论中，添加新链接可能不会促进，反而破坏特定网络的同步，导致停电或交通拥堵[43‒44]。在许多自然分层网络中，如鸽群[22]和马群[45]，跟随者可能探测到食物资源、新栖息地或者提示捕食者的线索。因此，自下而上的紧急信息流，即反向连边有助于领导者为整个网络做出更好的决策。在供应链中，从零售商和客户的反馈对于生产商和供应商来说是不可或缺的，以增强供应效率。因此，这些现实生活中的情况激发了对大量分层网络中反向连边作用的研究。

为此，我们对几个典型的中等或大规模真实分层网络进行了广泛调查。对于其中的一些情况，出乎意料的是，大量的分析和数值研究揭示了绝大多数可能的反向连边根本不影响整个分层网络，因此我们将它们称为沉默反向连边。例如，对于一个由2373个节点/ 20 812条边/ 89级层次比特币网络切片[46]，沉默反向连边的比例超过了64.48%；在另一个更密集的巨型29 383个节点/ 56 377条边/ 17级分层网络（即GO [26‒27]），这一比例高达99.92%。相比之下，如果反向连边对同步过程产生影响，我们将其标记为有效的。我们已经确定了一些特定类别的网络结构，其中可以迅速提取出有效的反向连边。

接下来，我们重点关注反向连边在真实自然/社会/工程分层网络中的数量。再次出乎意料的是，反向连边的影响结果与它们的位置或网络规模无关。相反，它们的影响仅仅由包含额外反向连边的局部子网络决定，特别是着陆节点（即反向连边的结束节点）的入度。更准确地说，较大的入度着陆节点（即反向连边的结束节点）意味着较慢的同步。其根本原因是将其他分支的更多信息流合并到着陆节点有助于稀释反向连边的影响。

从科学角度看，本研究扩展了我们对分层网络拓扑的认识，使得可以准确地筛选出极少数在丰富的大规模分层网络中具有显著影响的活跃反向连边。在工程应用方面，本研究可能为通过精确定位额外反向连边来保护、攻击或调节大规模自然/社会/工程分层网络提供一些启示。更具体地说，这项工作揭示了通过在庞大网络中精确放置少量特定的恶意反向连边来攻击网络（即减慢其同步过程）的有效方法。相反，我们的工作还为通过筛选出对反向连边攻击脆弱，但通常构成网络路径极小比例的特定路径来保护网络提供了指导。简而言之，我们的论文为揭示分层网络原理在真实自然、社会和工程分层网络系统的各种应用方向铺平了道路。

2 实验和方法

2.1 实验

为了能够在实证实验中量化反向连边在分层网络中的作用，利用一个包含17艘小型无人艇的集群来模拟马群网络[47]的同步。因此，为简化起见，通过仔细调整运动学模型，本文将无人艇的运动刻画为一阶动力学系统。通过这种方式，无人艇集群在航行方向上的同步性能可以得到量化，并相应地验证反向连边在同步速度上的调节作用。

如附录A中的图S2至图S5所示，本实验所采用的无人艇集群平台的组成为：17艘30 cm长的小型无人艇、一个运动捕捉模块、一个监控和控制模块以及一个室内水池。其中，实验所使用的小型无人艇具体为HUSTER03型，长300 mm，高60 mm。每艘无人艇配备两个直流电机（R385型）、两根长150 mm的传动轴、两个速度编码（Freescale Mini256ABC型）、一个2.4 GHz无线模块（NRF24L01型）、三个F5红外发射器、一个LED指示灯、一个锂聚合物电池（Youme Su27型）和一个嵌入式微型控制器（STM32F103CBT6型）。其中无人艇的微控制器对电机、速度编码器、无线模块和红外发射器进行控制。

每艘无人艇仅接受邻居无人艇的朝向信息，从而分布式地计算自身的航向同步控制信号。具体地，定义 φ i ∈ 0 ,   2 π , i = 1 ,   2 ,    . . . ,   17为第i艘无人艇的航向。通信拓扑为有向无环图的无人艇集群内，所有无人艇航向将收敛至根节点对应的领导艇初始状态。不失一般性，规定领导艇为1号艇，因此无人艇集群达到航向同步的条件为：任意一条无人艇的航向与领导艇的航向差小于阈值0.05rad，即 ∀ i , φ i - φ 1 ≤ 0.05。

如图2（a）和（b）以及附录A中的图S6所示，再实验过程中，所有无人艇初始随机分布在矩形区域 - 3000,1000 × - 1000,1000  mm处，初始速度为零。然后，所有无人艇的移动方向被同步了起来。为了更生动地展示反向连边的影响，我们在三种情景下进行了实验，即：①没有反向连边，②一个沉默反向连边（17→11），③一个活跃反向连边（17→12），如图2（c）~（e）所示。为了计算同步过程的收敛时间，每个都取三次独立运行的平均值。观察到一个活跃反向连边[图2（e）红色轨迹端点]有效地减慢了同步速度，而其他情况则没有影响它[图2（c）和（d）绿色轨迹端点]。在其他情景下，同步过程的比较见附录A中的图S7。

2.2 算法

考虑一个具有N个节点的单根分层网络 G，并且处于拓扑排序下。因此具有一个下三角的拉普拉斯矩阵 L o ∈ R N × N，其中 R表示实数集，假设本文考虑的所有有向图都是无权重的。令 𝒱表示图 G的节点集， ℋ ( ν ) ∈ R + , ν ∈ 𝒱表示节点 ν所在的网络层次。定义函数 ℋ ( ν )将节点 v映射到它距离根节点的最长路径长度上，如附录A中的图S1和第S1节所示。考虑添加从节点 𝓁到 ℏ的反向连边，跨度为 r = ℋ ( 𝓁 ) - ℋ ( ℏ ) > 0 ; ℏ , 𝓁 ∈ 𝒱 , ℏ ≠ r o o t，其中“root”表示图 G的根节点。将这条反向连边记为 ( ℏ , 𝓁 )，它唯一确定了图 G的一个子图 G 1，该子图包含节点 ℏ , 𝓁以及从节点 𝓁到 ℏ的所有路径。令 Ω为子图 G 1的节点集，以及 Ω的基数为 n : = Ω。因此，一旦反向连边 ( ℏ , 𝓁 )添加后，图 G的拉普拉斯矩阵 L o将变为 L o ¯。子图 G 1对应 L o ¯对角线上的一个块矩阵 L = [ l i , j ] ∈ R n × n，其中， l是矩阵 L的元素。即

L ¯ o = L 1 0 0 * L 0 * * L 2
L = l 1,1 0 ⋯ ⋯ - 1 - 1 l 2,2 0 ⋯ 0 ⋮ ⋱ ⋱ ⋱ 0 ⋯ ⋯ ⋯ l n - 1 , n - 1 0 ⋯ ⋯ ⋯ - 1 l n , n

式中，方阵 L包含了从节点 l到 ℏ的所有路径。因此，仅根据涉及的子网络 G 1中节点的入度筛选出有效反向连边，便成了一个有趣的问题，以避免对巨大拉普拉斯矩阵进行耗时的谱计算。为此，我们设计了有效反向连边搜索算法1，该算法由两个步骤组成：路径搜索和节点搜索。

步骤1：路径搜索。在子图 G 1中搜索从节点 𝓁到节点 ℏ的路径。将 Γ i表示为第 i条这样的路径，将 c表示为这样的路径数。那么， c ≥ 1是确定有效反向连边的必要条件。

步骤2：节点搜索。在子图 G 1中搜索中部集束和漏斗集束的节点，对应于算法1中的三个条件。正如在第3.2节中讨论的那样，这些节点指示了 G 1中的信息流，并确定了反向连边的有效性。

通过算法1（更多细节见附录A中的第S2节），可以在不计算巨大矩阵 L o的特征值的情况下，筛选出真实网络中超过99.4%的有效反向连边（见第3.3节）。本质上，与经典QR算法相比，计算和评估判别矩阵的计算复杂度已经从 𝒪   ( N 3 )减少到了 𝒪   ( N ) [48]。然而，剩下的少数有效反向连边（≤0.6%）带来了分析困难，这是由 G 1中的入度赋予的外部和内部信息流之间复杂的平衡所致。幸运的是，在大多数应用场景中，筛选出绝大多数有效反向连边已经能够满足应用需求。

3 结论

3.1 分层网络中有效反向连边占比较小

分层广泛存在于自然生物群体、基因网络和工程系统中。自然地，考虑到添加反向连边可能会向原网络中加入环路，从而阻碍同步过程。反向信息流的情况有时会带来应用价值，也可能引起严重甚至灾难性的后果，例如，壳式换热器中的液体逆流或行人逆流引发交通从自由状态向拥挤状态的转变。因此，从网络视角研究逆流效应至关重要。直觉上，大多数从低层到高层的反向连边会影响分层网络的同步。然而，通过穷尽所有可能的反向连边，我们发现其中只有少数几条实际上能够改变大量分层网络的同步节奏。

首先，在没有环路的分层网络中，反向连边被定义为从低层到高层的连接。本文将每个节点的层级数定义为该节点到根节点的最远距离。我们以一个代表性的分层拓扑——马群的互通网络为例进行说明，如图1所示。量化研究反向的马群交流对于研究真实马群具有重要意义。为此，我们使用了17艘小型无人艇来模拟马群的同步现象，其中每艘船对应马群中的一个小团体，并与其前方的马群（即直接的领导者）保持运动上的一致。

如图2（a）所示，在每次实验中，无人艇最初随机分布在一个水池中。如图2（b）所示，基于图1所示的拓扑结构，无人艇间通过通信，最终实现航向的同步。值得注意的是，我们记录并发现了拥有不同反向连边的艇群达到同步的时间间隔不同。这样，不同反向连边的作用就可以进行量化比较。有关实验的更多详细信息请参阅附录A中的第S3节。

意外的是，从图2可以观察到，对于所研究的小型马群拓扑结构，在所有可能的反向连边中只有63%能够影响同步过程[图2（e）中的反向连边17→12需要18.0 s，而图2（c）中的需要7.5 s]，我们将这63%反向连边标记为活跃的反向连边。剩下的37%的反向连边是沉默的，因为它们根本不影响同步速度[同步时间仍为7.5 s，如图2（c）和（d）中的沉默反向连边17→11 vs 7.5 s]。

活跃的反向连边似乎占据了所有可能的反向连边的大多数。然而，通过对真实分层网络进行深入研究，似乎活跃边的比例随着网络规模的增加而急剧减少。以一个典型的巨型分层网络，即由29 323个节点和56 377条边组成的分层有向图“GO”为例[26‒27]，根据对所有可能的反向连边（超过3.8亿条）同步过程的详细分析，其中只有不到0.08%是活跃的。为了深入了解这一现象，我们必须对能够调节相应网络动力学和同步节奏的反向连边类型有进一步的了解。在这一点上，这一节需要解决三个基本问题：①每个分层网络中有多少活跃的反向连边？②如何高效准确地定位它们？③活跃的反向连边能够多大程度地减慢同步过程？

然而，由于水面无法保持绝对静止，在每次独立运行实验中很难确保所有17艘无人艇的初始状态是相同的。因为一旦调整了一艘艇的方向和位置，产生的兴波将干扰其它艇。因此，我们使每次独立运行中无人艇的初始状态尽可能随机分布。图3中给出了在理想环境中对活跃反向连边减速效应的模拟。考虑一阶积分器的动力学 x ˙ = - L o x，其中， x表示系统的状态。对于相同的初始状态，具有沉默和活跃反向连边的艇群拓扑同步过程显然是不同的。

3.2 活跃反向连边的位置

为了全面准确地定位各种分层网络中的活跃反向连边，需要一个指标来量化同步速度。文献中普遍接受的一个指标是Fiedler值（即图拉普拉斯算子的第二小特征值实部），因为它量化了图的连接强度。重要的是，可以从图4 Pearson相关性测试中的相关系数和显著性p值中观察到该指标的量化能力[49]。这意味着同步速度与具有马群拓扑结构的实际17艘无人艇网络代数连通性密切相关。因此，我们采用Fiedler值作为量化网络同步速度的指标，从这个意义上讲，指标越小，网络达到同步的速度越慢。

对反向连边的研究中的一个重要问题是，什么样的额外反向连边能够改变 λ 2？为了解决这个问题，考虑实际实验数据，观察到如果额外反向连边没有形成新的环路，那么这条边将是无效的。如图1所示，沉默额外反向连边16→13（绿色虚线箭头）无法形成任何新的环路。此外，在大多数情况下，拉普拉斯谱保持不变，因为整个网络的原始拉普拉斯可以通过简单地改变节点顺序重新写成下三角。换句话说，形成一个新的环路是活跃反向连边的必要条件（但不是充分条件）。为了说明这个问题，以图1中的两条反向连边14→13（红色虚线箭头）和13→10（蓝色虚线箭头）为例。两者都形成了环路，但前者是活跃的，而后者不是。因此，形成新的环路并不能保证反向连边是活跃的，准确定位活跃反向连边仍然是一个具有挑战性的问题。

为此，考虑一个拓扑排序的N节点单根分层网络 G，其拉普拉斯矩阵为下三角。假设存在至少一条从节点 ℏ到节点 l的路径，该路径形成一个由节点组成的子网络 G 1。我们的研究发现，子网络 G 1中节点的入度显著影响附加逆边的有效性（详见第2节）。特别是在子网络 G 1中，节点的入度可以根据子网络和补集中的起始节点分别划分为内部和外部入度。因此，如果子网络 G 1中的所有节点至少有一个外部入度，根据Gershgorin圆盘定理，反向连边肯定不能影响网络的同步过程，因为代数连通性 λ 2大于或等于1。因此，如果子网络 G 1中至少有一个节点没有外部入度，就有必要进一步判断是否是一条活跃的反向连边。

为了说明活跃反向连边的影响，可以将节点的入度看成此点的信息通道宽度，并且宽度沿信息流变化。这种现象让人联想到一种聚束效应，如图5（a）所示，这说明存在一些节点收紧了信息通道，从而激活了反向连边的逆流效应。我们的研究表明，通常存在两种聚束效应，更确切地说，是中部聚束和漏斗聚束。如图5（b）所示，中部聚束表示信息通道被至少一个内部入度仅为1的节点（即流节点）收紧。因此，由于存在最窄通道宽度为1，反向连边的逆流影响没有被稀释。然而，对中部聚束的进一步分析表明，如果存在至少一个内部入度仅为1的节点，而子网络中所有其他节点的外部入度不超过1，那么尽管存在外部入度，反向连边的逆流影响不会完全被有限的外部节点中和。

如图5（c）所示，漏斗聚束现象表示信息通道在子网络 G 1中先被拉伸，然后突然变窄。在这种情况下，上层节点具有的外部入度不可忽略，而底层节点则仅具有内部入度。此时，反向连边的逆流影响也不会被完全中和。通过上述聚集效应分析，对于检测活跃反向连边算法的更多详细信息，请参见算法1。

为了验证所提出的算法1，我们在前文提到的巨大有向图（GO）上进行了实验。该有向图根据节点与单根的距离被分为17个层级。可以观察到，在379 260 333个可能的逆边中，超过99.5%的活跃反向连边可以在不进行任何额外计算的情况下被算法1迅速筛选出来。剩下的0.5%反向连边可以通过直接计算它们的Fiedler值来评估，即相应判别矩阵特征值的最小实部（判别矩阵的定义见附录A中的S1部分）。

3.3 活跃反向连边对同步过程的减速程度

了解活跃反向连边的位置后，可以通过仔细调整少量活跃反向连边的比例，从而微调网络的同步速度；或者相反，着重保护少数活跃反向连边免受外部攻击。然而，活跃反向连边对同步过程的减速程度尚不清楚。首先为了简化该问题，从链式网络开始。一个仅跨越一个节点的活跃反向连边可以将同步速度减少超过61.8%，但这显然不是最大的减速效果，实验发现跨越更多链节点有助于进一步减缓同步速度。

接下来，我们进一步定量研究活跃反向连边对16种具有代表性的实际分层网络（从几十个节点到数万个节点）的影响。这些网络中活跃反向连边对同步过程的定量影响如图6所示，并在表1中总结。我们使用减少百分比（PR）和平均减少百分比（APR）来衡量逆边对收敛速度的影响程度，即 P R = λ 2 - λ ˜ 2 / λ 2，其中 λ 2和 λ ˜ 2分别表示添加该逆边前后网络的Fiedler值。APR是具有相同平均入度 d ¯ i n和跨越范围 r的逆边PR的平均值。

可以观察到，除了马群网络[图6（b）]外，所有网络中有效逆边（ERLs）的比例都不超过36%。有趣的是，活跃反向连边对同步过程的影响与网络规模或其特定位置无关。相反，这种影响仅由包含附加活跃反向连边的子网络 G 1决定。换句话说，除子网络 G 1外的任何其他边或节点的传输能力或同步过程完全不受影响。这是由于分层网络的拉普拉斯矩阵 L是一个下三角矩阵。只受活跃反向连边影响的相关子拉普拉斯矩阵见附录A中的S1部分。

需要注意的是，如图6所示，仅一个活跃反向连边就可以突然将收敛速度降低超过60%，从而负面影响网络的同步过程，无论网络有多大（如巨大的GO图）。此外，减速效果仅受子网络中平均入度的影响，即平均入度越小，同步速度越慢。这种现象可以解释为活跃反向连边的影响被合并到相同子图的其他分支所稀释。这类似于多个小溪汇入主流时，每个支流的影响都被稀释。这一观察对于通过调节节点的入度来微调网络的同步过程具有重要意义。

因此，通过使用算法1，可以精确搜索出少量存在的活跃反向连边，并通过集中关注一个更小的子网络来量化反向连边影响的强度。这些发现完善了我们对分层网络的认识，并使数学分析一些规则网络成为现实。

在这里，一个引人注目的事实是：当活跃反向连边的终止节点的入度为1时，同步减速率的最小值与黄金比例 λ * = 1 - ( 5 - 1 ) / 2 ≈ 0.382相关；当活跃反向连边的跨越范围也为1时，同步减速率的最大值与黄金比例相关。这是因为改变后的特征值由一个显式特征多项式决定，该多项式可以分解为一个具有黄金比例解的二次多项式 λ 2 - λ - 1 = 0。从应用的角度来看，所揭示的代数连通性 λ 2的黄金比例是一种研究网络的最佳谱值，它也可能为网络系统提供能量成本和最佳移动轨迹之间的平衡点[50]。

4 讨论

反向连边通常代表着从低层节点到高层节点的反馈，在自然、社会、经济和工程等背景的分层网络中十分常见，并发挥着重要作用。网络集体中的实体相互合作，共同推动系统达到同步的稳定状态[6]。这些反向连边可能代表着动物群体中的一般个体发送的关于食物、捕食者或栖息地的信息，社交网络中的观点反馈，分布式发电系统中的电力环路，微观细胞组织中人工添加的生物信号连接，宏观协同机器人系统的信号反馈等现实意义。在这些普遍存在的实际系统中，单条反向连边的显著影响已经被广泛认同。

而本文开展了具体的无人艇集群同步实验以及基于真实网络拓扑的大量数值仿真，结合数学分析得出，反向连边的作用仅取决于它跨过的子网络。只有当反向连边位于一些特殊位置，即满足特定的“聚束条件”，才能影响网络在收敛速度上的同步性。这样的子网络可以通过微调的子网络参数（如平均入度）来仔细调整网络同步过程的主导收敛速率 λ 2 ( L )，从而影响整个规模（无论大小）的有向网络同步节奏。这种网络同步和协调的最佳频谱有助于优化网络性能，并平衡网络化系统（如原子核[50]）的能量成本和最佳轨道。

目前，单条反向连边的影响已经得到较充分的讨论，关于多条反向连边的情形也有一些阶段性发现。仿真中发现如果两条有效反向连边以嵌套的形式添加到有向图中，由于它们跨过的子网络相互重叠，会起到更强的“聚束”效应，使得同步过程的减速效果来得更加强烈。这一点在链式网络中更加明显，向其添加多条有效反向连边后，同步速度减小的程度与所有嵌套反向连边跨度的总和呈正相关，并且可以扩展到一般有向图中特殊的“茎”结构[51]。如果添加的反向连边对应的子网络没有共同的节点，则具有最显著效果的反向连边起主导作用。但对于子网络重叠的反向连边，仍未有规律性的观察结果，这是由于这些反向连边的跨域范围、入度、有向路径之间存在复杂的耦合关系，缺乏专门的分析工具进行进一步研究。总体来说，向一般的有向无环网络添加两条及以上的反向连边，所产生的同步过程影响仍难以量化和建模。而对于非线性的动态网络化系统，线性化处理是使系统与当前分析框架兼容的可行方法。然而，网络结构、初始状态和非线性形式对同步能力的影响机制目前还远未被充分揭示。

从科学的角度，本研究细化和增强了现有关于逆边作用的知识。例如，我们的研究显示，大多数大型分层网络的反向连边是无效的，因为它们完全不影响网络的同步过程和协同能力。不仅如此，我们给出了搜索少量存在的活跃反向连边并量化它们对同步性能的影响的方法和原理。从工程应用的角度来看，本研究通过搜索具有聚束效应（如“茎”节点）的子网络，为攻击或防御大规模分层网络提供了启示。

5 结论

在这项工作中，我们着重研究了反向连边的添加对分层网络同步过程的影响。研究发现，无论网络规模如何，只有少数活跃反向连边由于其对所涉及信息流的聚束效应，可以影响到网络的同步过程。这些活跃反向连边仅一条就可以将大型分层网络的同步速度降低超过60%，并且这种减速效果的程度高度依赖于跨越子网络的平均入度。根据聚束效应的理论模型，本文还提出并验证了一种高精度、高效率的活跃反向连边搜索算法。此外，进行了无人艇集群航向同步实验和对实际分层网络的大量模拟，实验和仿真结果都支持这些发现和分析。本研究可能为保护、攻击或调节整个分层网络的同步过程提供了一种新的方法，如对多机器人系统、智能电网或无线传感器网络，只需通过调整少数的活跃反向连边即可。

参考文献

原文顺序 | 出版日期 | 本文引用
[1]

Strogatz SH. Exploring complex networks. Nature 2001;410(6825):268‒76. . 10.1038/35065725
[2]

Schöll E. Chaos control sets the pace. Nat Phys 2010;6(3):161‒2. . 10.1038/nphys1611
[3]

Albert R, Barabási AL. Statistical mechanics of complex networks. Rev Mod Phys 2002;74(1):47‒97. . 10.1103/revmodphys.74.47
[4]

Newman MEJ. The structure and function of complex networks. SIAM Rev 2003;45(2):167‒256. . 10.1137/s003614450342480
[5]

Parrish JK, Edelstein-Keshet L. Complexity, pattern, and evolutionary trade-offs in animal aggregation. Science 1999;284(5411):99‒101. . 10.1126/science.284.5411.99
[6]

Vicsek T, Zafeiris A. Collective motion. Phys Rep 2012;517(3‒4):71‒140.
[7]

Ioannou CC, Guttal V, Couzin ID. Predatory fish select for coordinated collective motion in virtual prey. Science 2012;337(6099):1212‒5. . 10.1126/science.1218919
[8]

Weimerskirch H, Martin J, Clerquin Y, Alexandre P, Jiraskova S. Energy saving in flight formation. Nature 2001;413(6857):697‒8. . 10.1038/35099670
[9]

Sawicki J, Omelchenko I, Zakharova A, Schöll E. Chimera states in complex networks: interplay of fractal topology and delay. Eur Phys J Spec Top 2017;226:1883‒92. . 10.1140/epjst/e2017-70036-8
[10]

Nishikawa T, Motter AE. Synchronization is optimal in nondiagonalizable networks. Phys Rev E 2006;73(6):065106. . 10.1103/physreve.73.065106
[11]

Nishikawa T, Motter AE. Maximum performance at minimum cost in network synchronization. Physica D 2006;224(1‒2):77‒89.
[12]

Sorrentino F. Effects of the network structural properties on its controllability. Chaos 2007;17(3):033101. . 10.1063/1.2743098
[13]

Li L, Jia QS, Wang H, Yuan R, Guan X. A systematic method for network topology reconfiguration with limited link additions. J Netw Comput Appl 2012;35(6):1979‒89. . 10.1016/j.jnca.2012.07.021
[14]

Pokhilko A, Fernández AP, Edwards KD, Southern MM, Halliday KJ, Millar AJ. The clock gene circuit in Arabidopsis includes a repressilator with additional feedback loops. Mol Syst Biol 2012;8(1):574. . 10.1038/msb.2012.6
[15]

Verma R. Aanalysis of 1996 western American electric blackouts. In: Proceedings of Bulk Power System Dynamics and Control-VI; 2004 Aug 22 27; Cortina d’Ampezzo, Italy; 2004.
[16]

Berizzi A. The Italian 2003 blackout. In: Proceedings of IEEE Power Engineering Society General Meeting; 2004 Jun 6‒10; Denver, CO, USA; 2004. . 10.1109/mpae.2004.1293595
[17]

Andersson G, Donalek P, Farmer R, Hatziargyriou N, Kamwa I, Kundur P, et al. Causes of the 2003 major grid blackouts in North America and Europe, and recommended means to improve system dynamic performance. IEEE Trans Power Syst 2005;20(4):1922‒8. . 10.1109/tpwrs.2005.857942
[18]

Liu YY, Slotine JJ, Barabási AL. Control centrality and hierarchical structure in complex networks. PLoS ONE 2012;7(9):e44459. . 10.1371/journal.pone.0044459
[19]

Iudice FL, Garofalo F, De Lellis P. Bounded partial pinning control of network dynamical systems. IEEE Trans Control Netw Syst 2023;10(1):238‒48. . 10.1109/tcns.2022.3198856
[20]

Das AK, Fierro R, Kumar V, Ostrowski JP, Spletzer J, Taylor CJ. A vision-based formation control framework. IEEE Trans Robot Autom 2002;18(5):813‒25. . 10.1109/tra.2002.803463
[21]

Tanner HG, Pappas GJ, Kumar V. Leader-to-formation stability. IEEE Trans Robot Autom 2004;20(3):443‒55. . 10.1109/tra.2004.825275
[22]

Nagy M, Ákos Z, Biro D, Vicsek T. Hierarchical group dynamics in pigeon flocks. Nature 2010;464(7290):890‒3. . 10.1038/nature08891
[23]

Ding W, Yan G, Lin Z. Collective motions and formations under pursuit strategies on directed acyclic graphs. Automatica 2010;46(1):174‒81. . 10.1016/j.automatica.2009.10.025
[24]

Torres P, van Wingerden JW, Verhaegen M. PO-MOESP subspace identification of directed acyclic graphs with unknown topology. Automatica 2015;53:60‒71. . 10.1016/j.automatica.2014.12.020
[25]

King AJ, Sueur C. Where next? Group coordination and collective decision making by primates. Int J Primatol 2011;32:1245‒67. . 10.1007/s10764-011-9526-7
[26]

Ashburner M, Ball CA, Blake JA, Botstein D, Butler H, Cherry JM, et al. Gene Ontology: tool for the unification of biology. Nat Genet 2000;25(1):25‒9. . 10.1038/75556
[27]

The Gene Ontology Consortium. Expansion of the Gene Ontology knowledgebase and resources. Nucleic Acids Res 2017;45(D1):D331‒8. . 10.1093/nar/gkw1108
[28]

Cantoni M, Weyer E, Li Y, Ooi SK, Mareels I, Ryan M. Control of large-scale irrigation networks. Proc IEEE 2007;95(1):75‒91. . 10.1109/jproc.2006.887289
[29]

Gebraad PMO, van Dam FC, van Wingerden JW. A model-free distributed approach for wind plant control. In: Proceedings of American Control Conference; 2013 Jun 17‒19; Washington, DC, USA; 2013. . 10.1109/acc.2013.6579907
[30]

Yang F, Kang P, Guan X. Distributed economic dispatch for cyber attacked smart grid based on resilient event-triggered consensus. In: Proceedings of 59th IEEE Conference on Decision and Control (CDC); 2020 Dec 14‒18; Jeju, Republic of Korea; 2020. . 10.1109/cdc42340.2020.9304250
[31]

Smotherman M, Krishnamurthy S, Aravind PS, Hunnicutt D. Efficient DAG construction and heuristic calculation for instruction scheduling. In: Proceedings of the 24th Annual International Symposium on Microarchitecture; 1991 Nov 18‒20; Albuquerque, NM, USA; 1991. . 10.1145/123465.123482
[32]

Horowitz R, Varaiya P. Control design of an automated highway system. Proc IEEE 2000;88(7):913‒25. . 10.1109/5.871301
[33]

Montague PR, Dayan P, Person C, Sejnowski TJ. Bee foraging in uncertain environments using predictive hebbian learning. Nature 1995;377(6551):725‒8. . 10.1038/377725a0
[34]

Huelsbergen L. Dynamic resolution: a runtime technique for the parallelization of modifications to directed acyclic graphs. Int J Parallel Program 1997;25:385‒417. . 10.1007/bf02699884
[35]

Johnston WM, Hanna JRP, Millar RJ. Advances in dataflow programming languages. ACM Comput Surv 2004;36(1):1‒34. . 10.1145/1013208.1013209
[36]

Bang-Jensen J, Gutin GZ. Digraphs: theory, algorithms and applications. London: Springer; 2009. . 10.1007/978-1-84800-998-1_18
[37]

Friedman N. Inferring cellular networks using probabilistic graphical models. Science 2004;303(5659):799‒805. . 10.1126/science.1094068
[38]

Husmeier D, Dybowski R, Roberts S. Probabilistic modeling in bioinformatics and medical informatics. London: Springer; 2005. . 10.1007/b138794
[39]

Moret BME, Nakhleh L, Warnow T, Linder CR, Tholse A, Padolina A, et al. Phylogenetic networks: modeling, reconstructibility, and accuracy. IEEE/ACM Trans Comput Biol Bioinformatics 2004;1(1):13‒23. . 10.1109/tcbb.2004.10
[40]

Quinn CJ, Coleman TP, Kiyavash N, Hatsopoulos NG. Estimating the directed information to infer causal relationships in ensemble neural spike train recordings. J Comput Neurosci 2011;30:17‒44. . 10.1007/s10827-010-0247-2
[41]

Eisen MB, Spellman PT, Brown PO, Botstein D. Cluster analysis and display of genome-wide expression patterns. Proc Natl Acad Sci USA 1998;95 (25):14863‒8. . 10.1073/pnas.95.25.14863
[42]

Granger CW. Investigating causal relations by econometric models and cross spectral methods. Econometrica 1969;37(3):424‒38. . 10.2307/1912791
[43]

Witthaut D, Timme M. Braess’s paradox in oscillator networks, desynchronization and power outage. New J Phys 2012;14(8):083036. . 10.1088/1367-2630/14/8/083036
[44]

Cohen JE, Horowitz P. Paradoxical behaviour of mechanical and electrical networks. Nature 1991;352(6337):699‒701. . 10.1038/352699a0
[45]

Ozogány K, Vicsek T. Modeling the emergence of modular leadership hierarchy during the collective motion of herds made of harems. J Stat Phys 2015;158(3):628‒46. . 10.1007/s10955-014-1131-7
[46]

Seres IA, Gulyás L, Nagy DA, Burcsi P. Topological analysis of Bitcoin’s lightning network.In:Pardalos P,Kotsireas I,Guo Y,Knottenbelt W,editors.Mathematical research for blockchain economy. Cham: Springer; 2020. p. 1‒12. . 10.1007/978-3-030-37110-4_1
[47]

Liu B, Chen Z, Zhang HT, Wang X, Geng T, Su H, et al. Collective dynamics and control for multiple unmanned surface vessels. IEEE Trans Control Syst Technol 2020;28(6):2540‒7. . 10.1109/tcst.2019.2931524
[48]

Demmel JW. Applied numerical linear algebra. Philadelphia: SIAM; 1997. . 10.1137/1.9781611971446
[49]

Gibbons JD, Chakraborti S. Nonparametric statistical inference. In: Lovric M, editor. International encyclopedia of statistical science. Berlin: Springer; 2014.
[50]

Calleman CJ. The purposeful universe: how quantum theory and Mayan cosmology explain the origin and evolution of life. New York City: Simon and Schuster; 2009.
[51]

Mo X, Chen Z, Zhang HT. Effects of adding a reverse edge across a stem in a directed acyclic graph. Automatica 2019;103:254‒60. . 10.1016/j.automatica.2019.02.020
AI Summary AI Mindmap
PDF (4416KB)

2377

访问

0

被引

详细
导航
相关文章

AI思维导图

/

〈 〉