Physica A 2020 | 链接预测综述（一）：基于相似性的方法

题目：Link prediction techniques, applications, and performance: A

survey

期刊：Physica A

论文地址：https://www.sciencedirect.com/science/article/abs/pii/S0378437120300856

前面看了一些图嵌入、GNN以及节点预测的相关知识，关于graph的学习该步入链接预测了。由于这篇综述太长，所以分成几个部分来讲，本篇文章主要讲基于相似性的方法。

摘要

在静态网络中，链接预测用于发现缺失的链接，而在动态网络中，链接预测用于预测未来可能出现的链接。

链路预测是物理学（确实没想到）和计算机科学领域中一个快速发展的研究领域。现如今已经有了大量的链接预测技术，如基于相似性的索引、概率方法、降维方法等，本篇综述对这些方法进行了广泛的探讨。除了基于聚类和信息论的模型之外，本篇综述还将介绍基于学习的方法。本文还对相似性和其他一些有代表性的方法的实验结果进行了列表和讨论。为了使其具有一般性，本综述还涵盖了不同类型网络中的链路预测，例如有向网络、时态网络、二部网络和异质网络。

1. 引言和背景

社交网络（更一般的表述是复杂网络）可能具有高度动态性和复杂性。

问题定义：对于一个简单的无向网络

，如下所示：

本文设定了一种简单情况：不允许有多重边和自环。设有集合

，里面包含了一共

边，

，不存在的链接一共有

条，但其中某些链接可能在未来出现。链接预测的目标就是寻找缺失的链接，如上图中的AD、AC等。

文章组织：第2节介绍现有的一些链接预测方法；第3节讨论了一项实验研究，包括评估策略和几个真实网络数据集的基本拓扑信息，此外还探讨了基于相似性的方法的准确性和效率的实验结果；第4节总结了链路预测问题的变化；第5节描述了不同的应用场景；第6节阐述了链接预测当下一些最新的发展；第7节总结了这项工作，并提出了一些未来的方向。

2. 现有方法

现有的链接预测方法可以总结如下：

下面依次介绍这些方法。

2.1 基于相似性的方法

基于相似性的方法是链接预测中最简单的一种方法。对于每一对节点

，我们可以计算它们之间的相似性得分

。针对

，我们可以算出对应节点对之间的相似性得分，如果得分较高，则说明它们间有链接。

每一对节点之间的相似性可以使用网络的某些属性来计算，其中最主要的是结构属性。基于结构属性的分数可以分为几个类别，如局部和全局、节点相关和路径相关、参数相关和无参数等。

局部相似性指数

局部相似性通常使用公共邻居和节点的度信息来计算。主要包括以下17种：

（1）公共邻居(Common Neighbors, CN)

计算公式如下：

其中

和

分别表示节点

和

的邻居。CN被定义为两个节点公共邻居的数量。

简单来说，CN认为，如果两个节点拥有很多的公共邻居，那么它们就比较相似，节点间就很有可能存在链接。

（2）Jaccard系数(Jaccard Coefficient)

计算公式如下：

CN存在一个问题：如果一个节点的邻居很多，那么它与任何节点的CN指标都比较大。因此我们需要考虑节点邻居的数量，即如果两个人共同邻居的数量在他们所有好友数量中占比很大，那么它们更容易建立联系。不过Liben Nowell等人证明，与CN相比，这种相似性度量的性能更差。

（3）Adamic/Adar Index(AA)

Adamic/Adar指数定义如下：

这里

表示节点的度。Adamic/Adar指数同样是对CN的改进，简单来说，两个节点虽然拥有很多公共邻居，但每个邻居的重要性是不同的，不能等同。从公式可以看出来，如果某个邻居拥有更多度（更多的邻居），那么它的权重越小。比如在现实生活中，一个朋友较少的人恰好同时是A和B的朋友，那么A和B更有可能是朋友。

（4）优先链接(Preferential Attachment, PA)

PA定义如下：

