论文标题： The Immense Impact of Reverse Edges on Large Hierarchical Networks

期刊：Engineering

作者：Haosen Cao, Bin-Bin Hu 等

发表时间： May 2024

DOI：https://doi.org/10.1016/j.eng.2023.06.011

微信链接：点击此处阅读微信文章

华中科技大学人工智能与自动化学院张海涛教授团队在中国工程院院刊《Engineering》上发表了关于复杂网络反边效应的最新研究成果“The Immense Impact of Reverse Edges on Large Hierarchical Networks”。

有向分层网络的同步是自然界、工业界和社会生活中广泛存在的物理现象，当网络拓扑中新增逆层次结构的连边，人们常常认为大部分反向连边都将影响网络的同步速度。令人惊奇的是，本文通过大量实验发现，仅有少数特定位置上的反向连边具有这样的同步影响能力。更有趣的是，随着网络规模的扩大，有效反边所占比例将进一步降低，甚至低于0.1%。因此，如何在复杂的大型网络拓扑中确定有效反边的位置，并进一步定量分析其对同步的影响程度，据此调节复杂网络同步速度，仍是一项挑战。

为系统性研究反向连边在网络同步中所起的作用，文章首先开展了分布式无人艇集群朝向同步实验，验证了部分反向连边能够延长艇群达到一致的时间。

反向连边在自然或人工的复杂网络系统中都十分常见，有些连边对网络的收敛速度、节点鲁棒性、连通性等同步性能都存在较大影响。然而，现有的工作仅停留在研究部分特殊的反向连边，如“死端”结构、“茎”结构，对反向连边的物理机理也尚未有明确解释。为深入研究反边现象的机理，文章围绕如下三个问题展开：（1）具有调控能力的有效反向连边占所有反边比例多少；（2）如何搜索确定有效反边的位置；（3）有效反边影响同步速度的程度与哪些因素有关。

文章将有向网络的同步过程视为了信息流动、进而统一的过程，从物理角度构建了信息流“聚束”效应模型，刻画了基于图拉普拉斯矩阵的网络同步信息流传递模式。

分析发现，无论网络规模如何，都存在少量的有效反向连边，它们改变了图拉普拉斯矩阵局部的入度分布情况，从而减慢网络的同步速度。根据模型提出了有效反边搜索算法，用于判断和搜索具有同步阻碍作用的特定反向连边，从而指导引入有效反边来调控网络的同步性能，抑或通过保护少量有效反边来避免网络受到外界干扰或恶意攻击。算法有效性在实际网络拓扑与人工网络拓扑上得到了验证。

实验结果显示这些有效反边虽然在网络分层网络中占的比例较小，但能极大程度影响网络同步速度，例如向数万节点的大型网络中添加一条相邻节点之间的反向连边，就能够将网络的同步速率指标降低超过60%。这一实验现象反映出反向连边对于网络的同步性能具有高效的调控能力。进一步研究发现这种减速效应的程度仅由该反向连边跨过的子网络决定，与网络规模或反向连边的位置无关，并且可以根据该子网络平均入度进行定量估计。

网络同步现象的内在机理与物理特性对于更好地设计和控制多智能体系统、智能电网系统等具有重要意义。反向连边通常代表着从较低级节点到较高级节点反馈，在自然、社会、经济和工程等背景的分层网络中十分常见，并发挥着重要作用。而反向连边具有形式多变、工程中成本较低、调控能力强等特点，该工作可能为保护、攻击或调节整个分层网络同步过程提供理论参考，应用场景例如多机器人系统、电力网络或无线传感器网络等。

引用信息：Haosen Cao, Bin-Bin Hu, Xiaoyu Mo, Duxin Chen, Jianxi Gao, Ye Yuan, Guanrong Chen, Tamás Vicsek, Xiaohong Guan, Hai-Tao Zhang, The Immense Impact of Reverse Edges on Large Hierarchical Networks, Engineering, 2024, 36:238–247.

开放获取全文

https://doi.org/10.1016/j.eng.2023.06.011

推荐阅读

华中科技大学张海涛、魏翔教授联合实现主动脉夹层的自动诊断

Engineering影响因子位列工程类综合期刊第二名

Engineering天线技术专题论文集锦

观点评述：糖医学——当前的技术发展水平/前沿科技

太空太阳能发电前景光明吗？