一种新颖的基于引力场的链路预测方法

摘要

本发明涉及链接预测技术领域，涉及一种新颖的基于引力场的链路预测方法，包括以下步骤：一、用节点的重要性来衡量万有引力方程中的质量属性，用节点之间的相似性来衡量万有引力方程中的距离属性；二、考虑节点间的直接和间接引力值，提出基于引力场的新型链接预测框架LPFGF，并得到节点间相似度框架计算方程；三、将LPFGF扩展到多种链路预测算法，形成了新的链路预测算法，并进行链路预测。本发明能较佳地进行链路预测。

说明书

技术领域

本发明涉及链接预测技术领域，具体地说，涉及一种新颖的基于引力场的链路预测方法。

背景技术

利用网络的特征、结构和节点信息来预测两个不相连的节点之间的链接概率的过程被称为链接预测。链接预测包括对隐性链接(存在于现实世界的网络中，但不易被观察到)和未来链接(不存在于网络中，但随着网络的发展和外部信息及其他因素的影响，未来可能会出现)的预测。

链接预测的应用给人类社会带来了极大的便利。例如，链接预测在社交网络中被用来预测两个互不相识的人将来成为朋友的可能性，在蛋白质相互作用网络中也被用来发现最有可能发生相互作用的蛋白质结构，然后做相互作用实验，可以提高实验成功率。随着数据的爆炸性增长，网络中的错误链接和隐性链接越来越多，通过链接预测方法可以纠正和删除错误的链接，显示隐性链接。链接预测在网络建模、推荐系统、节点分类、网络重建和知识获取等应用中也很常见。

引力场是空间中两个质量物体产生相互引力的模型。引力值由物体的质量、物体之间的距离和万有引力常数决定。当物体的质量越大，物体之间的距离越小，这两个物理之间的引力就越大。这与分析复杂网络中的节点与节点之间的相互作用很相似。当网络中节点的重要性越大，节点之间的距离越短，说明这两个节点之间的关系强度越大，从而说明这两个节点在未来连接的概率越高。因此，基于这样的考虑，引入万有引力方程来模拟复杂网络中节点之间的关系强度，并将解决节点之间未来连接概率的问题投射到物理空间来解决。

随着复杂网络的快速发展，链路预测得到了研究人员的广泛关注，并提出了不同的链路预测算法。目前，主要有以下三类。

第一类是基于节点相似度的链接预测算法。第二类是基于最大似然估计的链接预测算法。第三类是基于机器学习的链接预测算法。上述算法都是利用网络的局部信息结构或节点信息来计算节点对之间的连接概率，而不是从物理空间计算概率。目前，有一些关于将引力场引入复杂网络的研究。例如，从物理学的角度，将欧几里得空间中的数据点视为复杂网络中的节点，将数据对象之间的关联视为复杂网络中的节点关系，发现欧几里得空间中的数据结构与复杂网络的拓扑结构非常相似，并构建了一个二维静态数据的数据场，这给复杂网络研究界带来了很大的影响，使许多研究者从物理学的角度研究和分析复杂网络的拓扑特性。在万有引力公式中，质量是代表物体在引力场中的重要性的最基本属性。物体之间的引力随着物体质量的增加而增加。在复杂网络中，度是反映节点重要性的最直观的属性。利用节点的度来确定节点的重要性，然后在复杂网络中建立了一个引力场模型。他们将该模型应用于对节点的重要性进行排序的任务。然而，他们忽略了一些小度节点在网络中起着至关重要的作用，如连接两个团的桥节点，使用这个模型来评估节点的重要性很容易导致不准确的结果。

发明内容

本发明的内容是提供一种新颖的基于引力场的链路预测方法，其能够克服现有技术的某种或某些缺陷。

根据本发明的一种新颖的基于引力场的链路预测方法，其包括以下步骤：

一、用节点的重要性来衡量万有引力方程中的质量属性，用节点之间的相似性来衡量万有引力方程中的距离属性；

二、考虑节点间的直接和间接引力值，提出基于引力场的新型链接预测框架LPFGF，并得到节点间相似度框架计算方程；

