基于图勾勒的图链路预测方法

尤洁，李劲,2，张赛，李婷

（1. 云南大学 软件学院，云南 昆明 650091； 2. 云南省软件工程重点实验室，云南 昆明 650091）

图上的链路预测是指通过已有的网络拓扑结构和节点属性信息等预测网络中尚未产生连边的两个节点之间产生链接的可能性，或者是已经产生但是并未发现的链接信息，是图数据挖掘的重要方向之一，受到广泛的关注。

当前，关于链路预测的研究方法主要包括3种：1)基于极大似然估计的方法。该方法将网络链接看作是内在层次的反映，采用极大似然估计进行预测。但该方法的预测准确性与样本数据量有关，高质量的预测需要大的样本数据，导致计算复杂度高，不适用于大规模网络[1-2]；2)基于概率模型方法。通过建立可调参数模型再现网络的结构和关系特征，将预测问题转化为预测边的属性问题进行预测，此类方法具有较高预测精度，但预测过程中涉及到非普适性的参数和节点属性信息，使得应用范围受限，计算复杂度高[3]；3)基于节点相似性预测方法[4-14]。假设节点之间存在链接的可能性与节点之间的相似性紧密相关，通过预测节点之间的相似性来进行链路预测。其中，基于节点相似性模型的预测方法由于方法简单，链接预测质量较好等成为目前主流的链接预测方法。

针对已有研究工作的不足，本文在保证链路预测质量的前提下，降低预测算法的计算复杂性角度，提出基于图勾勒[16]的链路预测算法。首先，基于图勾勒技术对现有的链路预测方法进行扩展，定义了基于ADS(all-distances sketches)结构的链路预测相似性度量指标，提出了基于图勾勒的链路预测算法，将一般链路预测算法的计算复杂度由降低至，其中是ADS勾勒参数，是网络节点数。其次，基于并行图计算平台Spark，提出了ADS的并行计算方法以及基于ADS技术的并行链路预测实现方法。从算法运算时间和预测精度两方面验证算法的有效性，实验结果表明：基于ADS技术的链路预测算法可以保证一定预测精度，同时降低预测方法的时间复杂度，提升运算效率。

1 背景知识

1.1 链路预测

下面分别给出本文中采用的3种节点间相似度度量指标及定义：

定义1Common Neighbor(CN)[5]：如果图中两个节点拥有的共同邻居节点越多，那么这两个节点就越相似，则它们之间存在或者未来发生链接的可能性就越大。相似度定义为

定义2Adamic Adar(AA)[6]：AA在CN的基础上，赋予邻居节点权重，它认为共同邻居节点的节点度对相似度也有影响，共同邻居节点度越大，它对节点相似度的贡献越小，反之，共同邻居节点度越小，它对节点的相似度的贡献越大。因此在求相似度的公式中，对共同邻居节点度赋予一个惩罚因子。其相似度定义为

定义 3Resource Allocation(RA)[7]：RA 从资源分配的角度考虑节点相似性。它认为没有直接相连的两个节点，资源可以从一个节点传递到另一个节点，它们的共同邻居节点是两个节点传递资源的媒介，每一个媒介都有一个单位的资源，它将自己的资源平均分配给它的邻居节点，另一个节点接收到的资源数就是这两个节点的相似度。其相似度定义为

评估指标：链路预测结果的衡量指标主要包括Precision(准确率)[17]和AUC(曲线下面积)[18]，Precision针对局部结果进行评估，AUC基于全局进行评估，本文讨论的是整体性能，故以AUC作为预测精度的评估标准。AUC的值越高，则链路预测整体性能较好。

定义4对于边集进行数据划分，有E =，假设是属于全集，但是不属于边集，从中取出一条边的预测值记为，从中选出一条边的预测值记为，比较次，若，若，否则不计数，具体如下：

1.2 图勾勒技术

ADS(all-distances sketches)是定义在图节点上的数据摘要结构。通过对图中各节点的可达邻居节点集进行抽样，抽样结果与原节点的集合构成了该节点的Sketch结构。在大图上，基于ADS可有效进行节点相似关系，中心度等度量计算[16]。v

定义5节点的All-Distances Sketches(ADS)的定义如下[16]：

例1图的ADS结构如图1所示，该图为有向图带权图。节点上的数值为勾勒ADS结构所对应生成的0 ～ 1的随机数。

图 1 图的ADS示例Fig. 1 An illustration of ADS in a graph

图中每个节点的ADS结构是一个集合。以节点 1 为例，ADS(1)()={(1，0)，(2，8)，(3，9)，(4，18)，(6，18)}表示在图中随机值取值情况下，ADS勾勒参数为2时节点1的ADS结构，集合中元素(4，18)表示节点1到节点4的最短距离是18。例如：

2 链路预测方法

