具有合成网络结构的分层赋权图指标综述

A Review of Graph Indices of Composite Networks with Weighted and Layered Structures

摘要: 本文综述了复杂网络领域内，针对合成网络结构，特别是分层赋权图，所采用的一系列图指标及其在研究网络结构与动态特性中的最新进展。这些指标包括但不限于复杂网络的同步能力指标，用于评估网络在受到外部或内部扰动后恢复同步状态的能力；网络一致性指标，可以衡量带有扰动多智能体系统的抗干扰保持网络一致的能力；图的基尔霍夫指标，主要衡量电网络的电气传输效率；本文旨在总结这些指标在合成网络结构研究中的应用现状，探讨其相互关联与潜在影响，并展望未来的研究方向。

Abstract: This paper reviews a series of graphical indices applied to the composite network structures, particularly layered and weighted graphs, in the field of complex networks, as well as the latest progress of these network indices in studying network structure and dynamic characteristics. These indices include but not limited to the synchronization ability of complex networks, which is used to evaluate the network’s ability to resume a synchronized state after being disturbed by external or internal factors; The network coherence can measure the ability of a multi-agent system with disturbances to maintain network consistency against interference; and the Kirchhoff index of graphs, mainly measures the electrical transmission efficiency of an electrical network. This paper aims to summarize the current application status of these metrics in the research of synthetic network structures, explore their interrelationships and potential impacts, and look forward to future research directions.

1. 引言

随着网络科学的迅速发展，对复杂网络结构及其动态特性的研究已成为一个重要的跨学科领域。复杂网络，如社会网络、生物网络、信息网络和技术基础设施网络等，因其广泛存在于自然和社会系统中而备受关注。复杂网络的同步能力是其动态特性的一个重要方面，它描述的是网络中节点活动模式能否达到一致的状态，这一能力对于理解诸如神经元同步、电力系统的稳定运行等问题至关重要。图的基尔霍夫指标(Kirchhoff index)，也被称作网络电阻或有效电阻的总和，主要衡量电网络的电气传输效率。它不仅有助于理解网络的鲁棒性，还可以用于优化网络设计。

2. 复杂网络同步能力指标

复杂网络同步是指网络中各节点在某种动态过程中达到一致状态的现象。同步能力指标(synchronizability)用于量化网络实现同步的难易程度，是评估网络稳定性和鲁棒性的重要参数。在加权网络中，节点的连接强度和方向性对同步能力有显著影响。Duan通过展示两个简单规则对称图的例子来激发研究，这两个图具有相同的结构参数，如平均距离、度分布和节点间中心度，但同步能力指标却截然不同。对于具有相同节点动态的给定网络，进一步说明影响网络同步能力指标的两个关键因素是网络内连接矩阵和网络拓扑矩阵的特征值。发现对于互补图断开的网络，增加边永远不会降低其同步能力指标，无界同步区域总是比有界同步区域更容易分析[1]。朱剑基于主稳定方程(MSF)，研究了k层可变耦合风车型网络的特征值谱。在同步域有界和无界的情况下，研究了分层风车型网络的同步能力指标与节点数、层数、层间耦合强度等网络参数之间的关系。从单层和多层网络的角度给出了同步性的优化方案，发现通过适当改变参数可以提高分层风车型网络的同步性[2]。Zambrano通过比较三种生成小世界复杂网络的算法——Watts-Strogatz算法、Newman-Watts算法以及Sanchez-Posadas算法，来探讨哪种算法在促进由混沌振荡器作为节点的复杂网络同步性方面更为优越。同步能力指标是分析的核心视角。采用了连接图的拉普拉斯矩阵的特征比作为评估指标。通过对比分析发现Sanchez-Posadas算法在提升复杂网络同步性方面展现出相较于Watts-Strogatz算法和Newman-Watts算法的明显优势[3]。Wang利用主稳定方法从理论上推导了多层全耦合网络及其最简单的等值网络的同步能力。证明了一个多层完全耦合网络与其对应的最简单的等值网络具有相同的同步能力。通过实验对推导进行验证，并观察同步过程。分析了影响多层全耦合网络同步性能的因素，层内耦合强度、层间耦合强度、各网络层的节点数、重要节点数和网络层数[4]。Chen研究的是复杂网络的鲁棒性度量及其在不同类型网络中的应用。具体来说，文章针对现有网络鲁棒性度量方法的不足，提出了新的度量方法，并验证了其有效性、高效性和应用价值[5]。

