链路预测问题的介绍与优化

链路可以理解成一种特定的联系或者相互作用，故链路预测的本质就是预测两个事物之间是否拥有某种特定形式的联系。链路预测作为复杂网络研究中的分支，其本身脱离不了网络结构。

考虑一个无向网络G（V，E），其中V为节点集合，E为边集合。假定该网络共有N个节点，M条边，则全集U共有个节点对。通过特定的链路预测方法，对于每一对还没有连边的节点对（x，y）计算分数值Sxy，通过比较这些分数值的大小，发现得分最高的节点对出现连边的概率最大。

事实上，这是将问题简化后的描述，因为在实际生活中，网络不仅是有向的，而且不同的节点、边均具有不同的权重。目前，学者也对有向加权的链路预测做了不少研究。

在有了链路预测计算结果之后，还涉及算法精确度衡量的问题。将已知的连边集合E分为训练集ET和测试集EP两部分，E=ET∪EP，且ET∩EP=∅，属于U但不属于E的边代表不存在的边。计算节点对的分数值时，仅能使用训练集ET中的信息，即将整体网络划分为两部分，用一部分的信息去进行链路预测，将预测结果与另一部分网络实际情况进行比对，比对结果越相符代表预测精度越高。目前，较常使用AUC（Area Under the Receiver Operating Characteristic Curve）、Precision和Ranking score三种指标来衡量链路预测算法的精确度，三种指标各有侧重：AUC，也就是接受者操作特性曲线下面积，倾向于从整体角度去衡量算法准确性；Precision指标只考虑排序在前k位的边的预测准确性；Ranking score更注重于所选择的需要预测的边的排名次序。(www.xing528.com)

其中，从测试集中随机抽取一条链接和一条不存在的链接，那么AUC即表示为测试集的链接的相似度高于不存在的链接相似度分数的概率。将上述随机抽边的过程进行n次，如果两者分数值相同的次数有n1次，同时每次计0.5分；如果测试集中所抽边的分值大于不存在的边的分数值的次数有n2次，同时每次计1分。那么AUC的算术表达式为。

若所有分数值均随机产生，则AUC=0.5，说明测试集和训练集拥有相同的相似度分布，而当AUC大于0.5时，说明所使用的相似度算法更加有效，且值越大代表相似度算法精度越高。

Precision则为预测网络新增连边与实际网络新增连边中重合的边的数目占总的新增连边的比例。即通过相似度算法得到的边与测试集中的边进行比较，前n个预测边中有n1条属于测试集中的边，那么预测精度为Precision=×100%。