ADS是对节点的全局邻居节点进行抽样，而CN、AA、RA 3种算法的默认情况是基于1跳邻居进行计算的，故为了排除多跳邻居对相似度的影响，基于节点的ADS结构的链路预测算法中也只考虑一跳邻居节点。基于1跳邻居的ADS的大小永远不大于节点的1跳邻居数，所以在求两个集合的相似度时，运算量也相应减少。在AA算法和RA算法中还涉及到求共同邻居节点的度，其他相似性度量指标也涉及到节点中心度的计算等，这个过程中需要耗费大量的计算时间，而ADS抽样的过程中会过滤掉一部分的邻居节点，故在一定程度上减少了部分求节点度、中心度的运算量。

对图勾勒后，得到的ADS结构不再是单一的节点集、边集所构成的图数据，而是由节点及其部分邻居节点构成的集合，这部邻居节点包括了一跳至多跳另据节点，还带有相应的可达距离，故ADS需要根据自身结构定义合适的相似性指标，具体定义如下：

定义6基于ADS的CN度量指标(ADS-CN)定义如下：

定义7基于ADS的AA度量指标(ADS-AA)如下：

定义8基于ADS技术扩展的RA度量指标(ADS-RA)定义如下：

公式中符号含义同定义6。

2.1 基于ADS勾勒技术的链路预测算法

首先简要介绍链路预测算法的基本思想，链路预测算法首先将待预测数据集划分为训练集和测试集。找出训练集中不存在连边的节点对，得到中不存在连边的数据集和，并计算节点对的相似度值，随机从和中各选出一条边，比较它们的相似度的值，重复多次，根据AUC公式定义，得到预测精度。基于ADS勾勒技术的链路预测算法的基本思想：在计算节点对相似度之前，构造出边集的图结构，对图进行ADS勾勒处理，得到中每个节点的ADS结构，根据基于ADS结构定义的相似性度量指标进行链路预测。由于节点的ADS是独立于图的，这样带来的优势是原图有些节点发生变化以后，只需要更新变化节点的ADS，带来的好处是可以独立动态更新节点的ADS结构，更新代价小；处理后的数据另一个优点是利于并行化处理，每个节点及其ADS结构与其他节点时独立的，在其他并行框架下，每个节点ADS互不干扰，利于并行。基于ADS勾勒技术的链路预测算法的具体描述如算法1。

分析算法1的时间复杂度。首先，由文献[16]可知，对于图中的一个节点，的期望大小为其中是从节点出发的可达邻居节点数，是第i个调和级数，由于()且，所以的期望大小为。于是，基于ADS技术求图中节点相似度的时间复杂度为。

算法1基于ADS勾勒技术的链路预测算法

输入，预测值比较次数n，勾勒参数K；

输出AUC值。

1) 切割边集E为训练集Er和测试集Ep，；

//找出训练集中不存在连边的结点对集合

2.2 基于ADS勾勒技术的并行化链路预测算法

为提高链路预测算法的执行效率，在算法1基础上，进一步提出了基于Spark的并行化的链路预测算法。该算法具体描述如算法2。算法2的执行过程与算法1一致，但算法2将算法1中的每一步骤采用弹性分布式数据集(RDD)进行了实现。基于RDD表示，采用对RDD的Map-reduce并行化操作有效提升链接预测算法的执行效率。RDD转换和操作细节详见算法2中的描述。

算法2基于Spark的并行化链路预测算法G(V,E)

输入，预测值比较次数n；

输出AUC值。

//找出训练集中不存在连边的结点对集合

//求出各顶点的邻居节点

//求出各结点的节点度

//求结点x, y的相似度

3 实验结果

3.1 实验环境设置

表 1 实验数据集拓扑结构信息Table 1 Experimental dataset topology information

本文实验在USAir97(美国航空网络数据[17])、Yeast(酵母菌蛋白质相互作用网络数据[18])、Grid(美国电力网络数据[19])3个数据集上进行测试，实验结果主要对链路预测算法和基于ADS勾勒技术的链路预测算法两种算法的运行时间和预测精度进行对比分析。实验环境包括内存：64 GB；处理器：inter(R) Xeon(R) CPU E5-2620 v3 @ 2.40 GHz 2.40 GHz；开发平台：Intellij IDEA 2016.2.5+Spark GraphX；开发语言：Scala。

本次所有实验结果均是对数据集进行10次划分，求平均值，由于程序运行时间存在误差，故每次划分结果得到训练集在运行相关算法的程序时，运行20次求平均值作为划分一次的数据值。AUC计算公式中的统一取10万次。

3.2 基于ADS的链路预测算法的有效性

ADS勾勒技术是对原数据的一种抽样方法，通过抽样达到降低计算复杂度的目的，但是由于它只是对数据的近似勾勒，所以用勾勒的结果进行数据的分析与挖掘，在精度上会有一定的损失，是不可避免的，但是损失一定范围内的精度，却提升了较大的计算效率。

