基于欧几里得嵌入的复杂网络链路预测
《Physica A: Statistical Mechanics and its Applications》:Link prediction via Euclidean embedding in complex networks
【字体:
大
中
小
】
时间:2026年08月29日
来源:Physica A: Statistical Mechanics and its Applications 3.1
编辑推荐:
摘要
现实中的网络往往具有潜在的度量结构。基于这一观察,近期研究将来自不同应用领域的网络嵌入到潜在空间中,特别是从双曲几何的角度出发。然而,节点实际地理位置与其潜在空间表示之间的实证比较仍然有限。清晰地理解嵌入结果对于理论研究和实际应用都至关重要。在本工作中,我们提出了一种
摘要
现实中的网络往往具有潜在的度量结构。基于这一观察,近期研究将来自不同应用领域的网络嵌入到潜在空间中,特别是从双曲几何的角度出发。然而,节点实际地理位置与其潜在空间表示之间的实证比较仍然有限。清晰地理解嵌入结果对于理论研究和实际应用都至关重要。在本工作中,我们提出了一种新颖的欧氏空间网络嵌入方法,并在真实网络中系统地比较了节点的真实地理位置与其推断的潜在位置。我们的结果为揭示隐藏空间的结构及其与物理地理的关系提供了更深入的见解。此外,我们将学到的潜在表示应用于链路预测任务,该任务旨在利用不完整的网络信息识别潜在连接。实验结果表明,所提出的方法在多个真实世界网络上实现了具有竞争力的链路预测精度,同时以相对较低的计算成本提供了可解释的潜在空间表示。总体而言,本工作为大规模网络嵌入提供了一种可解释且具有地理信息的解决方案,对于地理敏感型网络应用具有独特优势。
引言
近几十年来,理解现实世界网络的组织结构变得越来越具有挑战性[1]、[2]、[3],这主要归因于网络规模的快速增长和网络动态复杂性的不断增加。来自计算机科学、生物学和物理学等广泛学科的研究者投入了大量精力研究真实网络的结构特性[4]、[5]。复杂网络分析的核心问题之一是大规模稀疏网络中噪声的减少和缺失信息的推断[6]、[7]。缺失信息不仅包括节点之间未被观测到的历史连接,还包括潜在的未来的连接,例如揭示恐怖网络中的隐藏关系[8]。
在许多真实世界的网络中,如电力网络、机场系统和道路网络,节点嵌入在物理空间中并占据固定的地理位置。在这些网络中,节点更有可能连接到地理位置上邻近的节点,两个节点之间连接存在的概率与它们之间的空间距离呈负相关[9]、[10]。具体而言,这种关系通常被建模为 $p_{ij} \propto d_{ij}^{-\beta}$,其中 $d_{ij}$ 表示节点 $i$ 和 $j$ 之间的距离,$\beta > 0$ 是一个可调参数。这种对短程连接的空间偏好在具有真实地理位置信息的网络中是显而易见的,在这些网络中节点位置在现实中是固定的。类似的空间效应在社交网络中也得到了观察。个人居住在特定的地理区域,受到时间和经济成本的约束,使得地理邻近的人之间的社会互动更为可能。近期的实证研究进一步表明,在线社交网络表现出显著的空间聚集特性:同一区域内的用户倾向于具有比跨区域用户显著更高的连接密度,因为区域邻近性通常与共同的兴趣、文化和社会背景相关联[11]、[12]。
这些例子表明,地理距离在塑造地理受限网络的拓扑方面起着根本性的作用。然而,对于许多真实世界的网络,获取准确的地理坐标是困难的甚至不可行的。此外,网络连通性往往受到物理和环境因素的影响——如山脉、山谷和河流——这些因素无法通过简单的地理坐标充分捕获。我们通过将这些网络嵌入到一个隐藏空间中来绕过这个难题,其中隐藏空间中的距离充当了真实距离的对应物。尽管先前的研究已经将隐藏空间表示应用于导航和社区检测(即将节点分类到不同的组中)等任务[13]、[14],但网络结构与潜在空间中节点位置之间的关系,以及真实地理空间与潜在隐藏空间之间的对应关系,仍然缺乏充分的理解。
链路预测的目标是通过估计一对节点将被连接的 likelihood 来推断网络的未来演化[15]、[16]。已经提出了各种方法来解决这一问题。最直观的方法是基于相似性的方法,它们利用两个节点共享的共同邻居数量来量化连接的 likelihood。然而,这类方法往往倾向于高度节点,导致有偏的预测。为了解决这一问题,提出了一些加权相似度度量,包括 Jaccard 指数[17]、Salton 指数[18]和资源分配指数[19]。由于依赖于局部网络信息,这些方法因其计算效率高和复杂度低而引起了广泛关注。此外,为了解决诸如高度流行节点的过度影响和冷启动问题等挑战[20]、[21]、[22],人们开发了各种基于全局网络信息的链路预测方法。代表性例子包括 SimRank[23]、基于分层随机图的方法[7]和随机块模型[24]、[25]。尽管其预测能力有所提高,但基于全局信息的方法计算量较大,这限制了其在大规模复杂网络中的适用性[26]、[27]。
在本工作中,我们提出了一种针对地理受限网络的欧氏隐藏空间嵌入方法。其核心思想是直接从网络拓扑中推断一个有效的空间表示,使得在重建的隐藏空间中两个节点之间的距离反映它们潜在的连接成本或接近程度。与传统的基于相似性的链路预测方法不同,后者主要依赖局部邻居重叠或全局路径信息,我们的方法通过网络的改进谱表示来构建节点坐标。与许多现有的隐藏空间嵌入方法不同,我们的方法明确研究了推断出的潜在距离与真实地理距离之间的关系,从而为网络连通性提供了可解释的几何解释。
本工作的主要创新有三点:
• 首先,我们仅从邻接矩阵重建欧氏潜在空间,无需预先知道节点坐标。
• 其次,对于具有地理信息的网络,我们系统地比较隐藏空间距离与真实地理距离,并表明重建的空间捕捉了有意义的空间组织。
• 第三,我们利用推断的隐藏坐标进行链路预测,假设在隐藏空间中更近的节点对被连接的可能性更大。
通过这种方式,所提出的方法结合了可解释性和预测效用,为空间受限的复杂网络提供了一种具有地理信息的嵌入框架。
相关工作
网络几何旨在通过揭示网络的潜在度量属性来带来对网络结构理解范式的转变[28]、[29]。这一研究领域找到了众多应用,从大脑网络分析到互联网数据包路由[30]、[31]。在这一框架下,不断积累的实证和理论证据表明,许多真实世界网络的潜在隐藏度量空间是双曲的。先前的研究集中于隐藏空间重建。
隐藏空间重建
本节的目的是描述如何仅从网络拓扑重建一个隐藏的欧氏空间。基本假设是,观测到的邻接矩阵包含了关于节点之间潜在接近程度的隐含信息:在底层隐藏空间中距离较近的节点对被连接的可能性更大。因此,通过从网络结构中提取合适的谱坐标,我们旨在为每个节点分配一个低维欧氏空间中的位置。
真实网络中的真实位置与隐藏位置
为了验证隐藏空间模型的有效性,我们在真实网络和一个人工模型网络中探索了隐藏度量空间。意大利电力网络具有真实的地理位置信息,代表了意大利高压电气网络的拓扑,包含98个节点和175条边。其他三个真实世界网络分别是 Maayan-faa[53]、OpenFlights[53] 和 Euroroad[53]、[54]。这些网络的结构特性总结在表1中。
在链路预测中的应用
在本节中,我们将所提出的隐藏空间方法应用于六个真实世界网络:美国电力网络[53]、Maayan-faa[53]、OpenFlights[53]、Euroroad[53]、[54]、Yelp[55] 和 Maayan-pdzbase[53]、[56]。美国电力数据集代表美国西部电气电网,与第4节用于地理验证的意大利电力网络不同。这些数据集用于两个相关但不同的目的。对于地理验证,我们使用意大利……
结论
我们得出结论,网络拓扑和节点的有效空间组织都受到隐藏空间中节点间距离的强烈影响。在合成网络和真实世界网络上的实验结果表明,当隐藏空间坐标与实际地理位置高度相关时,可以仅通过网络连通矩阵准确地重建这些坐标,而无需任何关于真实地理信息的先验知识。这一特性尤其适用于……
作者贡献声明
Dai Yu:撰写——初稿,软件,方法论,形式化分析,概念化。Hui Li:项目管理,方法论,调查,概念化。Yifan Liu:软件,方法论,数据管理。Wei Zhang:撰写——审阅与编辑,软件,方法论。Zhen-Zhen Wang:撰写——初稿,方法论,调查,形式化分析。Jing Shen:软件,方法论。Zian Le:软件,数据管理。Mingyang Zhou:监督,方法论,形式化分析。Hao Liao
利益冲突声明
作者声明,他们没有已知的竞争性经济利益或个人关系,这些关系可能影响本文所述工作的报告。
Dai Yu | Hui Li | Yifan Liu | Wei Zhang | Zhen-Zhen Wang | Jing Shen | Zian Le | Mingyang Zhou | Hao Liao
广东工业大学,中国广东省广州市番禺区外环西路100号,510520
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号