如何选择链路预测指标？

在关于链路预测的相关研究中，链路预测的指标有30多种。大致可以分为三类：基于相似性、基于极大似然估计和基于概率模型的链路预测指标。目前应用最广泛的是基于节点相似性的链路预测指标，属于比较成熟的指标，它不仅能够考虑网络的局部或者全局特征，也能够刻画出网络结构特征。而且基于节点相似性的链路预测指标定义和计算简单，计算复杂度不高，预测精度高，适合规模较大的网络。准确定义节点之间的相似性不是一件容易的事情，这些相似性指标无法保证在所有网络中都拥有较好的预测结果。可能某个指标只对某类网络具有较高的预测精确度，而对于其他类型网络预测精确度较低。所以学者更多的是从网络结构出发，寻找节点的网络结构相似性，保证节点相似性数据的可靠性。

基于网络结构相似性的指标众多，可以分为三大类：基于局部信息的相似性指标、基于半局域信息的相似性指标、基于全局信息的相似性指标。所以本文将基于网络结构相似性从三个分类中选取共八个在物流网络方面应用较多的链路预测指标。

（一）基于局部信息的相似性指标

基于局部信息是指只通过网络中节点的局部信息，比如节点度和共同邻居来计算的相似性指标。相较于其他指标而言，计算复杂度较低，适合样本规模较大的网络。

1.CN指标

CN指标认为两个节点间的共同邻居越多，两个节点越有可能相连。在“一带一路”国家航空网络中指两个国家间共同存在航班连接的国家数量越多，两个国家越有可能有航班联系。CN指标所包含的信息较少，但是计算复杂度低，适合大规模节点网络。

公式中的Γ（i）、Γ（j）分别表示i节点和j节点的邻居节点的集合。

2.AA指标

AA指标将节点间共同邻居节点度值的大小考虑进来，由共同邻居的节点个数来分配每个节点的权重比例。认为某两个共同邻居的度值越小，这两个节点越相似，则越可能有连接。

公式中的kz为节点i和节点j的共同邻居k的度值。

3.RA指标

RA指标与AA指标类似，只是对度值的惩罚的权重不同。AA是以1/logk的形式下降，而RA是以1/k的形式下降。当网络的平均度较小时，二者的结果差别不大；否则会出现较大差异。

（二）基于半局域信息的相似性指标

基于半局域信息是指考虑某个节点与其他节点较短路径内的相似性，其中也可以度值和共同邻居数量为权重。

1.LP指标

LP指标是在CN指标的基础上考虑多三阶路径。当ε等于0时，LP指标就是CN指标。

公式中（A2）ij、（A3）ij分别指节点i和节点j之间路径长度为2和3的路径数。(www.xing528.com)

2.LRW指标

为降低计算复杂度，LRW指标为考虑有限步数t内的随机游走过程。（t）为粒子从节点i出发随机游走到节点j的概率。公式如下：

qi=ki / M表示节点i的初始资源分布，M为网络中的总边数，ki为节点i的度值。ρij（t）表示离子在t时刻从节点i出发，在t+1时刻刚好在节点j的概率。

3.SRW指标

SRW指标是将LRW指标t步及以前的结果进行加总。这个指标给距离上临近目标节点的点更多的机会与目标节点相连，考虑了网络的局域性。

（三）基于全局信息的相似性指标

基于全局信息是考虑某个节点在网络中到其他所有节点的路径长度等所有的信息，包括的信息最全面，但是计算复杂度较高，计算时间较长。

1.Katz指标

Katz指标考虑了网络中所有路径，根据路径长度给定不同的惩罚机制，路径长度越短权重越大。对于路径长度短的赋予较小的惩罚，对于路径长度长的赋予较大的惩罚，权重呈衰减系数。

公式中（Ai）ij为节点i和节点j间路径长度为i的路径数，β要小于邻接矩阵最大特征值的倒数。

2.RWR指标

RWR指标是PageRank的拓展应用。它假设网络中的粒子，每游走一步都有一定概率返回原始出发点，是具有重启特性的随机游走。某一个粒子t时刻在节点i处，那么t+1时刻该粒子达到网络各个节点的概率向量为

公式中c为粒子不返回原始点的概率，ei表示一个一维一列向量仅有第i个元素为1，其他都是0，P为该网络的马尔科概率转移矩阵。

所以RWR相似性为

公式中ρij为节点i出发的粒子走到节点j的概率。