基于路径惩罚集体影响力的复杂网络链路预测

《Physica A: Statistical Mechanics and its Applications》：Link prediction of complex networks based on path-penalized collective influence

　　

摘要

链路预测作为复杂网络研究中的核心任务，旨在基于现有的结构信息识别潜在的链接，为后续实验提供理论指导。现有的大多数链路预测方法依赖于节点之间的结构相似性，无论是局部的还是全局的，而相对较少关注全局拓扑结构对链路形成的潜在抑制效应。为了解决这一问题，本文提出了一种基于集体影响力诱导的路径惩罚机制（CPP）的新型链路预测方法。CPP引入了集体影响力的概念，并引入了拓扑屏障的概念，以刻画非相邻节点对之间最短路径上分布的骨干节点所关联的结构阻力。假设对这类骨干节点的依赖程度越高，从统计意义上来说，直接链路形成的倾向性就越低。通过对候选节点对的最短路径构建惩罚机制，CPP为结构上不太合理的链路分配较低的预测优先级。在多个真实网络上的实验表明，CPP在区分正负样本方面具有很强的辨别能力，在AUC-ROC、AUC-PR和精确率方面与九种代表性基线方法相比取得了具有竞争力或领先的性能。在不同训练集比例下的额外实验进一步表明，CPP在不同稀疏程度的网络下均能保持强大的预测性能。这些结果表明，CPP通过引入全局拓扑约束，为链路预测提供了有效且可解释的视角，并拓展了结构抑制机制在网络分析中的应用。

引言

复杂网络在20世纪末涌现[1]、[2]，源于对真实网络中"小世界"和"无标度"特性的科学发现与研究。由于其固有的跨学科性质，复杂网络的应用跨越多个科学领域，包括物理学[3]、[4]、[5]、[6]、[7]、[8]、[9]、[10]、[11]、数学[12]、计算机科学[13]、[14]、[15]以及系统科学。这些领域提供了分析工具——图论、矩阵分析、概率论和组合学——其中图论构成了复杂网络研究的基础。例如，复杂网络与统计物理学的结合有助于更深入地理解微观结构如何影响宏观动力学。除了传统的基于拓扑的链路预测方法外，各种新颖的方法已被提出以进一步提高预测性能[16]，复杂网络与机器学习之间的融合也日益凸显[17]、[18]、[19]。例如，在图神经网络的研究中，网络结构被用于组合优化、分子建模和交通预测。而针对具有特定拓扑结构的复杂网络的研究——为理解深度学习模型的架构提供了新的视角[15]。

同时，复杂网络的研究不断拓展至多个子领域。在社会网络分析中，链路预测问题和基于邻居的相似性指标已成为经典话题[20]、[21]、[22]、[23]；在智能交通系统中，深度学习和生成对抗网络（GAN）已被应用于各种类型复杂网络的预测任务[24]、[25]、[26]；在网络优化和影响力最大化方面，基于超图的启发式方法已被提出[27]；在结构分析和信息论[28]、社区检测[29]、结构熵[30]、局部熵[31]、[32]以及非广延性方面，已被用于刻画网络的复杂性，同时概率分配的新距离度量和基于排列的推理也相继出现[33]、[34]、[35]。此外，复杂网络与人工智能、系统科学和统计物理学的融合日益紧密：一方面，与统计物理学的交叉加深了我们对微观结构如何影响宏观动力学的理解[36]、[37]；另一方面，与机器学习的融合促进了图神经网络在组合优化、分子建模和交通预测中的应用。总体而言，这些研究成果不仅丰富了复杂网络的理论框架，也为跨学科应用提供了新的方向。

链路预测的核心假设之一是，结构相似的节点更有可能形成连接[38]。该原则认为，个体之间在属性、行为或结构位置上的相似性将显著增加其产生交互的可能性。这一原则被转化为一种结构假设：如果两个节点在网络中共享相似的位置、邻居配置或基于路径的特征，则它们更有可能相连[39]。这些方法从根本上基于一个假设，即节点相似性越高，连接的可能性就越大。尽管这一假设在链路预测研究中被广泛采用，但在真实网络中并不总是成立[40]。例如，在社会网络中，结构相似的用户可能并没有真正的交互意图；在生物网络中，功能相似的蛋白质可能由于空间分离而无法结合。换言之，节点之间的结构相似性并不必然保证链路的存在，而仅依赖这一原则可能导致不准确的预测。因此，需要一种新方法来有效过滤结构上不合理的链路，以提高链路预测的准确性[41]、[42]、[43]、[44]、[45]、[46]。