PA被定义为节点度的乘积。PA认为，如果两个节点的邻居节点越多，它们俩成为邻居的概率也更大。不过根据后文的实验结果显示，PA的效果是最差的，但PA的计算很简单，成本低。在分类网络中，PA的性能有所提高，而在非分类网络中则非常糟糕。换句话说，如果度较大的节点密集连接，而度较低的节点很少连接，则PA显示出更好的结果。

（5）资源分配指数( Resource Allocation Index, RA)

RA被定义为：

RA指数和AA指数很相似。不同的是，RA对高度节点的惩罚更大。RA指数在具有高聚类系数的异质网络上显示了良好的性能，尤其是在交通网络上。

（6）余弦相似性 or 索尔顿指数(Cosine similarity or Salton Index, SI)

SI指数定义如下：

在向量空间中，我们一般可以利用SI计算相似性。

（7）Sorensen Index

Sorensen Index定义如下：

Sorensen Index主要用于生态数据，它比Jaccard更能抵抗异常值。

（8）CAR-based Common Neighbor Index(CAR)

CAR定义如下：

这里

表示节点

邻居的子集。

是指本地社区的链接数量。CAR认为，如果两个节点的公共邻居是本地社区的成员，则它们间存在链接的可能性很大。

（9）CAR-based Adamic/Adar Index (CAA)

定义如下：

（10）CAR-based Resource Allocation Index (CRA)

定义如下：

（11） CAR-based Preferential Attachment Index (CPA)

将LCL和PA结合得到CPA，定义如下：

其中

表示节点

未与节点

共享的邻居数。

上面列出的这些基于CAR的度量方法在LCP网络上显示出最佳性能，LCP网络与动态和异质系统相关。

（12）Hub Promoted Index (HPI)

HPI定义为：

（13）Hub Depressed Index (HDI)

HDI定义为：

（14）Local Naive Bayes-based Common Neighbors (LNBCN)

LNBCN定义为：

其中

是节点聚类系数，

是网络密度：

（15）Leicht–Holme–Newman Local Index (LHNL)

LHNI被定义为：

（16）节点聚类系数(Node Clustering Coefficient, CCLP)

CCLP被定义为：

这里

是节点

的聚类系数，定义为：

表示通过节点

的三角形总数。

（17）Node and Link Clustering coefficient (NLC)

节点和链接聚类系数被定义为：

全局相似性指数

全局指数是使用网络的整个拓扑信息计算的，这种方法的计算复杂度更高，似乎不适用于大型网络。下面我挑了几个比较经典的指标：

（1）Katz Index(KI)

Katz Index定义如下：

这里

表示节点

和

间长度为

的路径的数量，

为邻接矩阵，

中每个数都为相应节点对间长度为

的路径数量，

是控制路径权重的衰减因子，为了保证收敛，

必须满足以下条件：

其中

为邻接矩阵A的最大特征值。

简单来说，KI聚合了两个节点间的所有路径，路径越长权重越小。

（2）Random Walk with Restart (RWR)

考虑一个从节点

开始的随即游走，它以

的概率移动到下一个邻居节点，然后以

的概率返回到节点

。

表示该随机游走在稳态下位于节点

的概率。这个概率可以表示为：

这里

是长度为

的seed vector。转移矩阵

定义如下：

此时概率可以简化为：

由于这种相似性是不对称的，因此节点对(x, y)之间的最终相似性得分可以计算为：

（3）Shortest Path

定义如下：

其中

是利用Dijkstra算法得到的节点间的最短路径。

此外，还有LHNG、 、ACT、NACT、MF等全局相似性指标，这里不再具体阐述了，需要了再看。

准局部相似性指数

准局部指数是作为局部和全局方法性能和复杂性之间的权衡而引入的。这里只介绍Local Path Index(LP)。

LP的表达式如下：

这里

是自由参数。显然，如果

，则测量值收敛到公共邻域。广义上的LP：

其中

为最大阶数。随着

的增加，LP计算将变得复杂。一些论文发现，LP优于一些基于近邻性的指标，如RA、AA和CN。