三、将LPFGF扩展到多种链路预测算法，形成了新的链路预测算法，并进行链路预测。

作为优选，步骤一中，网络G的凝聚度

其中n≥2,D

从方程(1)中发现，收缩节点v

其中k

从方程(1)和(2)中得出，如果一个节点的度数很大，而且该节点在网络中处于关键位置，收缩该节点后，整个网络将被压缩成一个更紧凑的网络，通过该节点的最短路径长度也将缩短；

为了量化节点v

其中

从公式(3)得出，节点的重要性与节点的程度和位置有关；收缩节点v

因此，为了实现节点重要性的归一化，节点v

其中，

作为优选，步骤一中，使用节点重要性来衡量万有引力方程中的质量属性M，因此，有：

M

通用引力方程的距离属性r是由节点相似度S(a,b)确定，两个节点越相似，两个节点之间的距离就越短；有：

如果节点b和节点a相似，节点b在网络中重要性大，那么节点b对节点a产生的引力值就大，那么这两个节点之间的关系就密切；因此，引力值为：

G′为引力常数，由于G′存在于所有方程中，所以忽略；因此，节点a和b之间的引力值为：

用节点间的直接引力值来衡量节点间的关系强度，另外考虑节点间的间接引力值，使预测结果更加准确，即，首先计算目标节点的所有邻接节点对另一个目标节点产生的引力值之和，然后对直接引力值和间接引力值这两部分进行求和运算，从而得到节点间的相似度值。

作为优选，新型链接预测框架LPFGF中，分为模块1和模块2；

模块1中：

首先，输入网络G，然后将网络数据集划分为训练集和测试集；其次，计算邻接矩阵A；如果有一条连接v

模块2中：

首先，通过利用基于节点相似度的链接预测基准方法，得到相似度矩阵S；第二，将每个节点的重要性和两个节点之间的相似度值代入引力值公式；第三，考虑节点间的直接和间接引力值来评估节点间的关系强度，然后推导出节点间的相似度框架计算方程，得到相似度矩阵S′；最后，通过对S′进行归一化，得到归一化的相似性矩阵S″。

作为优选，链路预测基准方法为CN、AA、RA和LRW。

本发明利用节点收缩后的节点重要性来衡量万有引力方程中的质量属性，用引力来评价节点之间的关系强度，所提出的LPFGF算法框架可以成功地提高其他链接预测算法的预测性能，最大提高幅度为15％。本发明不仅考虑了小度节点重要性，而且克服了因删除节点而造成的网络断裂问题。

附图说明

图1为实施例1中一种新颖的基于引力场的链路预测方法的流程图；

图2为实施例1中收缩节点的示意图；

图3为实施例1中由节点3、4、5及其相邻节点组成的网络示意图；

图4为实施例1中LPFGF的算法框架示意图；

图5(a)为实施例1中Citeseer数据集的度分布示意图；

图5(b)为实施例1中DBLP数据集的度分布示意图；

图5(c)为实施例1中Cora数据集的度分布示意图；

图5(d)为实施例1中Wiki数据集的度分布示意图；

图6(a)为实施例1中Citeseer数据集使用NLPGF算法前后原始基准方法的平均AUC值比较示意图；

图6(b)为实施例1中在DBLP数据集使用NLPGF算法前后原始基准方法的平均AUC值比较示意图；

图6(c)为实施例1中在Cora数据集使用NLPGF算法前后原始基准方法的平均AUC值比较示意图；

图6(d)为实施例1中在Wiki数据集使用NLPGF算法前后原始基准方法的平均AUC值比较示意图。

具体实施方式

为进一步了解本发明的内容，结合附图和实施例对本发明作详细描述。应当理解的是，实施例仅仅是对本发明进行解释而并非限定。

实施例1

如图1所示，本实施例提供了一种新颖的基于引力场的链路预测方法，其包括以下步骤：

一、用节点的重要性来衡量万有引力方程中的质量属性，用节点之间的相似性来衡量万有引力方程中的距离属性；

