链路预测：利用已知信息预测网络节点连接

（一）链路预测问题描述

链路预测就是利用网络中已知信息，预测网络中节点i和节点j是否有可能发生连接，以及两个节点间连接的可能性。

如图9-1-1所示，（a）为原始网络，共有4个节点，5条边。如果所有节点都有连边，那么网络中的连边数量为（4-1）×4/2=6条。从原始网络中的实际连边选择（b）训练集和（c）测试集，（d）为不存在边集。根据选择的链路预测算法，对测试集和不存在边集的节点对之间相似性进行打分，如果分值都大于不存在边集，那么说明选择的链路预测精确度比较高。使用预测精确度高的链路预测算法，对不存在边集的节点对之间相似性进行打分，分值越高的节点对，越可能有连接。对于原始网络（a）只有一条不存在边，所以下一个连接节点对就是节点2和节点3。

链路预测是数据挖掘的研究方向之一，在计算机领域应用较为广泛。随着复杂网络技术的深入研究，链路预测方法在网络中的应用也多了起来，主要应用在网络演化机制和网络发展方向上，推动复杂网络演化模型的发展。

图9-1-1　链路预测示意图

（二）数据集划分

根据上面链路预测问题描述部分的内容，我们知道链路预测的第一步就是划分数据集。对于数据集E，可以划分为训练集和测试集ET和EP，有E=ET∪EP，ET∩EP=ø。划分数据集的方法有多种，具体如下：

1.随机抽样

随机抽样方法就是假设随机划分数据集中比例为p的边作为测试集，剩余的边作为训练集。该方法保证了每条边被选入测试集的概率是相同的，在链路预测中使用广泛，但是不适用于样本分布严重不均匀的数据集。

2.K-折折叠交叉检验

K-折折叠交叉检验就是总共做K次实验，将样本随机分为K份，选择其中一份作为测试集，其余的K-1份为训练集，输入训练模型得到一个预测精度。重复K次，整个网络的预测精度为K次预测精度的平均值。这样所有的数据都被选择为了测试集，相较于随机抽样避免了样本不均匀导致的模型精度不可信。

3.逐项遍历

逐项遍历是一种比较精确的数据集划分方法，它每次都从网络中选择一条边为测试集，剩余的为训练集。遍历网络中所有的边，最后计算得到的平均值作为整个网络的预测精确度。但是该方法计算时间和复杂度较高，适合样本规模较小的网络。(www.xing528.com)

（三）模型评价指标

链路预测的最后一步就是对该算法进行准确性评价，合理的评价指标可以选择出适合该模型的最优链路预测算法。评价链路预测算法准确度的指标主要有三个：AUC、准确率（Accuracy）、精确度（Precision）。这三个指标考虑的侧重点有所不同，适用于不同的数据集。AUC是对算法整体准确度的测量；准确率是算法对数据预测正确的概率；精确率是只考虑排序靠前的边的准确度。

1.AUC值

AUC是指ROC曲线与坐标轴围成的面积。ROC曲线以假阳性率为横轴，真阳性率为纵轴，根据分类阈值绘制而成的曲线，被广泛用来评价分类器的效果。在链路预测问题中，我们并不需要画出具体的ROC曲线图，只需要AUC值。我们可以将AUC问题理解为求解测试集N P中随机选取一个节点对的分值，大于随机选取一个不存在边集M中节点对分值的概率。具体到模型来说就是，每次从测试集中N P选取一个节点对，再随机从不存在边集N中选取一个节点对，如果前者的分支大于后者，则加1分；如果两个值一样就加0.5分；然后重复操作n次。如果任意测试集N P中的节点对的分值，大于不存在边集M中节点对的分值，则AUC的值为1，为最好的链路预测算法。AUC定义如式（9-1）所示：

其中，n1表示测试集中的分值大于不存在边集的次数，n2表示二者分值相同的次数，n为重复操作的次数。

如果所有边的分数值不是按照相似性指标计算，而是随机产生的，那么AUC值应当接近于0.5，因此当AUC的值大于0.5时，说明该算法比随机预测方法要准确。理论上，n值最大为测试集的数据量。

2.准确率

准确率是指该链路预测算法预测正确的边数占所有网络边数的概率，是比较常见的一个评价指标。但是该指标在数据集正反例不平衡的情况下，不具有客观的评价结果。如果某个数据集有90%的样本为反例，10%的样本为正例，而我们的预测策略认为所有样本都为反例，准确率就为90%。从准确率结果来看，该预测模型表现优秀，但是该模型无法预测出正例样本。这是以准确率作为评价标准的缺点，只适合样本分布均匀的数据集。

3.精确度

有时候我们并不关注网络中所有连边的预测结果，而只是关注最可能产生连接的结果是否准确。比如某个机场要建立新航线，如果预测结果的前几个机场都是现在已经建立联系的机场，那么我们认为这样的模型精确度比较高。精确度就是定义前L个预测边预测正确的比例。如果其中有m条边来自测试集，那么精确度的定义为：

从上式可以看出，给定了L，精确度越高，模型预测准确度越高。