因此，在本工作中，提出了一种基于路径惩罚的链路预测模型。新模型基于渗流理论中已经揭示的现象，即网络的全局连通性依赖于少量骨干节点，其移除会触发系统的突然崩溃[47]。受此观察启发，我们引入路径惩罚机制到链路预测中，以抑制潜在链接对骨干节点的过度依赖，从而为整体网络结构提供更忠实的表示。在此基础上，我们构建了一个路径惩罚预测框架，用于识别和过滤结构上不合理的候选链路，突出具有更高真实连通潜力的节点对。实验结果表明，所提出的路径惩罚链路预测方法具有显著的预测优势，始终优于现有方法，在稀疏网络中表现尤为突出。该方法在AUC-ROC和AUC-PR分数上优于所有基线方法，表现出区分正负样本和有效识别极端类别不平衡下稀有正样本的卓越能力。同时，它在精确率方面也保持了优异的性能，进一步证实了路径惩罚机制在提高预测准确性方面的有效性。

本文其余部分组织如下。在第2节中，我们介绍了复杂网络中路径惩罚的概念，该概念汲取自渗流理论和网络骨干识别，以及路径惩罚中的骨干节点抑制。在第3节中，我们提出了基于路径惩罚的链路预测方法，包括通过集体影响力排名定义惩罚分数，以及惩罚比例对链路预测的影响。最后，我们在第4节中总结我们的工作。

章节片段

复杂网络中的路径惩罚

路径惩罚并非复杂网络研究中的新概念[48]。人们已广泛观察到，网络的全局连通性依赖于少量骨干节点，其移除会触发系统的突然崩溃。这一现象被渗流理论很好地捕捉到了，该理论为刻画网络的结构完整性提供了强大的数学框架。在本节中，我们首先介绍渗流理论的概念及其应用

基于路径惩罚的链路预测

基于前一章的分析，我们提出了一种基于集体影响力的路径惩罚（CPP）方法用于复杂网络中的链路预测。该方法利用集体影响力（CI）来识别网络中的骨干节点，并将它们视为潜在的拓扑屏障。当两个节点尝试形成连接时，其最短路径上的骨干节点施加了结构抑制。通过引入基于排名的惩罚机制，我们量化了这种阻力

在真实网络上的实验评估

在前几章中，我们系统地提出并分析了一种基于集体影响力（CI）的最短路径惩罚链路预测方法，揭示了其预测性能、被惩罚节点数量与CI半径参数之间的内在关系。为了进一步验证该方法的有效性，以下章节在一系列真实网络上进行了实验。为了多样化实验设置并增强泛化能力

结论

本文提出了一种基于集体影响力和路径惩罚的链路预测方法。该方法基于渗流理论的洞见，即网络的全局连通性强烈依赖于相对少量的关键骨干节点，其移除会触发巨型连通分量的快速崩溃。相应地，我们将"路径惩罚"的概念引入链路预测，并提出假设，从统计意义上来说，候选节点对

CRediT作者贡献声明

张卓博：写作——初稿，可视化，方法论，调查，概念构思。单一殊：可视化，验证，调查，概念构思。孙龙龙：可视化，验证。李美竹：写作——审阅与编辑，可视化，获取资助。张琦：写作——审阅与编辑，可视化，验证，监督，项目管理，方法论，获取资助。

利益冲突声明

作者声明他们没有已知的竞争性经济利益或个人关系，这些关系可能会影响本文报告的工作。

致谢

本工作得到国家自然科学基金（项目编号：62303198）、江苏大学高级人才科研启动基金（项目编号：5501170008）和江苏科技大学科研基金（项目编号：1052932204）的支持。

张卓博|单一殊|孙龙龙|李美竹|张琦

江苏科技大学理学院，镇江 212100，中国