二、考虑节点间的直接和间接引力值，提出基于引力场的新型链接预测框架LPFGF，并得到节点间相似度框架计算方程；

三、将LPFGF扩展到多种链路预测算法，形成了新的链路预测算法，并进行链路预测。将该框架扩展到CN、AA、PA和LRW等多种链路预测算法，形成了LPFGF-CN、LPFGF-AA、LPFGF-PA、LPFGF-LRW等链路预测算法。

相关定义

节点收缩：当收缩网络G中的任何节点v

链路预测：设G＝(V,E)是一个无定向网络，U是网络G中可能存在的最大边数，其中U＝|V|(|V|-1)/2，U-E是网络G中不存在的边集。所以，链接预测被描述为找出未来最有可能形成边的顶点对。在本实施例中，未连接的节点之间的相似度是由提出的链接预测方法计算出来的，从大到小排序。相似度值越高，连边概率就越高。

一种改进的节点重要性评估方法

网络G的凝聚度

其中n≥2,D

从方程(1)中发现，收缩节点v

其中k

可以从方程(1)和(2)中推断出，如果一个节点的度数很大，而且该节点在网络中处于关键位置，收缩该节点后，整个网络将被压缩成一个更紧凑的网络，通过该节点的最短路径长度也将缩短，说明该节点在网络中很重要。

为了量化节点v

其中

从公式(3)可以看出，节点的重要性与节点的程度和位置有关。收缩节点v

因此，为了实现节点重要性的归一化，节点v

其中，

基于引力场的链接预测框架

普遍的引力方程定义如下：

其中G'是引力常数，M代表物体的属性，如质量和重要性，r是两个物体之间的距离。

复杂网络中的节点之间的关系强度，很像物体之间的引力。节点之间的关系取决于节点本身的程度、特征、间性和重要性，并取决于节点之间的距离。因此，用引力来评价节点之间的关系强度，并将节点之间的相似性问题投射到物理空间中来解决。

质量是能够反映物体在引力场中的重要性的最基本特征。在复杂网络中决定节点重要性的最重要的变量之一是节点度。然而，一些小度节点对网络也很重要，如连接两个团的桥节点。因此，使用基于节点收缩的改进的节点重要性评价方法来衡量万有引力方程中的质量属性M。因此，有：

M

通用引力方程的距离属性r是由节点相似度S(a,b)。两个节点越相似，两个节点之间的距离就越短。有：

如果节点b和节点a比较相似，节点b在网络中重要性较大，那么节点b对节点a产生的引力值就比较大，那么这两个节点之间的关系就比较密切。因此，引力值为：

为了区分网络G，这里的引力常数用G′表示。由于G′存在于所有方程中，所以它可以被忽略。因此，节点a和b之间的引力值为：

用节点间的直接引力值来衡量节点间的关系强度，另外考虑节点间的间接引力值，使预测结果更加准确，即，首先计算目标节点的所有邻接节点对另一个目标节点产生的引力值之和，然后对直接引力值和间接引力值这两部分进行求和运算，从而得到节点间的相似度值。

接下来，将用一个简单的例子来说明这个过程。图3显示的是一个由节点3、4、5及其相邻节点组成的人工网络。x的相邻节点的集合用Γ(x)表示。

(1)节点3和节点5之间的直接引力值为：

F

(2)节点3和节点5的邻居节点之间的引力值是：

F

F

F

F

(3)节点5与节点3的邻居节点之间的引力值为：

F

F

F

(4)将节点3和5之间的直接和间接引力值相加，得到节点3和5之间的相似度值为：

因此，根据公式(17)，得到任意两个节点u和v之间的相似性算法框架方程为：

将这个算法框架应用于不同的链接预测算法，会得到不同的相似度结果。将这个相似性矩阵归一化，最后得到的相似性框架方程为：

其中|V|是网络中节点的数量。

此外，还提供了一个LPFGF的算法框架图。LPFGF的算法框架可以分为两个部分，如图4所示。各部分的具体描述如下。

新型链接预测框架LPFGF中，分为模块1和模块2；

模块1中：