3.2.1 两种算法执行效率

图 2～4分别给出了 USAir97、Yeast、Grid数据集基于CN、AA、RA3种相似性度量指标的两种算法的执行效率。从图中可以看出基于ADS勾勒技术的链路预测算法执行时间均低于原链路预测算法的执行时间，由于链路预测算法不涉及到值得变化，故在值变化过程中结果不改变。而基于图勾勒技术的链路预测算法随着值的变化算法执行时间有所增加，但是均低于原链路预测算法，计算效率提高了约百分之15%～25%，这是由于ADS结构是原数据集的一个抽样，每个节点的一跳邻居节点集的数目远远小于原图的一跳邻居节点集的数目，当值足够大时，抽样的结果也只能等于原图的数据。

图 2 CN、AA、RA度量指标运行时间对比(USAir97)Fig. 2 CN, AA, RA metrics comparison of run time(USAir97)

3.2.2 两种算法的预测精度

图5～7给出了3个数据集在两种算法下的预测精度，实验结果显示，基于ADS的链路预测算法的预测精度随着值的增加而逐渐接近于原链路预测算法的精度，数据线最后趋于重合。

图 3 CN、AA、RA度量指标运行时间对比(Yeast)Fig. 3 CN，AA，RA metrics comparison of run time(Yeast)

图 4 CN、AA、RA度量指标运行时间对比(Grid)Fig. 4 CN，AA，RA metrics comparison of run time(Grid)

从表1中可以看出USAir97数据集节点远小于Yeast数据集和Grid数据集，但是图中结果显示USAir97数据集较为理想的预测结果对应的值要比其余两个数据集对应的值要大，这是由于USAir97数据集要比Yeast数据集和Grid数据集稠密，在网络刻画中对精度的要求更高，所以相对而言预测结果较为理想的情况下对应的值要大。

图5和图6中精度的变化逐渐上升最后趋于稳定，但是图7中精度的变化有波动，在千分之一上下波动，存在原因可能有两个：1)计算AUC过程中抽取的次数不够所造成的误差；2)ADS节点随机值变化过程中产生的误差。

图 5 CN，AA，RA度量指标AUC对比(USAir97)Fig. 5 Comparison of the CN, AA, RA metrics AUC(USAir97)

图 6 CN、AA、RA度量指标AUC对比(Yeast)Fig. 6 Comparison of the CN，AA，RA metrics AUC(Yeast)

图 7 CN、AA、RA度量指标AUC对比(Grid)Fig. 7 comparison of the CN，AA，RA metrics AUC(Grid)

3.3 基于ADS与基于网嵌入的链路预测算法对比

DeepWalk[20]是一种基于随机游动的网络表示学习方法。通过DeepWalk可获得图中节点的向量化表示，进而可基于向量点积进行链接预测。在真实图数据上将本文方法与基于Deep-Walk的链接预测方法进行了实验对比。测试数据为蛋白质交互网络[21](protein-Protein Interactions)。该数据包括19 706 个节点、390 633条边。采用CN-ADS与DeepWalk在算法执行时间和AUC值上进行了比较。其中DeepWalk的参数设置为：向量学习模型为Skip-Gram，向量维数设为64。实验结果如图8、9所示。从图8、9结果可知，小值可保证算法执行效率，然而，AUC较DeepWalk差。提高值后，在执行时间仍小于D e e p W a l k的情况下，可显著改善AUC值。特别地，当＞32后，AUC值优于DeepWalk。对于链接预测而言，本文算法在一定条件下优于DeepWalk的结果。

图 8 PPI数据集上CN-ADS与DeepWalk的时间对比Fig. 8 Time comparison of CN-ADS and DeepWalk on PPI

图 9 PPI数据集上CN-ADS与DeepWalk的AUC对比Fig. 9 AUC comparison of CN-ADS and DeepWalk on PPI

4 结束语

本文针对大规模网络数据在链路预测中存在时间复杂度高、运算量大等问题，对现有的链路预测方法进行扩展，结合现有的图勾勒技术，提出了基于ADS技术的链路预测方法，根据勾勒的结果结合现有的预测方法，定义了基于ADS结构的链路预测方法，在算法预测精度和预测时间中取得了较好的折衷，并在真实网络数据中验证了算法的有效性。

本文是基于局部信息相似度进行链路预测的，更精确的预测方法是基于全局信息进行预测的，如何更好地在图勾勒技术的基础上基于全局信息定义预测方法，是将来展开的要点之一。此外，为验证图勾勒技术在链路预测问题上面的有效性，本文是通过实验数据进行验证分析的，缺少严谨的理论证明，后续工作将会致力于从理论方面证明图勾勒技术对链路预测的有效性。