3. 图的基尔霍夫指标

图的基尔霍夫指标(Kirchhoff index)是指图中所有无序点对之间的电阻距离之和，是衡量图连通性和结构复杂度的一个重要指标。基尔霍夫指数(Kirchhoff index)可用于解释分子的图形特征。从电网络的角度来看，它能够反映电阻距离(resistance distance)和平均电能。基尔霍夫指标不仅反映了网络的物理性质，还与其动态特性和功能特性密切相关。Sajjad研究了三角形双锥六面体链这一多面体图结构中的电阻距离及其基尔霍夫指标。三角形双锥六面体链是一种多面体图结构，在网状化学等领域具有广泛的应用。对其电阻距离和基尔霍夫指标的研究有助于深入理解该结构在电网络、通信网络等实际系统中的性能表现，为相关系统的设计和优化提供理论依据[6]。Geng研究线性苯撑分子图的拉普拉斯谱、基尔霍夫指标以及生成树的数量。线性苯撑是一种由苯环(六边形)和其他可能的四边形结构线性连接而成的分子图。这种结构在化学和材料科学中具有重要意义，特别是在网状化学和纳米材料的研究中[7]。Sun利用电网络理论和图论的技术，对具有极值基尔霍夫指数的五边形链进行特征描述。五边形链是一种特殊的图结构，它由一系列五边形(即具有五个顶点和五条边的多边形)线性连接而成。研究丰富了图论和电网络理论在化学和生物学领域的应用，为QSAR和QSPR的研究提供了新的视角和方法[8]。Wang研究了两种类型网络的拉普拉斯谱，并特别针对其中的一种特殊情况——棱柱图，得出了其基尔霍夫指数和生成树数量的显式公式。研究成果有助于解决网络设计、电路布局、社交网络分析等领域的实际问题[9]。

4. 网络一致性指标

多智能体网络模型达到一致性的鲁棒性可以由网络一致性指标(network coherence)来衡量[10] [11]，该指标体现了带有扰动或噪声多智能体系统的抗干扰保持网络一致的能力，也即体现其量化网络协调能力。文献[10] [11]中提出了网络一致性指标可由拉普拉斯特征值相关的数学表达式来刻画。近年来该研究领域出现了很多重要成果。文献[12]基于特定的网络结构，推导了三种网络一致性指标的表达式，以及它们对网络规模的依赖关系。对于一阶主从模型，该文献发现网络一致性能指标取决于领导者与最大度节点之间的最短路径距离，同时也与主点的度数相关。在科赫网络(Koch network)中，所讨论的一致性指标的渐近行为，与在其他不具备无标度小世界特性的网络中的渐近行为存在差异。文献[13]研究了对称树的一致性相关指标与主导节点个数之间的关系。文献[14]推导得出嵌套网络拉普拉斯谱的递推表达式，进而得到了一致性相关指标的数学表达式。文献[15]从图谱理论的角度出发，研究了一种适用于层状和格状相结合结构的多智能体系统的一阶网络一致性指标(FONC)。采用图的并运算构建了两组非同构的层状格状结构，并通过拉普拉斯谱方法得到了该指标的表达式，进而获得了相应的渐近结果。研究发现，在所考虑的经典图类的合成图框架下，当连通性较好的处于中心位置的子结构节点集基数趋于无穷大时，整个网络的一阶网络相干性将与中心格状结构呈现出相同的渐近行为。文献[16]分析了一类多边形网络在噪声分布下的网络一致性。推导出了一类多边形网络的一阶和二阶无领导者网络一致性的精确解析解；探究了网络拓扑结构对网络一致性的影响。研究发现，随着迭代次数的增加，一阶无领导者网络的一致性与鲁棒性得到显著提升。最后，该研究证实了多边形网络中二阶网络一致性与节点数量之间存在近似线性关系。文献[17]聚焦一类非平衡网络的一致性问题，重点考察领导者选择与网络参数对一致性的影响.探讨了三类不同的一致性算法，分别为一阶和二阶无领导点算法，以及一阶领导者–跟随者算法。具体研究内容如下：首先，推导一阶和二阶无领导者网络一致性的精确解；其次，针对一阶领导者–跟随者网络设计多种领导者分配方案，得到与网络规模N、双环基数p和q以及领导者数量k相关的表达式；最后，通过数值仿真与鲁棒性分析，得出领导点数量及拓扑结构对网络一致性的影响。