首先，输入网络G，然后将网络数据集划分为训练集和测试集；其次，计算邻接矩阵A；如果有一条连接v

模块2中：

首先，通过利用基于节点相似度的链接预测基准方法，得到相似度矩阵S；第二，将每个节点的重要性和两个节点之间的相似度值代入引力值公式；第三，考虑节点间的直接和间接引力值来评估节点间的关系强度，然后推导出节点间的相似度框架计算方程，得到相似度矩阵S′；最后，通过对S′进行归一化，得到归一化的相似性矩阵S″。

链接预测基准方法为CN、AA、RA和LRW等。

实验结果与分析

实验数据集

Citeseer、DBLP、Cora和Wiki数据集，用于测试所提出的LPFGF算法框架是否是一个有效的预测框架，其拓扑学属性总结于表1，其中|V|表示节点数，|E|表示边的数量，|Y|表示网络标签的数量，K表示平均程度，D表示网络直径，L表示平均路径长度，P表示密度，C表示平均聚类系数。

表1四个数据集的拓扑特性

评价指标和基准方法

评价链接预测算法的预测精度的三个重要指标是AUC,Precision和RankingScore。本实施例通过AUC评价指标对链接预测性能进行评估。一般来说，AUC值应大于0.5，不超过1。

为了评价所提出的LPFGF算法框架的预测性能，利用了18种基于相似性的不同链接预测算法作为基准算法，并比较了这些算法在采用LPFGF框架前后的链接预测性能。此外，为了强调所提出的LPFGF框架的贡献，还提供了4个前经典网络表示学习模型的预测性能，即DeepWalk、Node2Vec、LINE和SDNE在链接预测任务上的预测性能作为比较。

度分布的可视化

度分布被定义为网络中节点度的概率分布。图5(a)、图5(b)、图5(c)、图5(d)显示了Citeseer、Cora、DBLP和Wiki的度分布。通过观察四个数据集的度分布，在Citeseer和Cora数据集上，大多数节点的度主要集中在0和10之间，而在DBLP和Wiki数据集上，大多数节点的度主要集中在10和50之间。根据节点的密度，结合表1中四个数据集的拓扑特性描述，可以发现Citeseer和Cora数据集是相对较稀疏的网络，而DBLP和Wiki数据集是相对较密集的网络。

实验结果

本实施例采用随机抽样的方法来划分四个数据集。四个数据集的训练比例分别设定为0.7、0.8和0.9。实施结果分别为进行10次实验后得到的平均值为最终结果。

表2和表3显示了应用LPFGF框架前后18个基于节点相似性的基准指标的预测结果，以证明LPFGF算法框架的可行性。

表2列出了相关工作中列出的原始链接预测基准算法的原始AUC值。AUC结果显示，在DBLP和Wiki数据集上，整体预测性能较好。在这四个数据集上，只有六种算法的链接预测准确率高于80％，占33.3％，它们是LP、Katz、LHNII、LRW、SRW和MFI，其中Katz和MFI算法的预测性能优于其他算法，其准确率在这四个数据集上高于90％。然而，CN、Salton、HPI和其他算法在Citeseer数据集上的预测精度很差，最低为65.8％。通过实验结果发现，与四种基于节点相似性的链接预测方法相比，基于路径的、基于随机游走的和其他的链接预测算法在预测性能方面比基于局部信息的算法更好。

表2原始链接预测算法的AUC值比较(％)

表3列出了在使用提出的LPFGF算法框架后基于节点相似性的链接预测基准方法的AUC值。观察表3的结果，在DBLP和Wiki数据集上，使用提出的LPFGF算法框架后，整体预测性能较好，AUC值基本达到90％以上。在这四个数据集上，有10种算法的链接预测精度高于80％，占55.6％，它们是Salton、HDI、LHNI、LP、Katz、LHNII、LNBCN、LRW、SRW和MFI。其中，Katz、LHNII和MFI算法在链接预测方面有较好的表现，其在四个数据集上的预测精度都高于90％。特别是在Citeseer数据集上，它们的准确率超过了93％。PA算法在Citeseer、DBLP和Wiki数据集上的结果接近于原始结果，而在Cora数据集上的结果则略有下降。与四种基于节点相似性的链接预测方法相比，发现这四种链接预测算法在应用LPFGF框架进行优化后，其性能都有一定程度的提高。相比之下，LPFGF框架在提高基于网络局部信息的链接预测基准方法的性能方面更为成功。

