复杂网络中链接可预测性的研究：二阶谱扰动方法

《Physica A: Statistical Mechanics and its Applications》：Link predictability in complex networks: A second-order spectral perturbation method

　　摘要：在复杂网络链接预测领域中，预测性是一个极具挑战性的问题，其目的是揭示网络内在结构与该结构可被预测程度之间的关系。尽管现有研究已提出了多种预测性指标，但仍然需要更多基于结构特征和谱信息的度量方法。本文我们引入了一种二阶边对扰动框架，用于表征网络的结构确定性。与传统仅能捕捉单个边贡献的单边扰动方法不同，我们的框架同时扰动边对，以揭示它们之间的协作与竞争耦合模式。通过分析边对对邻接矩阵最大特征值的整体影响，我们构建了一个结构确定性指数（SD），该指数能够体现网络拓扑对链接形成的宏观约束。SD指数本质上量化了边对之间正（协作）耦合分布的集中程度，提供了一种基于熵的结构规则性度量方法。在此基础上，我们进一步将相对谱间隙（RSG）和网络能量分布熵（EDE）这两种关键的谱描述符整合为一个统一的预测性度量指标——LPability，并通过简单的感知器模型来模拟结构-谱特征与链接预测性之间的非线性关系。在合成网络（ER、WS、BA）以及12个真实世界网络上的大量实验表明：（1）SD指数能够有效区分不同的网络模型，对于具有均匀耦合模式的ER网络，该指数值相对较高，而对于具有集中耦合模式的WS和无标度BA网络，其值则显著较低；（2）LPability与各种真实网络中先进的链接预测算法的性能之间存在较强的正相关关系。我们的研究结果表明，所提出的框架为评估复杂网络中的链接预测性提供了一种基于谱信息且具有结构可解释性的方法。

引言：在复杂网络研究中，网络结构[1]、[2]以及动态特性[3]、[4]是两大主要研究方向。网络结构不仅对于理解网络动态至关重要，而且在探索和理解网络的结构演化机制方面也发挥着不可替代的作用[5]、[6]。复杂网络中的链接预测是一种用于研究网络结构的方法[7]，它旨在探究可观察到的网络结构的生成机制，从而预测未来可能形成的链接，或识别那些已经存在但尚未被观测到的链接[8]、[9]，进而形成我们所说的重构网络。目前，已有基于节点相似性[10]、[11]、矩阵补全[12]、[13]以及机器学习[14]、[15]、[16]的方法，这些方法都致力于提高网络链接预测的准确性。然而，在复杂网络链接预测的研究领域中，还有一个根本性的问题尚未得到解决：“利用可观察到的链接，能在多大程度上准确预测复杂网络中缺失的链接？”在学术上，这个问题通常被称为复杂网络链接预测性问题[17]。复杂网络链接预测性问题对于设计链接预测算法以及探索网络演化机制具有重要意义。一些学者已在此领域开展了初步研究，并取得了重要成果[18]、[19]、[20]。

链接预测性指的是网络的一种固有属性——即仅依据可观察到的结构信息，无需依赖特定算法，就能实现的链接预测准确度的理论上限。而链接预测算法的性能则是指某种特定算法在给定网络上的实际预测准确度，它受到算法设计、参数选择以及训练策略的影响。本文的目标是构建一种基于结构特征的度量指标（LPability），用以估算网络的内在链接预测性，同时以算法AUC作为外部实证基准来验证这一估算结果。尽管现有研究在复杂网络链接预测性领域已取得一定进展，但目前大多数方法仍依赖于单边扰动分析，这类方法无法充分捕捉网络结构中边与边之间的协作或竞争关系。具体而言，传统的谱扰动方法仅考虑移除或添加单条边对谱特性的影响，无法体现边与边之间的“协作”（δλ1>0）和“竞争”（δλ1<0）相互作用。换句话说，两条边对网络结构确定性的综合影响可能大于或小于它们各自影响的简单之和。通过同时扰动两条边并计算它们对λ1的共同影响，我们的二阶边对扰动框架能够量化这些相互作用模式，而这些模式则为构建结构确定性指数提供了基础。基于此，我们构建了一种新的结构确定性指数，从宏观角度量化网络结构对其内部链接形成所施加的约束程度。该指数不仅克服了传统单边扰动方法的局限性，还为从结构确定性视角理解链接预测性提供了新思路。