5. 分层网络结构

多层(或分层)复杂网络，指由多个相互关联的单层结构组成的复杂网络结构，广泛存在于通信网络、电力系统、社交网络、交通系统、生物网络等领域，因其在实际应用中的广泛存在[18]-[20]，已成为一个前沿课题。其协同行为(同步、一致性等)是系统高效运作的核心保障。单层网络模型因难以捕捉实际系统的层次关联与交互复杂性，逐渐被多层网络模型取代。许多网络化系统都具有分层或多层图结构[18] [21] [22]。协同问题相关指标作为量化网络协同能力的核心工具，其研究可追溯至经典复杂网络理论。然而，作为网络协同一致问题研究的一个分支，将基于拉普拉斯谱的图谱方法应用于加权分层网络图指标分析的相关研究论文相对较少，值得进一步研究。

6. 网络指标间的区别与联系

网络协同一致稳定性指标(同步问题或者一致性问题的系统结构的最小非零特征值)则面向多智能体系统，刻画系统趋于一致状态的收敛能力，其判据直接依赖拉普拉斯矩阵的特征值–代数连通度越大，稳定性越强，收敛速度越快。

基尔霍夫指标和网络一致性相关指标(network coherence)的关联在于，都跟图的拉普拉斯特征值有关，都与网络结构图的非零特征值的倒数和有关，区别在于反应的是两种不同网络类型的性能指标。基尔霍夫指标聚焦图的拓扑连通性，定义为图中所有顶点对之间有效电阻的总和，电阻越小、指标值越低，图的连通性越强。网络一致性相关指标则是可以应用拉普拉斯谱的相关表达式来刻画带有噪声扰动网络的鲁棒性。基尔霍夫指标是纯拓扑属性，与系统动态无关；稳定性相关协同指标则融合网络结构与动力学特性(如智能体个体动态方程)，需结合特征值分布综合判断。

7. 结论与展望

本文总结剖析了复杂网络的内在运作机制及其在实际应用中的效能表现，重点聚焦于网络的同步能力、一致性指标、基尔霍夫指标等核心指标。首先，复杂网络的同步能力作为评估其稳定性和鲁棒性的关键标尺，受网络拓扑结构、节点连接强度及方向性等多重因素制约。研究显示小世界网络和无标度网络因其独特的结构特征，展现出较高的同步能力。目前系统且完整的描述具有分层赋权图结构的网络化系统性能指标及各类指标具体关系的研究结果相对非常稀少，值得深入研究。我们可以通过精细调控分层网络权重分配与改进拓扑结构，进一步强化其同步或者一致性相关网络性能。

基金项目

自治区级大学生创新创业训练项目：S202410994017，S202410994029。新疆自治区教育厅项目(XJEDU2022P129, XJEDU2024P080)；国家级大学生创新创业训练项目：202410994008。

NOTES

^*通讯作者。