表3使用LPFGF框架优化后的原始链接预测算法的AUC值比较(％)

提供图6(a)、图6(b)、图6(c)、图6(d)作为原始基准方法在使用LPFGF算法框架前后的平均AUC值的对比图，这样可以更直观地看到原始基准方法在使用LPFGF算法框架前后的预测性能变化。平均AUC值是指每个数据集上AUC值的平均值。在图6(a)、图6(b)、图6(c)、图6(d)中，横轴代表原始基准方法，纵轴代表平均AUC值，带有三角形符号的折线代表使用LPFGF框架前原始基准方法的平均AUC值，带有玫瑰圆圈符号的折线代表使用LPFGF框架后原始基准方法的平均AUC值。

从图6(a)、图6(b)、图6(c)、图6(d)中可以看出，在使用所提出的LPFGF框架后，链接预测方法的预测性能得到了很大的提高。尤其是CN、Salton和HPI方法，在Citeseer和Cora数据集上的预测性能提高了15％。PA略有下降，但接近于原来的结果。LP、Katz、LRW和SRW在Citeseer和Cora数据集上略有改善，而在DBLP和Wiki数据集上基本相同。当PA算法被LPFGF框架优化后，它将节点收缩作为节点重要性评估方法。根据公式(2)和(4)，节点的重要性不仅由其度决定，还由其位置决定。如果节点的度数很高，但它在网络中不处于关键位置，那么该节点可能不是至关重要的。PA算法只考虑了节点度对节点相似度的影响。因此，它导致了轻微的性能下降。因此，将节点间的相似性问题投射到物理空间中去解决是有效和可行的。

如表4所示，提供了所提出的算法，如LPFGF-CN、LPFGF-Salton、LPFGF-HPI等的预测性能与四种前经典网络表征学习模型的预测性能的比较，这四种模型是DeepWalk、Node2Vec、LINE和SDNE在训练率为0.8的Cora和Citeseer数据集上的预测。需要注意的是，除了原来的基准算法的预测性能高于这四种基于网络表征学习模型的链接预测外，其他的都列在表4中，这些算法都是由提出的LPFGF算法框架优化的。

表4 LPFGF框架和四种网络表示学习算法的AUC值比较(％)

表4显示，在提出的LPFGF算法框架优化后，其他经典链接预测算法的预测性能在一定程度上优于前期经典网络表征学习模型，这进一步说明提出的LPFGF框架是可行的、成功的。

时间复杂度分析

建议的算法框架分为两部分，每一部分都将单独考察其时间复杂性。第一部分是计算节点的重要性。计算节点重要性的过程需要使用Floyd算法计算最短距离矩阵，并在收缩节点后找到凝聚度矩阵，Floyd算法和找到凝聚度矩阵的时间复杂度分别为O(N

总结

本实施例首先引入万有引力方程来评价复杂网络中节点之间的关系强度，其次利用节点收缩法得到的节点重要性来衡量通用引力方程的质量属性，利用节点之间的相似度来衡量通用引力方程的距离属性，提出基于引力场的链接预测框架，简称LPFGF。然后，得到了节点之间的相似性方程，然后将节点之间的相似性问题投射到物理空间来解决。最后，在四个实际数据集上的仿真结果显示，利用LPFGF框架，大多数基于节点相似性的链接预测算法的预测性能都有一定程度的提高。

以上示意性的对本发明及其实施方式进行了描述，该描述没有限制性，附图中所示的也只是本发明的实施方式之一，实际的结构并不局限于此。所以，如果本领域的普通技术人员受其启示，在不脱离本发明创造宗旨的情况下，不经创造性的设计出与该技术方案相似的结构方式及实施例，均应属于本发明的保护范围。