一种用于寻找复杂网络中关键循环的张量谱方法

《Chaos, Solitons & Fractals》：A tensor spectral method for finding key cycles in complex networks

　　摘要：循环是图论和复杂网络中的基本研究对象，循环上的每个节点都与两个相邻节点相连。这种两邻接关系可以通过2-邻接张量来自然表示。在Liu等人（2023年）的研究中，他们利用2-邻接张量的谱半径来判断图中是否存在循环。在本文中，我们提出了一种基于2-邻接张量谱半径变化的循环排序方法。为分析图结构如何影响这种循环排序，我们建立了关于连通图及其子图的2-邻接张量谱半径的充要条件。该条件表明悬挂路径结构不会影响2-邻接张量的谱半径，这一发现也加强了Liu等人（2023年）在k=2时的结论。在实验部分，我们重点研究现实世界网络中的三角形排序。实验结果表明，所提出的方法在识别重要三角形方面具有有效性。

引言：中心性度量是复杂网络分析中的基本研究主题[1]、[2]、[3]。随着这一领域的发展，研究人员越来越关注基于高阶结构的中心性度量[4]、[5]。在这些结构中，循环结构已被广泛研究。例如，Fan等人通过定义循环数矩阵和循环比率来量化节点的重要性[6]。Shi等人引入了循环数指标来识别有影响力的传播者[7]。此外，Jiang等人提出了基于Fiedler向量的循环重要性排序方法，Fiedler向量是对应于第二小的拉普拉斯特征值的单位特征向量[8]。这些现有方法依赖于图的矩阵表示，主要捕捉节点间的成对连接。实际上，循环是一种起点和终点相同的闭合路径，意味着循环内的每个节点都恰好与两个相邻节点相连。为了描述这种两邻接关系，标准的矩阵表示存在局限性。因此，我们引入了2-邻接张量[9]，它能够自然地表示这种两邻接关系。张量是一种多维数组，其特征值分别由Qi[10]和Lim[11]独立定义。自那时起，张量的特征值已在包括网络分析[12]、[13]、[14]、[15]、[16]、[17]、[18]、[19]、[20]以及谱图理论[21]、[22]、[23]、[24]、[25]在内的众多领域得到应用。最近，Liu等人引入了图的k-邻接张量，它是图邻接矩阵的推广形式，并得到了关于图的若干谱结果[9]。为了适应本文中提出的循环结构分析，我们考虑k=2的情况。对于图G，2-邻接张量A(G)=(ai1i2i3)是一个三阶、n维张量。如果节点i1与两个不同的节点i2和i3相连，则元素ai1i2i3的值为1/2，其余元素均为0。谱半径ρ2(G)是A(G)所有特征值中的最大模值。参考文献[9]通过2-邻接张量的谱半径来描述图中是否存在循环，具体如下：引理1.1 [9]：图G中存在循环当且仅当ρ2(G)≥1。为了评估循环的重要性而不仅仅是其存在性，我们进一步提出了一种基于2-邻接张量谱半径变化的循环排序方法。通过评估特定循环被扰动时谱半径的变化程度，该方法可以识别出重要的循环。为研究图结构对所提出的循环排序方法的影响，我们探讨了2-邻接张量谱半径的性质。首先，我们建立了充要条件，证明连通图及其2-核具有相同的2-邻接张量谱半径，从而表明悬挂路径不会影响2-邻接张量的谱半径。这一结果加强了参考文献[9]中k=2情况下的结论。然后，我们给出了包括棒棒糖图、风筝图和广义友谊图在内的一些图类中2-邻接张量谱半径的表达式。最后，通过对现实世界网络进行的实验，证明了所提出的循环重要性排序方法的有效性。通过将所提出的方法与现有的循环排序方法如Fiedler向量法[8]进行比较，我们表明基于张量的方法为理解循环的重要性提供了新的见解。本文的结构如下：第2节介绍与张量相关的定义和基本引理。第3节，我们提出了一种新的循环排序方法，并分析了2-邻接张量谱半径与循环结构之间的关系。第4节通过现实世界网络的实验结果来说明所提方法的有效性。最后，第5节给出讨论与结论。

章节片段：初步知识：本节首先介绍张量及其谱的概念，随后定义k-邻接张量及相关引理。设?n表示复数域?上的n维向量集合。对于一个m阶、n维的张量A=(ai1i2?im)和一个向量x=(x1,…,xn)T∈?n，乘积Axm?1是?n中的一个向量，其第i个分量由∑i2,…,im=1naii2?imxi2?xim给出。如果存在非零向量x∈?n使得Axm?1=λ，则复数λ称为A的特征值。

主要结果：在第一小节中，我们介绍了循环中心性排序方法。Restrepo等人[29]通过测量移除节点和边后邻接矩阵最大特征值的变化来表征节点和边的动态重要性。在本文中，我们将这一理念扩展到循环结构，根据2-邻接张量谱半径的变化对循环进行排序。在第二小节中，我们分析了2-邻接张量谱半径与图结构之间的关系。

实验：在本节中，我们通过实验来验证所提出的排序方法。虽然该框架可应用于不同长度的循环，但本节的实验侧重于三角形。三角形是最短的循环，被视为复杂网络中的基本结构。我们首先以经典的Zachary空手道俱乐部网络作为案例进行研究。

讨论与结论：在本文中，我们基于2-邻接张量谱半径的变化开发了一种循环排序算法，然后分析了图结构如何影响这种循环排序。我们的分析基于这样一个事实：如果图包含循环，那么其2-邻接张量的谱半径大于或等于1。我们还建立了连通图及其子图的2-邻接张量谱半径关系的充要条件。

CRediT作者贡献声明：Qing Xu：撰写——初稿、可视化、软件、方法论、研究、概念设计。Chunmeng Liu：撰写——审阅与编辑、验证、方法论、研究、概念设计。Lizhu Sun：撰写——审阅与编辑、验证。Changjiang Bu：撰写——审阅与编辑、验证、监督。

利益冲突声明：作者声明没有已知的财务利益或可能影响本文所述工作的个人关系。

致谢：所有作者都对这项工作做出了同等贡献。作者们想要感谢Abbas Mohamed Sherif的讨论。本研究得到了黑龙江省优秀青年科学基金（项目编号YQ2024A009）和中央高校基本科研业务费（项目编号2412025QD038和3072025YC2403）的支持。

Qing Xu|Chunmeng Liu|Lizhu Sun|Changjiang Bu
哈尔滨工程大学数学科学学院，中国哈尔滨150001