此外，为了更充分地利用网络的谱信息，我们将相对谱间隙（RSG）和网络能量分布熵（EDE）这两种谱特征纳入结构确定性指数之中。这些特征分别反映了最大特征值与第二大特征值之间的分离程度以及谱上能量分布的集中情况。从涌现理论的角度来看，这些谱特性从不同维度体现了网络的整体结构约束及其稳定性。需要明确的是，多层感知器（MLP）在我们的框架中的作用并非取代或掩盖那三个结构指数（SD、RSG、EDE），而是用来揭示它们在共同决定链接预测性过程中可能存在的非线性相互作用。这三个指数各自捕捉网络结构的不同维度——SD衡量边对耦合的集中程度，RSG衡量谱的可分性，而EDE衡量能量分布的均匀性。多层感知器则作为一种简单工具，用于建模它们共同产生的潜在非线性效应。为了量化非线性的贡献，我们还将多层感知器与线性回归基准进行了比较。最后，我们运用多层感知器模型将结构确定性指数、相对谱间隙以及能量分布熵非线性地整合在一起，提出了一种全面的链接预测性度量指标——LPability。这一指标不仅具有清晰的结构可解释性，还具备强大的表达能力，能够从谱特征和结构特征两个层面共同刻画网络的链接预测潜力。大量的实验验证表明，LPability与各种先进链接预测算法的性能之间存在较强的正相关关系，这证明了其在不同网络结构下表征链接预测性的有效性。

本文的主要贡献如下：•我们提出了一种二阶边对扰动框架，通过分析边对对最大特征值λ1的共同影响，能够捕捉边与边之间的协作与竞争耦合模式，从而突破了传统单边扰动方法的局限。•我们构建了结构确定性指数（SD），用于定量描述边对之间正耦合分布的集中程度，同时还通过线性和非线性模型整合了网络能量和谱间隙信息，以此展现基于网络谱信息准确表征链接预测性的潜力。•我们在合成网络和真实世界网络上进行了大量数值实验，实验结果表明，本文提出的链接预测性指数与当前先进的链接预测算法性能之间存在显著相关性。跨不同网络类型的验证进一步证明了LPability的泛化能力。

本文的其余结构如下：第2节将对复杂网络链接预测性的现有研究以及基于相似性和矩阵分解的链接预测方法的最新进展进行简要回顾。第3节详细阐述本文的主要贡献，包括基于λ1变化的结构确定性指数、相对谱间隙以及网络能量分布熵。第4节介绍本研究中所进行的数值实验。第5节探讨所提方法的局限性、计算复杂性以及加速策略。第6节则对我们的工作进行简要总结，并讨论未来研究的方向。

相关研究：在科学界，预测性问题一直是一个备受关注的话题[21]、[22]。同样，链接预测性也是复杂网络链接预测研究中的一个重要理论问题。它不仅对于理解和探索复杂网络结构的生成机制具有重大意义[23]，而且在衡量现实世界中海量数据的价值方面也具有重要的应用价值[24]。目前，已有许多学者对此展开了研究。

动机与问题定义：对于一个连通的无向且无权重的网络G(V,E)，其邻接矩阵为A=(aij)n×n，其中当aij=1时表示节点vi和vj之间存在边，而aij=0则表示两者之间没有边。由于无向网络的邻接矩阵是实对称矩阵，因此它的特征值也是实数，且其特征向量构成一个正交基。设λ1>λ2>?>λn为邻接矩阵A的所有特征值，v(i)为对应于λi的标准化特征向量。

实验：本研究开展了四组数值实验，用以验证所提出的复杂网络链接预测性度量指标的有效性。需要强调的是，在本节中，我们区分了内在链接预测性（即LPability旨在估算的网络属性）与实证性的链接预测算法性能（通过特定算法的AUC/召回率来衡量），后者作为验证的外部基准。在第一个实验中，我们研究了……

讨论：要精确计算SD指数，需要通过求解方程（14）来构建完整的ΔΛ矩阵，而这一过程需要对所有O(M2)对边进行计算。每次计算都需要对n个特征分量求和，因此总的时间复杂度为O(M2n)，其中M为边的数量，n为节点的数量。对于本研究中所分析的网络（M～103–104，n～102–103），在标准硬件上这一计算仍然是可行的（在最复杂的情形下，即M=16,715的PB级硬件上，所需时间约为1.4×108……）

结论：本文提出了一种基于谱与结构的框架，用于量化复杂网络中的链接预测性。我们引入了一种二阶边对扰动方法，以此构建结构确定性指数（SD），该指数通过量化边对之间协作耦合分布的集中程度，来反映宏观拓扑结构对链接形成的约束作用。此外，我们还整合了相对谱间隙和网络能量分布特征……

CRediT作者贡献声明：Lang Chai：写作——审阅与编辑，写作——初稿撰写，可视化，验证，指导，软件，方法论，资金获取，数据整理，概念构思。Rui Huang：验证，指导，调研。

利益冲突声明：作者声明不存在任何可能影响本文研究工作的已知财务利益或个人关系。

致谢：本研究得到了重庆市教委科技研究计划（项目编号KJQN202400715）、重庆交通大学（项目编号F1230091）、重庆市研究生联合培养基地建设项目（项目编号JDLHPYJD2021016）以及武汉科技大学冶金过程系统科学重点实验室（项目编号Y202403）的支持。

Lang Chai|Rui Huang
中国重庆重庆交通大学数学与统计学院，邮编400074