第14卷第4期 智能系统学报 Vol.14 No.4 2019年7月 CAAI Transactions on Intelligent Systems Jul.2019 D0:10.11992/tis.201806007 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20190109.1422.004.html 基于图勾勒的图链路预测方法 尤洁'，李劲2，张赛，李婷 (1.云南大学软件学院，云南昆明650091：2.云南省软件工程重点实验室，云南昆明650091) 摘要：针对已有链路预测算法复杂度高，不适于在大规模图上进行链接预测的问题，本文基于图勾勒近似技 术对已有链路预测方法进行优化，提出了基于图勾勒的链路预测方法。该方法将链路预测算法的计算复杂度 由O(m3)降低至O(klog"n)。为进一步提高链接预测效率，给出了基于Spark的并行化链路预测实现方法。 在真实图数据集上进行测试，实验结果表明本文方法在保证链接预测精度的前提下，可有效提升算法效率。 关键词：图数据；算法复杂度；链路预测；图勾勒；节点相似性；并行计算；Apache Spark 中图分类号：TP311 文献标志码：A文章编号：1673-4785(2019)04-0761-08 中文引用格式：尤洁，李劲，张赛，等.基于图勾勒的图链路预测方法.智能系统学报，2019,14(4)：761-768. 英文引用格式：YOU Jie,LI Jin,.ZHANG Sai,.etal.Graph sketches-based link prediction over graph dataJ.CAAI transactions on intelligent systems,2019,14(4):761-768. Graph sketches-based link prediction over graph data YOU Jie',LI Jin,ZHANG Sai',LI Ting (1.School of Software,Yunnan University,Kunming 650091,China;2.Key Laboratory in Software Engineering of Yunnan Province,Kunming 650091,China) Abstract:The high computational complexity of existing link prediction algorithms makes them unsuitable for link pre- diction on large-scale graphs.To solve this problem,we propose a novel link prediction approach that involves combin- ing the existing link prediction approaches with graph sketch approximation.Our proposed approach reduces the compu- tation complexity of link prediction from O(n3)to O(n2k2log2n)Furthermore,to enhance the efficiency of our ap- proach;we also provide a parallel link prediction algorithm,which is implemented on the parallel computing frame- work Apache Spark.Finally,we conducted extensive experiments on a real network dataset to test the validation and ef- ficiency of our approach.The experimental results indicate that our methods can effectively improve the efficiency of link prediction while guaranteeing prediction accuracy as well. Keywords:graph data;algorithm complexity;link-prediction;graph sketches;nodes similarity;parallel computing; Apache Spark 图上的链路预测是指通过已有的网络拓扑结3种：1)基于极大似然估计的方法。该方法将网 构和节点属性信息等预测网络中尚未产生连边的 络链接看作是内在层次的反映，采用极大似然估 两个节点之间产生链接的可能性，或者是已经产 计进行预测。但该方法的预测准确性与样本数据 生但是并未发现的链接信息，是图数据挖掘的重 量有关，高质量的预测需要大的样本数据，导致 要方向之一，受到广泛的关注。 计算复杂度高，不适用于大规模网络：2)基于 当前，关于链路预测的研究方法主要包括 概率模型方法。通过建立可调参数模型再现网络 收稿日期：2018-06-02.网络出版日期：2019-01-10. 的结构和关系特征，将预测问题转化为预测边的 基金项目：国家自然科学基金项目(61562091)：云南省应用基 础研究计划面上项目(2016FB110,. 属性问题进行预测，此类方法具有较高预测精 通信作者：李劲.E-mail:lijin@ynu.edu.cn. 度，但预测过程中涉及到非普适性的参数和节点
DOI: 10.11992/tis.201806007 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20190109.1422.004.html 基于图勾勒的图链路预测方法 尤洁1 ，李劲1,2，张赛1 ，李婷1 （1. 云南大学 软件学院，云南 昆明 650091; 2. 云南省软件工程重点实验室，云南 昆明 650091） O ( n 3 ) O ( n 2 k 2 log2n ) 摘 要：针对已有链路预测算法复杂度高，不适于在大规模图上进行链接预测的问题，本文基于图勾勒近似技 术对已有链路预测方法进行优化，提出了基于图勾勒的链路预测方法。该方法将链路预测算法的计算复杂度 由 降低至 。为进一步提高链接预测效率，给出了基于 Spark 的并行化链路预测实现方法。 在真实图数据集上进行测试，实验结果表明本文方法在保证链接预测精度的前提下，可有效提升算法效率。 关键词：图数据；算法复杂度；链路预测；图勾勒；节点相似性；并行计算；Apache Spark 中图分类号：TP311 文献标志码：A 文章编号：1673−4785(2019)04−0761−08 中文引用格式：尤洁, 李劲, 张赛, 等. 基于图勾勒的图链路预测方法 [J]. 智能系统学报, 2019, 14(4): 761–768. 英文引用格式：YOU Jie, LI Jin, ZHANG Sai, et al. Graph sketches-based link prediction over graph data[J]. CAAI transactions on intelligent systems, 2019, 14(4): 761–768. Graph sketches-based link prediction over graph data YOU Jie1 ，LI Jin1,2 ，ZHANG Sai1 ，LI Ting1 (1. School of Software, Yunnan University, Kunming 650091, China; 2. Key Laboratory in Software Engineering of Yunnan Province, Kunming 650091, China) O ¡ n3 ¢ O ¡ n2k 2log2 n ¢ Abstract: The high computational complexity of existing link prediction algorithms makes them unsuitable for link prediction on large-scale graphs. To solve this problem, we propose a novel link prediction approach that involves combining the existing link prediction approaches with graph sketch approximation. Our proposed approach reduces the computation complexity of link prediction from to Furthermore, to enhance the efficiency of our approach; we also provide a parallel link prediction algorithm, which is implemented on the parallel computing framework Apache Spark. Finally, we conducted extensive experiments on a real network dataset to test the validation and efficiency of our approach. The experimental results indicate that our methods can effectively improve the efficiency of link prediction while guaranteeing prediction accuracy as well. Keywords: graph data; algorithm complexity; link-prediction; graph sketches; nodes similarity; parallel computing; Apache Spark 图上的链路预测是指通过已有的网络拓扑结 构和节点属性信息等预测网络中尚未产生连边的 两个节点之间产生链接的可能性，或者是已经产 生但是并未发现的链接信息，是图数据挖掘的重 要方向之一，受到广泛的关注。 当前，关于链路预测的研究方法主要包括 3 种：1) 基于极大似然估计的方法。该方法将网 络链接看作是内在层次的反映，采用极大似然估 计进行预测。但该方法的预测准确性与样本数据 量有关，高质量的预测需要大的样本数据，导致 计算复杂度高，不适用于大规模网络[1-2] ；2) 基于 概率模型方法。通过建立可调参数模型再现网络 的结构和关系特征，将预测问题转化为预测边的 属性问题进行预测，此类方法具有较高预测精 度，但预测过程中涉及到非普适性的参数和节点 收稿日期：2018−06−02. 网络出版日期：2019−01−10. 基金项目：国家自然科学基金项目 (61562091)；云南省应用基 础研究计划面上项目 (2016FB110). 通信作者：李劲. E-mail：lijin@ynu.edu.cn. 第 14 卷第 4 期 智 能 系 统 学 报 Vol.14 No.4 2019 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2019
·762· 智能系统学报 第14卷 属性信息，使得应用范围受限，计算复杂度高： Sw=r()nTy川 (1) 3)基于节点相似性预测方法。假设节点之间 式中：x、y表示节点；T(x)表示节点x的邻居节点 存在链接的可能性与节点之间的相似性紧密相 集；「Oy)表示节点y的邻居节点集；S表示x、y的 关，通过预测节点之间的相似性来进行链路预 相似度的值；厂(x)nTOy训表示节点x和节点y的 测。其中，基于节点相似性模型的预测方法由于 共同邻居节点数。 方法简单，链接预测质量较好等成为目前主流的 定义2 Adamic Adar(AA):AA在CN的基 链接预测方法。 础上，赋予邻居节点权重，它认为共同邻居节点 但是，基于节点相似性的预测方法，其计算复 的节点度对相似度也有影响，共同邻居节点度越 杂度为O(n),在大规模图数据上进行链接预测 大，它对节点相似度的贡献越小，反之，共同邻居 时，算法执行效率低。为有效处理大规模网络， 节点度越小，它对节点的相似度的贡献越大。因 文献[15]提出了基于节点局部信息的分布式并行 此在求相似度的公式中，对共同邻居节点度赋予 计算的预测方法。然而，该方法没有从降低时间 一个惩罚因子。其相似度定义为 复杂度的角度解决链路预测问题。 S4= 1 (2) 针对已有研究工作的不足，本文在保证链路 2 log(d) Er()nf(y) 预测质量的前提下，降低预测算法的计算复杂性 式中：x、y表示图节点；S表示x、y的相似度的 角度，提出基于图勾勒61的链路预测算法。首 值；「(x)表示节点x的邻居节点集；「y)表示节点 先，基于图勾勒技术对现有的链路预测方法进行 y的邻居节点集；z表示x、y的共同邻居节点；d, 扩展，定义了基于ADS(all-distances sketches)结构 表示z的节点度。 的链路预测相似性度量指标，提出了基于图勾勒 定义3 Resource Allocation(RA):RA从资 的链路预测算法，将一般链路预测算法的计算复 源分配的角度考虑节点相似性。它认为没有直接 杂度由0(m)降低至02k21og2N),其中k是 相连的两个节点，资源可以从一个节点传递到另 ADS勾勒参数，n是网络节点数。其次，基于并行 一个节点，它们的共同邻居节点是两个节点传递 图计算平台Spark,提出了ADS的并行计算方法 资源的媒介，每一个媒介都有一个单位的资源， 以及基于ADS技术的并行链路预测实现方法。 它将自己的资源平均分配给它的邻居节点，另一 从算法运算时间和预测精度两方面验证算法的有 个节点接收到的资源数就是这两个节点的相似 效性，实验结果表明：基于ADS技术的链路预测 度。其相似度定义为 算法可以保证一定预测精度，同时降低预测方法 (3) 的时间复杂度，提升运算效率。 评估指标：链路预测结果的衡量指标主要包 1背景知识 括Precision(准确率)刀和AUC(曲线下面积)1， Precision针对局部结果进行评估，AUC基于全局 1.1链路预测 进行评估，本文讨论的是整体性能，故以AUC作 给定无向图G=(WE),其中，V是顶点集，E 为预测精度的评估标准。AUC的值越高，则链路 边集。N=Ⅵ为网络节点数，M=E为边数。G 预测整体性能较好。 共有n(-1)/2个可能的节点对，所有节点对构成 定义4对于边集进行数据划分，有E= 全集U。令E表示U中不存在连边的节点对集 合，且没有连边的节点对表示为(x,y)∈E=U八E, Er UEp,ErnEp=中，假设E是属于全集U,但是不 属于边集E,从E。中取出一条边的预测值记为 其中x,y∈V。给定一种链路预测方法，Sy表示节 a,从E中选出一条边的预测值记为b,比较n次， 点对(x,y)的链路预测值，S值越高，表示(x,y)出 若a>b,m=1,若a=bn"=1,否则不计数，具体 现连边的概率越高。 如下： 下面分别给出本文中采用的3种节点间相似 度度量指标及定义： AUC=n+0.5n" (4) n 定义1 Common Neighbor(CN):如果图中 1.2图勾勒技术 两个节点拥有的共同邻居节点越多，那么这两个 ADS(all-distances sketches)是定义在图节点上 节点就越相似，则它们之间存在或者未来发生链 的数据摘要结构。通过对图中各节点的可达邻居 接的可能性就越大。相似度定义为 节点集进行抽样，抽样结果与原节点的集合构成
属性信息，使得应用范围受限，计算复杂度高[3] ； 3) 基于节点相似性预测方法[4-14]。假设节点之间 存在链接的可能性与节点之间的相似性紧密相 关，通过预测节点之间的相似性来进行链路预 测。其中，基于节点相似性模型的预测方法由于 方法简单，链接预测质量较好等成为目前主流的 链接预测方法。 O ( n 3 ) 但是，基于节点相似性的预测方法，其计算复 杂度为 ，在大规模图数据上进行链接预测 时，算法执行效率低。为有效处理大规模网络， 文献 [15] 提出了基于节点局部信息的分布式并行 计算的预测方法。然而，该方法没有从降低时间 复杂度的角度解决链路预测问题。 O ( n 3 ) O ( n 2 k 2 log2N ) k n 针对已有研究工作的不足，本文在保证链路 预测质量的前提下，降低预测算法的计算复杂性 角度，提出基于图勾勒[16] 的链路预测算法。首 先，基于图勾勒技术对现有的链路预测方法进行 扩展，定义了基于 ADS(all-distances sketches) 结构 的链路预测相似性度量指标，提出了基于图勾勒 的链路预测算法，将一般链路预测算法的计算复 杂度由 降低至 ，其中 是 ADS 勾勒参数， 是网络节点数。其次，基于并行 图计算平台 Spark，提出了 ADS 的并行计算方法 以及基于 ADS 技术的并行链路预测实现方法。 从算法运算时间和预测精度两方面验证算法的有 效性，实验结果表明：基于 ADS 技术的链路预测 算法可以保证一定预测精度，同时降低预测方法 的时间复杂度，提升运算效率。 1 背景知识 1.1 链路预测 G = (V,E) V E N = |V| M = |E| G n(n−1) /2 U E U (x, y) ∈ E = U\E x, y ∈ V S xy (x, y) S (x, y) 给定无向图 ，其中， 是顶点集， 边集。 为网络节点数， 为边数。 共有 个可能的节点对，所有节点对构成 全集 。令 表示 中不存在连边的节点对集 合，且没有连边的节点对表示为 ， 其中 。给定一种链路预测方法， 表示节 点对 的链路预测值， 值越高，表示 出 现连边的概率越高。 下面分别给出本文中采用的 3 种节点间相似 度度量指标及定义： 定义 1 Common Neighbor(CN)[5] ：如果图中 两个节点拥有的共同邻居节点越多，那么这两个 节点就越相似，则它们之间存在或者未来发生链 接的可能性就越大。相似度定义为 S CN xy = |Γ(x)∩Γ(y)| (1) x y Γ(x) x Γ(y) y x y |Γ(x)∩Γ(y)| x y 式中： 、 表示节点； 表示节点 的邻居节点 集； 表示节点 的邻居节点集；S 表示 、 的 相似度的值； 表示节点 和节点 的 共同邻居节点数。 定义 2 Adamic Adar(AA)[6] ：AA 在 CN 的基 础上，赋予邻居节点权重，它认为共同邻居节点 的节点度对相似度也有影响，共同邻居节点度越 大，它对节点相似度的贡献越小，反之，共同邻居 节点度越小，它对节点的相似度的贡献越大。因 此在求相似度的公式中，对共同邻居节点度赋予 一个惩罚因子。其相似度定义为 S AA xy = ∑ z∈Γ(x)∩Γ(y) 1 log(dz) (2) x y x y Γ(x) x Γ(y) y z x y dz z 式中： 、 表示图节点；S 表示 、 的相似度的 值； 表示节点 的邻居节点集； 表示节点 的邻居节点集； 表示 、 的共同邻居节点； 表示 的节点度。 定义 3 Resource Allocation(RA)[7] ：RA 从资 源分配的角度考虑节点相似性。它认为没有直接 相连的两个节点，资源可以从一个节点传递到另 一个节点，它们的共同邻居节点是两个节点传递 资源的媒介，每一个媒介都有一个单位的资源， 它将自己的资源平均分配给它的邻居节点，另一 个节点接收到的资源数就是这两个节点的相似 度。其相似度定义为 S RA xy = ∑ z∈Γ(x)∩Γ(y) 1 dz (3) 评估指标：链路预测结果的衡量指标主要包 括 Precision(准确率) [17] 和 AUC(曲线下面积) [18] ， Precision 针对局部结果进行评估，AUC 基于全局 进行评估，本文讨论的是整体性能，故以 AUC 作 为预测精度的评估标准。AUC 的值越高，则链路 预测整体性能较好。 ET ∪ Ep,ET ∩ Ep = ϕ E¯ U E Ep a E¯ b n a > b,n ′ = 1 a = b,n ′′ = 1 定 义 4 对于边集进行数据划分， 有 E = ，假设 是属于全集 ，但是不 属于边集 ，从 中取出一条边的预测值记为 ，从 中选出一条边的预测值记为 ，比较 次， 若 ，若 ，否则不计数，具体 如下： AUC = n ′ +0.5n ′′ n (4) 1.2 图勾勒技术 ADS(all-distances sketches) 是定义在图节点上 的数据摘要结构。通过对图中各节点的可达邻居 节点集进行抽样，抽样结果与原节点的集合构成 ·762· 智 能 系 统 学 报 第 14 卷
第4期 尤洁，等：基于图勾勒的图链路预测方法 ·763· 了该节点的Sketch结构。在大图上，基于ADS可 CN、AA、RA3种算法的默认情况是基于1跳邻 有效进行节点相似关系，中心度等度量计算。 居进行计算的，故为了排除多跳邻居对相似度的 定义5节点v的All-Distances Sketches 影响，基于节点的ADS结构的链路预测算法中也 (ADS)的定义如下Ia: 只考虑一跳邻居节点。基于1跳邻居的ADS的 ADS(v)=((u,d(v,u))Ir(u)X时，K()=1,K值 心度的运算量。 是平衡sketch规模大小和勾勒精度的参数。 对图勾勒后，得到的ADS结构不再是单一的 例1图的ADS结构如图1所示，该图为有 节点集、边集所构成的图数据，而是由节点及其 向图带权图。节点上的数值为勾勒ADS结构所 部分邻居节点构成的集合，这部邻居节点包括了 对应生成的0~1的随机数。 一跳至多跳另据节点，还带有相应的可达距离， 0.2 故ADS需要根据自身结构定义合适的相似性指 标，具体定义如下： 10 0.1 定义6基于ADS的CN度量指标(ADS-CN) 0.7 定义如下： 10 100.6 SADS-CN =ADS()nADS(y) (6) 0 03 式中：x、y表示待求相似度的节点；S表示x、y的 6 10 相似度的值；ADS(x),表示节点x的ADS概要结 0.9 9 构并且可达节点集的距离x≤1；ADSy),表示节 10 点y的ADS概要节点且可达节点距离y≤I; 0.8 ADS(x1nADS)表示节点x和节点y基于ADS 图1图的ADS示例 的概要结构的一跳共同邻居数。 Fig.1 An illustration of ADS in a graph 定义7基于ADS的AA度量指标(ADS-AA) 图中每个节点的ADS结构是一个集合。以 如下： 节点1为例，ADS(1)(K=2)={(1,0),(2,8),(3,9), SADS-MA 1 log(d.) (7) (4,18),(6,18)}表示在图中随机值取值情况下， EADS()OADS() ADS勾勒参数为2时节点1的ADS结构，集合中 式中：d,表示节点z在图中的节点度，其余符号定 元素(4,18)表示节点1到节点4的最短距离是 义同定义6。 18。例如： 定义8基于ADS技术扩展的RA度量指标 ADS(1)={1.0),(2,8),(3,9),(4,18),(6,18)} (ADS-RA)定义如下： ADS(2)={(2,0),(5,8),(4,10),(6,10),(3,10)} ∑ 1 (8) ADS(5)={(5,0).(8,10).(7,19).(6,28).(1,29),(3,38).(4,47) S 从给出的ADS(1)(K=2)可以看出，每个节点 A)D)d 公式中符号含义同定义6。 与其ADS集合里面对应的节点是可达关系，但是 2.1基于ADS勾勒技术的链路预测算法 每个节点的ADS集合里面并没有包含所有的可 首先简要介绍链路预测算法的基本思想，链 达节点，只包含了部分可达节点，在ADS中包含 路预测算法首先将待预测数据集E划分为训练 多少可达节点与勾勒参数K取值的大小相关，K 集E,和测试集E。找出训练集中不存在连边的 取值越大，勾勒的精度越高，ADS的尺寸越大。 节点对，得到E中不存在连边的数据集E和E。, 2链路预测方法 并计算节点对的相似度值，随机从E和E,中各 选出一条边，比较它们的相似度的值，重复多次， ADS是对节点的全局邻居节点进行抽样，而 根据AUC公式定义，得到预测精度。基于ADS
了该节点的 Sketch 结构。在大图上，基于 ADS 可 有效进行节点相似关系，中心度等度量计算[16]。 定义 5 节点 v 的 All-Distances Sketches (ADS) 的定义如下[16] ： ADS(v) = {(u,d (v,u))|r(u) |X| K th r (X) = 1,K 式中： 是 任意顶点； 表示节点 的 随 机 ran k 值，即函数 (对任意顶点 )； 表示从节点 到节点 的距离； 表示比节点 更接近节点 的节 点的集合 (即 )； 集合 中所有元素按照 rank 值从小到大排序，第 个元素的 rank 值，当 时， 值 是平衡 sketch 规模大小和勾勒精度的参数。 例 1 图的 ADS 结构如图 1 所示，该图为有 向图带权图。节点上的数值为勾勒 ADS 结构所 对应生成的 0 ~ 1 的随机数。 0.2 8 7 7 0.6 10 0.3 10 10 10 11 8 0.7 10 2 8 0.5 1 10 0.8 7 9 0.4 12 9 3 6 9 0.9 8 7 9 0.1 5 4 图 1 图的 ADS 示例 Fig. 1 An illustration of ADS in a graph K = 2 图中每个节点的 ADS 结构是一个集合。以 节点 1 为例，ADS(1)( )={(1，0)，(2，8)，(3，9)， (4，18)，(6，18)}表示在图中随机值取值情况下， ADS 勾勒参数为 2 时节点 1 的 ADS 结构，集合中 元素 (4，18) 表示节点 1 到节点 4 的最短距离是 18。例如： ADS(1) = {(1,0),(2,8),(3,9),(4,18),(6,18)} ADS(2) = { (2, 0), (5, 8), (4, 10), (6, 10), (3, 10)} ADS(5)={(5,0),(8,10),(7,19),(6,28),(1,29),(3,38),(4,47)} ADS(1) (K = 2) K K 从给出的 可以看出，每个节点 与其 ADS 集合里面对应的节点是可达关系，但是 每个节点的 ADS 集合里面并没有包含所有的可 达节点，只包含了部分可达节点，在 ADS 中包含 多少可达节点与勾勒参数 取值的大小相关， 取值越大，勾勒的精度越高，ADS 的尺寸越大。 2 链路预测方法 ADS 是对节点的全局邻居节点进行抽样，而 CN、AA、RA 3 种算法的默认情况是基于 1 跳邻 居进行计算的，故为了排除多跳邻居对相似度的 影响，基于节点的 ADS 结构的链路预测算法中也 只考虑一跳邻居节点。基于 1 跳邻居的 ADS 的 大小永远不大于节点的 1 跳邻居数，所以在求两 个集合的相似度时，运算量也相应减少。 在 AA 算法和 RA 算法中还涉及到求共同邻居节点 的度，其他相似性度量指标也涉及到节点中心度 的计算等，这个过程中需要耗费大量的计算时 间，而 ADS 抽样的过程中会过滤掉一部分的邻居 节点，故在一定程度上减少了部分求节点度、中 心度的运算量。 对图勾勒后，得到的 ADS 结构不再是单一的 节点集、边集所构成的图数据，而是由节点及其 部分邻居节点构成的集合，这部邻居节点包括了 一跳至多跳另据节点，还带有相应的可达距离， 故 ADS 需要根据自身结构定义合适的相似性指 标，具体定义如下： 定义 6 基于 ADS 的 CN 度量指标 (ADS-CN) 定义如下： S ADS−CN xy = ADS(x)1 ∩ADS(y)1 (6) x y x y ADS(x)1 x x ADS(y)1 y y ADS(x)1 ∩ADS(y)1 y 式中： 、 表示待求相似度的节点；S 表示 、 的 相似度的值； 表示节点 的 ADS 概要结 构并且可达节点集的距离 ≤1； 表示节 点 的 ADS 概要节点且可达节点距离 ≤1； 表示节点 x 和节点 基于 ADS 的概要结构的一跳共同邻居数。 定义 7 基于 ADS 的 AA 度量指标 (ADS-AA) 如下： S ADS−AA xy = ∑ z∈ADS(x)1∩ADS(y) 1 1 log(dz) (7) 式中： dz 表示节点 z 在图中的节点度，其余符号定 义同定义 6。 定义 8 基于 ADS 技术扩展的 RA 度量指标 (ADS-RA) 定义如下： S RA xy = ∑ z∈ADS(x)1∩ADS(y) 1 1 dz (8) 公式中符号含义同定义 6。 2.1 基于 ADS 勾勒技术的链路预测算法 E ET Ep E E¯ Ep E¯ Ep 首先简要介绍链路预测算法的基本思想，链 路预测算法首先将待预测数据集 划分为训练 集 和测试集 。找出训练集中不存在连边的 节点对，得到 中不存在连边的数据集 和 ， 并计算节点对的相似度值，随机从 和 中各 选出一条边，比较它们的相似度的值，重复多次， 根据 AUC 公式定义，得到预测精度。基于 ADS 第 4 期 尤洁，等：基于图勾勒的图链路预测方法 ·763·
·764· 智能系统学报 第14卷 勾勒技术的链路预测算法的基本思想：在计算节 13)if a>b do 点对相似度之前，构造出边集E的图结构，对图 14)m=+1 进行ADS勾勒处理，得到E,中每个节点的ADS 2.2基于ADS勾勒技术的并行化链路预测算法 结构，根据基于ADS结构定义的相似性度量指标 为提高链路预测算法的执行效率，在算法1 进行链路预测。由于节点的ADS是独立于图的， 基础上，进一步提出了基于Spark的并行化的链 这样带来的优势是原图有些节点发生变化以后，路预测算法。该算法具体描述如算法2。算法2 只需要更新变化节点的ADS,带来的好处是可以 的执行过程与算法1一致，但算法2将算法1中 独立动态更新节点的ADS结构，更新代价小；处 的每一步骤采用弹性分布式数据集(RDD)进行 理后的数据另一个优点是利于并行化处理，每个 了实现。基于RDD表示，采用对RDD的Map-re 节点及其ADS结构与其他节点时独立的，在其他 duce并行化操作有效提升链接预测算法的执行 并行框架下，每个节点ADS互不干扰，利于并行。 效率。RDD转换和操作细节详见算法2中的 基于ADS勾勒技术的链路预测算法的具体 描述。 描述如算法1。 算法2基于Spark的并行化链路预测算法 分析算法1的时间复杂度。首先，由文 输入G(VE),预测值比较次数n 献[16]可知，对于图中的一个节点v,ADS(w的期 输出AUC值。 望大小为K+K(H(n)-H(K)≈K(1+logn,-logK) I∥创建边集E的RDD 其中n,是从节点v出发的可达邻居节点数，H①= 是第1个调和级数，由于46：（州-n)且 1)dataRDD sc.textFile(edgesPath); I∥创建训练集E,的RDD H)=O(KIog),所以ADS(w)的期望大小为 2)edgestRDD-dataRDD.takeSample (0.9 O(K1ogm)。于是，基于ADS技术求图中节点相似 (dataRDD.count)); 度的时间复杂度为O(m2Klog2n)。 II创建测试集E,的RDD 算法1基于ADS勾勒技术的链路预测算法 3)edgespRDD+-dataRDD.subtract(edgestRDD); 输入G(WE),预测值比较次数n,勾勒参数K 找出训练集中不存在连边的结点对集合 输出AUC值。 4)pairRDD +edgestRDD.cartesian(edgestRDD) I)切割边集E为训练集E,和测试集Ep, subtract(edgestRDD); E=E,UEp,E,nEp=0; 求出各顶点的邻居节点 2)degree(w)←求出E,中所有结点的结点度； 5)verticesRDD -edgestRDD.groupByKey(.map (G'=(V,E,),v∈ (vertices.nbrs); 3)ADS(w)←根据式(3)构造图G中个结 6)g←Graph(verticesRDD,pairRDD);/构造图g 点的： 求出各结点的节点度 ADS(G'=(V,E),v∈ (7)degreeRDDverticesRDD.map(nbrs.size); 找出训练集中不存在连边的结点对集合 求结点x,y的相似度 4)A←-{w,w),w∈V且(w,w)∈E: 8)simRDD-g.triplets.map(sim(x,y.persist()); S)S←求出A中所有节点对的预测值： 9)simepRDD←-从simRDD筛选E,连边的预 得到E中所有连边结点对的预测值： 测值； IO)simeNotRDD←从simRDD筛选Ep连边预 6)Sw←{S(x,ylx,yeV且(x,y)eE: 得到E。中所有连边结点对的预测值： 测值； 7)Sm←{S(u,v)lu,veV且(u,v)eEp 11)a-simepRDD.takeSample(true,n); 8)fori←-1 to n do 3实验结果 9)a:从Sm中选出一条边的预测值： 10)b:Sy中选出一条边的预测值； 3.1实验环境设置 11)m:表示E。中的预测值大于E中预测值 表1给出了本文实验数据集统计信息。其 的次数； 中，N表示网络中节点的总数，E表示网络中边的 12)n":表示E。中的预测值等于E中预测值 总数，(ad表示网络节点的平均度，(d表示网络 的次数； 的平均最短距离，C表示网络的集聚系数
ET ET 勾勒技术的链路预测算法的基本思想：在计算节 点对相似度之前，构造出边集 的图结构，对图 进行 ADS 勾勒处理，得到 中每个节点的 ADS 结构，根据基于 ADS 结构定义的相似性度量指标 进行链路预测。由于节点的 ADS 是独立于图的， 这样带来的优势是原图有些节点发生变化以后， 只需要更新变化节点的 ADS，带来的好处是可以 独立动态更新节点的 ADS 结构，更新代价小；处 理后的数据另一个优点是利于并行化处理，每个 节点及其 ADS 结构与其他节点时独立的，在其他 并行框架下，每个节点 ADS 互不干扰，利于并行。 基于 ADS 勾勒技术的链路预测算法的具体 描述如算法 1。 v ADS(v) K +K(H (nv)− H (K)) ≈ K ( 1+lognv −logK ) nv v H(i) = ∑i j=1 1 j nv ⩽ n |V| = n H (n) = O ( Klogn ) ADS(v) O ( Klogn ) O ( n 2K 2 log2n ) 分析算 法 1 的时间复杂度。首先，由文 献 [16] 可知，对于图中的一个节点 ， 的期 望大小为 其中 是从节点 出发的可达邻居节点数， 是第 i 个调和级数，由于 ( ) 且 ，所以 的期望大小为 。于是，基于 ADS 技术求图中节点相似 度的时间复杂度为 。 算法 1 基于 ADS 勾勒技术的链路预测算法 输入 G(V,E) ，预测值比较次数 n，勾勒参数 K； 输出 AUC 值。 E = Er ∪ Ep,Er ∩ Ep = Ø 1) 切割边 集 E 为训练 集 Er 和测试 集 Ep， ； 2) degree(v) ← 求出 Er 中所有结点的结点度； (G ′ = (V,Er), v ∈ V) ADS(v) ← G ′ 3) 根 据式 (3) 构造图 中个结 点的； ADS(G ′ = (V,Er), v ∈ V) //找出训练集中不存在连边的结点对集合 A ← { (v,w)|v,w ∈ V且(v,w) ∈ Er } 4) ； 5) S vw ← 求出 A 中所有节点对的预测值； //得到 E 中所有连边结点对的预测值； S xy ← { S (x, y)|x, y ∈ V且(x, y) ∈ E } 6) ； Ep //得到 中所有连边结点对的预测值； S uv ← { S (u, v)|u, v ∈ V且(u, v) ∈ Ep } 7) ； 8) for i ← 1 to n do 9) a：从 S uv 中选出一条边的预测值； 10) b : S xy 中选出一条边的预测值； n ′ 11) ：表示 Ep 中的预测值大于 E 中预测值 的次数； n ′′ 12) ：表示 Ep 中的预测值等于 E 中预测值 的次数； 13) if a > b do n ′ = n ′ 14) +1 ； 2.2 基于 ADS 勾勒技术的并行化链路预测算法 为提高链路预测算法的执行效率，在算法 1 基础上，进一步提出了基于 Spark 的并行化的链 路预测算法。该算法具体描述如算法 2。算法 2 的执行过程与算法 1 一致，但算法 2 将算法 1 中 的每一步骤采用弹性分布式数据集 (RDD) 进行 了实现。基于 RDD 表示，采用对 RDD 的 Map-reduce 并行化操作有效提升链接预测算法的执行 效率。RDD 转换和操作细节详见算法 2 中的 描述。 算法 2 基于 Spark 的并行化链路预测算法 输入 G(V,E) ，预测值比较次数 n； 输出 AUC 值。 //创建边集 E 的 RDD 1) dataRDD ← sc.textFile(edgesPath) ； //创建训练集 Er 的 RDD edgestRDD ← dataRDD (dataRDD.count)) 2) .takeSample (0.9 * ； //创建测试集 Ep 的 RDD edgespRDD ← dataRDD.subtract( edgestRDD) 3 ) ； //找出训练集中不存在连边的结点对集合 pairRDD ← edgestRDD.cartesian( edgestRDD) subtract( edgestRDD) 4 ) . ； //求出各顶点的邻居节点 verticesRDD ← edgestRDD.groupByKey() (vertices.nbrs) 5) .map ； g ← Graph( verticesRDD, pairRDD) 6) ；//构造图 g //求出各结点的节点度 (7) degreeRDD ← verticesRDD.map(nbrs.size) ； //求结点 x, y 的相似度 simRDD ← g.triplets.map( sim( x, y.persist())) 8 ) ； 9) simepRDD ← 从 simRDD 筛选 Ep 连边的预 测值； 10) simeNotRDD ← 从 simRDD 筛选 EP 连边预 测值； 11) a ← simepRDD.takeSample (true, n) ； 3 实验结果 3.1 实验环境设置 N E ⟨ad⟩ ⟨d⟩ C 表 1 给出了本文实验数据集统计信息。其 中， 表示网络中节点的总数， 表示网络中边的 总数， 表示网络节点的平均度， 表示网络 的平均最短距离， 表示网络的集聚系数。 ·764· 智 能 系 统 学 报 第 14 卷
第4期 尤洁，等：基于图勾勒的图链路预测方法 ·765· 表1实验数据集拓扑结构信息 80r ■-CN-ADS Table 1 Experimental dataset topology information -●-CN 数据集 E < ●◆●● C USAir97 332 2126 12.8072.460.749 65 Yeast 2361 6646 5.63 4.380.388 60h PB 122419090 27.362.510.361 2 46 8101214161820 本文实验在USAir97(美国航空网络数据、 (a)基于CN的相似性度量指标 180r Yeasto(酵母菌蛋白质相互作用网络数据18)、 ■-AA-ADS 170 ●AA Grid(美国电力网络数据3个数据集上进行测 160p 试，实验结果主要对链路预测算法和基于ADS勾 5150 勒技术的链路预测算法两种算法的运行时间和预 140 测精度进行对比分析。实验环境包括内存：64GB; 130 处理器：inter(R)Xeon(R)CPUE5-2620v3@2.40GHz 24 68101214161820 2.40GHz;开发平台：Intellij IDEA2016.2.5+ (b)基于AA的相似性度量指标 Spark GraphX;开发语言：Scalao 150r -RA-ADS 本次所有实验结果均是对数据集进行10次 140 --RA 划分，求平均值，由于程序运行时间存在误差，故 130 ●●●●●0 每次划分结果得到训练集在运行相关算法的程序 时，运行20次求平均值作为划分一次的数据值。 110上 AUC计算公式中的n统一取10万次。 100 3.2基于ADS的链路预测算法的有效性 4 68101214161820 ADS勾勒技术是对原数据的一种抽样方法， (c)基于RA的相似性度量指标 通过抽样达到降低计算复杂度的目的，但是由于 图2CN、AA、RA度量指标运行时间对比(USAi97 它只是对数据的近似勾勒，所以用勾勒的结果进 Fig.2 CN,AA,RA metrics comparison of run time 行数据的分析与挖掘，在精度上会有一定的损 (USAir97) 失，是不可避免的，但是损失一定范围内的精度， 3.2.2两种算法的预测精度 却提升了较大的计算效率。 图5~7给出了3个数据集在两种算法下的预 实验结果已经表明，基于ADS的链路预测方 测精度，实验结果显示，基于ADS的链路预测算 法在K取较优值时，精度损失的范围远远小于计 法的预测精度随着K值的增加而逐渐接近于原 算效率提升的范围，所以得出ADS技术在链路预 链路预测算法的精度，数据线最后趋于重合。 测算法中对降低算法时间复杂度，提升计算效率 100 -CN-ADS 是有效的。 95 ●-CN 904 3.2.1两种算法执行效率 图2~4分别给出了USAir97、Yeast、Grid数据 集基于CN、AA、RA3种相似性度量指标的两种 75 算法的执行效率。从图中可以看出基于ADS 70 量■■ 勾勒技术的链路预测算法执行时间均低于原链路 4 81216202428323640 预测算法的执行时间，由于链路预测算法不涉及 (a)基于CN的相似性度量指标 到K值得变化，故在K值变化过程中结果不改 200 ■-AA-ADS 变。而基于图勾勒技术的链路预测算法随着K 190 -AA 180 ●●◆自 值的变化算法执行时间有所增加，但是均低于原 链路预测算法，计算效率提高了约百分之15%~ 美170 160 25%,这是由于ADS结构是原数据集的一个抽 150 样，每个节点的一跳邻居节点集的数目远远小于 140 令量里是服■ 原图的一跳邻居节点集的数目，当K值足够大 81216202428323640 时，抽样的结果也只能等于原图的数据。 (b)基于AA的相似性度量指标
表 1 实验数据集拓扑结构信息 Table 1 Experimental dataset topology information 数据集 N E C USAir97 332 2 126 12.807 2.46 0.749 Yeast 2 361 6 646 5.63 4.38 0.388 PB 1 224 19 090 27.36 2.51 0.361 本文实验在 USAir97(美国航空网络数据[17] )、 Yeast(酵母菌蛋白质相互作用网络数据 [ 1 8 ] )、 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。 n 本次所有实验结果均是对数据集进行 10 次 划分，求平均值，由于程序运行时间存在误差，故 每次划分结果得到训练集在运行相关算法的程序 时，运行 20 次求平均值作为划分一次的数据值。 AUC 计算公式中的 统一取 10 万次。 3.2 基于 ADS 的链路预测算法的有效性 ADS 勾勒技术是对原数据的一种抽样方法， 通过抽样达到降低计算复杂度的目的，但是由于 它只是对数据的近似勾勒，所以用勾勒的结果进 行数据的分析与挖掘，在精度上会有一定的损 失，是不可避免的，但是损失一定范围内的精度， 却提升了较大的计算效率。 K 实验结果已经表明，基于 ADS 的链路预测方 法在 取较优值时，精度损失的范围远远小于计 算效率提升的范围，所以得出 ADS 技术在链路预 测算法中对降低算法时间复杂度，提升计算效率 是有效的。 3.2.1 两种算法执行效率 K K K K 图 2~4 分别给出了 USAir97、Yeast、Grid 数据 集基于 CN、AA、RA3 种相似性度量指标的两种 算法的执行效率。从图中可以看出基于 ADS 勾勒技术的链路预测算法执行时间均低于原链路 预测算法的执行时间，由于链路预测算法不涉及 到 值得变化，故在 值变化过程中结果不改 变。而基于图勾勒技术的链路预测算法随着 值的变化算法执行时间有所增加，但是均低于原 链路预测算法，计算效率提高了约百分之 15%~ 25%，这是由于 ADS 结构是原数据集的一个抽 样，每个节点的一跳邻居节点集的数目远远小于 原图的一跳邻居节点集的数目，当 值足够大 时，抽样的结果也只能等于原图的数据。 80 75 70 65 60 2 4 6 8 10 K (a) 基于 CN 的相似性度量指标 t/ms CN-ADS CN 12 14 16 18 20 180 160 170 150 140 130 2 4 6 8 10 K (b) 基于 AA 的相似性度量指标 t/ms AA-ADS AA 12 14 16 18 20 150 140 130 120 110 100 2 4 6 8 10 K (c) 基于 RA 的相似性度量指标 t/ms RA-ADS RA 12 14 16 18 20 图 2 CN、AA、RA 度量指标运行时间对比 (USAir97) Fig. 2 CN, AA, RA metrics comparison of run time (USAir97) 3.2.2 两种算法的预测精度 K 图 5~7 给出了 3 个数据集在两种算法下的预 测精度，实验结果显示，基于 ADS 的链路预测算 法的预测精度随着 值的增加而逐渐接近于原 链路预测算法的精度，数据线最后趋于重合。 100 95 90 85 80 75 70 4 8 12 16 20 K (a) 基于 CN 的相似性度量指标 t/ms CN-ADS CN 24 28 32 36 40 200 180 190 170 160 150 140 4 8 12 16 20 K (b) 基于 AA 的相似性度量指标 t/ms AA-ADS AA 24 28 32 36 40 第 4 期 尤洁，等：基于图勾勒的图链路预测方法 ·765·
·766· 智能系统学报 第14卷 190 185 ■-RA-ADS 图5和图6中精度的变化逐渐上升最后趋于 180 -RA 稳定，但是图7中精度的变化有波动，在千分之一 175 170 ●—●—● 上下波动，存在原因可能有两个：1)计算AUC过 号165 160 程中抽取的次数不够所造成的误差；2)ADS节点 155 随机值变化过程中产生的误差。 150 145 481216202428323640 1.00r CN-ADS 0.95 CN (C)基于RA的相似性度量指标 0.90 图3CN、AA、RA度量指标运行时间对比(Yeast) 令0 0.80 Fig.3 CN,AA,RA metrics comparison of run time 0.75 (Yeast) 0.7 2468101214161820 90r ■-CN-ADS (a)CN与CN-ADS的AUC值对比 85 -0-CN 1.00 ●● 一●●●● ■-AA-ADS 0.95 ●=AA 75 0.90建 ●● 70 0.80 61 81216202428323640 0.75 0.7 (a)基于CN的相似性度量指标 246810,1214161820 230 ■-AA-ADS (b)AA与AA-ADS的AUC值对比 220 ●-AA 1.00 210◆ ●●● ■-RA-ADS 0.95 RA 0.90 180 0的 170 0.80 160 是量量是 0.75 1216202428323640 0.70 2 (b)基于AA的相似性度量指标 468101214161820 180 -RA-ADS (C)RA与RA-ADS的AUC值对比 175 ●-RA 图5CN,AA,RA度量指标AUC对比(USAir97) ●●●●● Fig.5 Comparison of the CN,AA,RA metrics AUC 美170 (USAir97) 0.70c 160量鲁 165 ■-CN-ADS 0.68 -CN 4 81216202428323640 0.66 (c)基于RA的相似性度量指标 0.64 0.62 图4CN、AA、RA度量指标运行时间对比(Gid) 0.60 Fig.4 CN,AA,RA metrics comparison of run time 81216202428323640 (Grid) (a)CN与CN-ADS的AUC值对比 从表1中可以看出USAi97数据集节点远小 0.70 于Yeast数据集和Grid数据集，但是图中结果显 ■-AA-ADS 0.68 ●-AA 示USAi97数据集较为理想的预测结果对应的K 0.66 值要比其余两个数据集对应的K值要大，这是由 0.64 于USAir97数据集要比Yeast数据集和Grid数据 0.62 集稠密，在网络刻画中对精度的要求更高，所以 0.60 相对而言预测结果较为理想的情况下对应的K 4 81216202428323640 值要大。 (b)AA与AA-ADS的AUC值对比
K K K 从表 1 中可以看出 USAir97 数据集节点远小 于 Yeast 数据集和 Grid 数据集，但是图中结果显 示 USAir97 数据集较为理想的预测结果对应的 值要比其余两个数据集对应的 值要大，这是由 于 USAir97 数据集要比 Yeast 数据集和 Grid 数据 集稠密，在网络刻画中对精度的要求更高，所以 相对而言预测结果较为理想的情况下对应的 值要大。 图 5 和图 6 中精度的变化逐渐上升最后趋于 稳定，但是图 7 中精度的变化有波动，在千分之一 上下波动，存在原因可能有两个：1) 计算 AUC 过 程中抽取的次数不够所造成的误差；2)ADS 节点 随机值变化过程中产生的误差。 1.00 0.95 0.90 0.85 0.80 0.75 0.70 2 4 6 8 10 K (a) CN 与 CN-ADS 的 AUC 值对比 AUC CN-ADS CN 12 14 16 18 20 1.00 0.90 0.95 0.85 0.80 0.75 0.70 2 4 6 8 10 K (b) AA 与 AA-ADS 的 AUC 值对比 AUC AA-ADS AA 12 14 16 18 20 1.00 0.95 0.90 0.85 0.80 0.75 0.70 2 4 6 8 10 K (c) RA 与 RA-ADS 的 AUC 值对比 AUC RA-ADS RA 12 14 16 18 20 图 5 CN，AA，RA 度量指标 AUC 对比 (USAir97) Fig. 5 Comparison of the CN, AA, RA metrics AUC (USAir97) 190 185 180 175 170 165 160 155 150 145 4 8 12 16 20 K (c) 基于 RA 的相似性度量指标 t/ms RA-ADS RA 24 28 32 36 40 图 3 CN、AA、RA 度量指标运行时间对比 (Yeast) Fig. 3 CN，AA，RA metrics comparison of run time (Yeast) 90 85 80 75 70 65 4 8 12 16 20 K (a) 基于 CN 的相似性度量指标 t/ms CN-ADS CN 24 28 32 36 40 230 200 210 220 190 180 170 160 4 8 12 16 20 K (b) 基于 AA 的相似性度量指标 t/ms AA-ADS AA 24 28 32 36 40 180 175 170 165 160 4 8 12 16 20 K (c) 基于 RA 的相似性度量指标 t/ms RA-ADS RA 24 28 32 36 40 图 4 CN、AA、RA 度量指标运行时间对比 (Grid) Fig. 4 CN，AA，RA metrics comparison of run time (Grid) 0.70 0.68 0.66 0.64 0.62 0.60 4 8 12 16 20 K (a) CN 与 CN-ADS 的 AUC 值对比 AUC CN-ADS CN 24 28 32 36 40 0.70 0.66 0.68 0.64 0.62 0.60 4 8 12 16 20 K (b) AA 与 AA-ADS 的 AUC 值对比 AUC AA-ADS AA 24 28 32 36 40 ·766· 智 能 系 统 学 报 第 14 卷
第4期 尤洁，等：基于图勾勒的图链路预测方法 ·767· 0.70 ■-RA-ADS 数设置为：向量学习模型为Skip-Gram,向量维数 0.68 -RA 设为64。实验结果如图8、9所示。从图8、9结 0.66 果可知，小K值可保证算法执行效率，然而， 20.64◆ AUC较DeepWalk差。提高K值后，在执行时间 0.62 仍小于DeepWalk的情况下，可显著改善 0.60 481216202428323640 AUC值。特别地，当K>32后，AUC值优于 DeepWalk。对于链接预测而言，本文算法在一定 (C)RA与RA-ADS的AUC值对比 条件下优于DeepWalk的结果。 图6CN、AA、RA度量指标AUC对比(Yeast) 220 Fig.6 Comparison of the CN,AA,RA metrics AUC 200 (Yeast) 180 一DeepWalk 160 -CN-ADS 0.472 140 CN-ADS 0.470 120 -CN 0.468 100 80更 30.466 481216202428323640 0.464 0.462 图8PPI数据集上CN-ADS与DeepWalk的时间对比 0.460 4 81216202428323640 Fig.8 Time comparison of CN-ADS and DeepWalk on PPI (a)CN与CN-ADS的AUC值对比 0.74 0.472 ■-AA-ADS 0.72 号一AA 0.70 0.470 0.68 0.468= 0.66 0.466 0.64 DeepWalk 062 0.464 ●-CN-ADS 0.60 0.462 0.58 0.460 0.56 481216202428323640 4 8 1216202428323640 (b)AA与AA-ADS的AUC值对比 0.472c 图9PPI数据集上CN-ADS与DeepWalk的AUC对比 ■-RA-ADS 0.470 ●RA Fig.9 AUC comparison of CN-ADS and DeepWalk on PPI 0.468 0.466 4结束语 0.464 本文针对大规模网络数据在链路预测中存在 0.462 481216202428323640 时间复杂度高、运算量大等问题，对现有的链路 (c)RA与RA-ADS的AUC值对比 预测方法进行扩展，结合现有的图勾勒技术，提 出了基于ADS技术的链路预测方法，根据勾勒的 图7CN、AA、RA度量指标AUC对比(Grid Fig.7 comparison of the CN,AA,RA metrics AUC 结果结合现有的预测方法，定义了基于ADS结构 (Grid) 的链路预测方法，在算法预测精度和预测时间中 3.3基于ADS与基于网嵌入的链路预测算法对比 取得了较好的折衷，并在真实网络数据中验证了 DeepWalk2o)是一种基于随机游动的网络表 算法的有效性。 示学习方法。通过DeepWalk可获得图中节点的 本文是基于局部信息相似度进行链路预测 向量化表示，进而可基于向量点积进行链接预 的，更精确的预测方法是基于全局信息进行预测 测。在真实图数据上将本文方法与基于Deep- 的，如何更好地在图勾勒技术的基础上基于全局 Walk的链接预测方法进行了实验对比。测试数 信息定义预测方法，是将来展开的要点之一。此 据为蛋白质交互网络2(protein-Protein 外，为验证图勾勒技术在链路预测问题上面的有 Interactions)。该数据包括19706个节点、390633 效性，本文是通过实验数据进行验证分析的，缺 条边。采用CN-ADS与DeepWalk在算法执行时 少严谨的理论证明，后续工作将会致力于从理论 间和AUC值上进行了比较。其中DeepWalk的参 方面证明图勾勒技术对链路预测的有效性
0.472 0.470 0.468 0.466 0.464 0.462 0.460 4 8 12 16 20 K (a) CN 与 CN-ADS 的 AUC 值对比 AUC CN-ADS CN 24 28 32 36 40 0.472 0.468 0.470 0.466 0.464 0.462 0.460 4 8 12 16 20 K (b) AA 与 AA-ADS 的 AUC 值对比 AUC AA-ADS AA 24 28 32 36 40 0.472 0.470 0.468 0.466 0.464 0.462 4 8 12 16 20 K (c) RA 与 RA-ADS 的 AUC 值对比 AUC RA-ADS RA 24 28 32 36 40 图 7 CN、AA、RA 度量指标 AUC 对比 (Grid) Fig. 7 comparison of the CN，AA，RA metrics AUC (Grid) 3.3 基于 ADS 与基于网嵌入的链路预测算法对比 DeepWalk[20] 是一种基于随机游动的网络表 示学习方法。通过 DeepWalk 可获得图中节点的 向量化表示，进而可基于向量点积进行链接预 测。在真实图数据上将本文方法与基于 DeepWalk 的链接预测方法进行了实验对比。测试数 据为蛋白质交互网络 [ 2 1 ] (protein-Protein Interactions)。该数据包括 19 706 个节点、390 633 条边。采用 CN-ADS 与 DeepWalk 在算法执行时 间和 AUC 值上进行了比较。其中 DeepWalk 的参 K K K 数设置为：向量学习模型为 Skip-Gram，向量维数 设为 64。实验结果如图 8、9 所示。从图 8、9 结 果可知，小 值可保证算法执行效率，然而， AUC 较 DeepWalk 差。提高 值后，在执行时间 仍 小 于 DeepWal k 的情况下，可显著改 善 AUC 值。特别地，当 >32 后 ， AUC 值优于 DeepWalk。对于链接预测而言，本文算法在一定 条件下优于 DeepWalk 的结果。 220 200 180 160 140 120 100 80 4 8 12 16 20 K t/s 24 28 32 36 40 DeepWalk CN-ADS 图 8 PPI 数据集上 CN-ADS 与 DeepWalk 的时间对比 Fig. 8 Time comparison of CN-ADS and DeepWalk on PPI 0.74 0.72 0.70 AUC 0.68 0.66 0.64 0.62 0.60 0.58 0.56 4 8 12 16 20 K 24 28 32 36 40 DeepWalk CN-ADS 图 9 PPI 数据集上 CN-ADS 与 DeepWalk 的 AUC 对比 Fig. 9 AUC comparison of CN-ADS and DeepWalk on PPI 4 结束语 本文针对大规模网络数据在链路预测中存在 时间复杂度高、运算量大等问题，对现有的链路 预测方法进行扩展，结合现有的图勾勒技术，提 出了基于 ADS 技术的链路预测方法，根据勾勒的 结果结合现有的预测方法，定义了基于 ADS 结构 的链路预测方法，在算法预测精度和预测时间中 取得了较好的折衷，并在真实网络数据中验证了 算法的有效性。 本文是基于局部信息相似度进行链路预测 的，更精确的预测方法是基于全局信息进行预测 的，如何更好地在图勾勒技术的基础上基于全局 信息定义预测方法，是将来展开的要点之一。此 外，为验证图勾勒技术在链路预测问题上面的有 效性，本文是通过实验数据进行验证分析的，缺 少严谨的理论证明，后续工作将会致力于从理论 方面证明图勾勒技术对链路预测的有效性。 0.70 0.68 0.66 0.64 0.62 0.60 4 8 12 16 20 K (c) RA 与 RA-ADS 的 AUC 值对比 AUC RA-ADS RA 24 28 32 36 40 图 6 CN、AA、RA 度量指标 AUC 对比 (Yeast) Fig. 6 Comparison of the CN，AA，RA metrics AUC (Yeast) 第 4 期 尤洁，等：基于图勾勒的图链路预测方法 ·767·
·768· 智能系统学报 第14卷 参考文献： [I5]饶君，吴斌，东昱晓.MapReduce环境下的并行复杂网 络链路预则1.软件学报，2012.23(12)：3175-3186. [1]吕琳媛.复杂网络链路预测[]，电子科技大学学报， RAO Jun.WU Bin.DONG Yuxiao.Parallel link predic- 2010,395):651-661 tion in complex network using mapreduce[J.Journal of LYU Linyuan.Link prediction on complex networks[J]. software,2012,23(12:3175-3186. Journal of University of Electronic Science and Techno- [16]COHEN E.All-distances sketches[M]//KAO M Y.En- 1 ogy of China,,2010,395):651-661. cyclopedia of Algorithms.New York:Springer,2016: [2]CLAUSET A,MOORE C,NEWMAN M E J.Hierarchic- 2320-2334. al structure and the prediction of missing links in [17]BATAGELJ V,MRVAR A.Pajek datasets[EB/OL].2006 networks[J].Nature,2008,453(7191):98-101. http://vlado.fmf.uni-lj.si/pub/networks/data/default.html. [3]AIROLDI E M,BLEI D M,FIENBERG S E,et al.Mixed [18]BU Dongbo,ZHAO Yi,CAI Lun,et al.Topological membership stochastic blockmodels[J].Journal of ma- structure analysis of the protein-protein interaction net- chine learning research,2008,9:1981-2014. work in budding yeast[J].Nucleic acids research,2003. [4]YU Kai,CHU Wei,YU Shipeng,et al.Stochastic relation- 31(9:2443-2450 al models for discriminative link prediction[C]//Proceed- [19]WATTS D J,STROGATZ S H.Collective dynamics of ings of the 19th International Conference on Neural In- formation Processing Systems.Vancouver,Canada,2006: 'small-world'networks[J].Nature,1998,393(6684): 1553-1560 440-442. [5]LIBEN-NOWELL D,KLEINBERG J.The link-predic- [20]PEROZZI B,AL-RFOU R,SKIENA S.DeepWalk:on- tion problem for social networks[J.Journal of the associ- line learning of social representations[C]//Proceedings of ation for information science and technology,2007,58(7): the 20th ACM SIGKDD International Conference on 1019-1031. Knowledge Discovery and Data Mining.New York, [6]ADAMIC L A,ADAR E.Friends and neighbors on the USA,2014:701-710 Web[J].Social networks,2003,25(3):211-230. [21]BREITKREUTZ B J,STARK C,REGULY T,et al.The [7]LYU Linyuan,JIN Cihang,ZHOU Tao.Similarity index bioGRID interaction database:2008 update[J].Nucleic based on local paths for link prediction of complex net- acids research,2008,36(S1):D637-D640. works[J].Physical review E,2009,80(4):046122. 作者简介： [8]ZHOU Tao,Lu Linyuan,ZHANG Yicheng.Predicting missing links via local information[].The European phys- 尤洁，女，1991年生，硕土研究 ical journal B,2009,71(4):623-630. 生，主要研究方向为数据与知识 [9]KATZ L.A new status index derived from sociometric 工程。 analysis[J].Psychometrika,1953,18(1):39-43. [10]LEICHT E A,HOLME P,NEWMAN ME J.Vertex sim- ilarity in networks[J].Physical review E,2006,73: 026120. [11]KLEIN D J,RANDIC M.Resistance distance[J].Journal 李劲.男，1975年生，副教授，中 of mathematical chemistry,1993,12(1):81-95. 国人工智能学会不确定性人工智能专 [12]FOUSS F,PIROTTE A,RENDERS J M,et al.Random- 委会委员，主要研究方向为数据与知 walk computation of similarities between nodes of a 识工程。 graph with application to collaborative recommendation[J] IEEE transactions on knowledge and data engineering, 2007,193355-369. [13]BRIN S,PAGE L.The anatomy of a large-scale hypertex- tual Web search engine[J].Computer networks and ISDN 张赛，女，1994年生，硕士研究 systems,1998,30(1-7):107-117. 生，主要研究方向为数据与知识工程。 [14]JEH G,WIDOM J.SimRank:a measure of structural- context similarity [C]//Proceedings of the 8th ACM SIGK- DD International Conference on Knowledge Discovery and Data Mining.Edmonton,Alberta,Canada,2002: 538-543
参考文献： 吕琳媛. 复杂网络链路预测 [J]. 电子科技大学学报, 2010, 39(5): 651–661. LYU Linyuan. Link prediction on complex networks[J]. Journal of University of Electronic Science and Technology of China, 2010, 39(5): 651–661. [1] CLAUSET A, MOORE C, NEWMAN M E J. Hierarchical structure and the prediction of missing links in networks[J]. Nature, 2008, 453(7191): 98–101. [2] AIROLDI E M, BLEI D M, FIENBERG S E, et al. Mixed membership stochastic blockmodels[J]. Journal of machine learning research, 2008, 9: 1981–2014. [3] YU Kai, CHU Wei, YU Shipeng, et al. Stochastic relational models for discriminative link prediction[C]//Proceedings of the 19th International Conference on Neural Information Processing Systems. Vancouver, Canada, 2006: 1553–1560. [4] LIBEN-NOWELL D, KLEINBERG J. The link—prediction problem for social networks[J]. Journal of the association for information science and technology, 2007, 58(7): 1019–1031. [5] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social networks, 2003, 25(3): 211–230. [6] LYU Linyuan, JIN Cihang, ZHOU Tao. Similarity index based on local paths for link prediction of complex networks[J]. Physical review E, 2009, 80(4): 046122. [7] ZHOU Tao, Lü Linyuan, ZHANG Yicheng. Predicting missing links via local information[J]. The European physical journal B, 2009, 71(4): 623–630. [8] KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39–43. [9] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Physical review E, 2006, 73: 026120. [10] KLEIN D J, RANDIĆ M. Resistance distance[J]. Journal of mathematical chemistry, 1993, 12(1): 81–95. [11] FOUSS F, PIROTTE A, RENDERS J M, et al. Randomwalk computation of similarities between nodes of a graph with application to collaborative recommendation[J]. IEEE transactions on knowledge and data engineering, 2007, 19(3): 355–369. [12] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer networks and ISDN systems, 1998, 30(1-7): 107–117. [13] JEH G, WIDOM J. SimRank: a measure of structuralcontext similarity[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Alberta, Canada, 2002: 538–543. [14] 饶君, 吴斌, 东昱晓. MapReduce 环境下的并行复杂网 络链路预测 [J]. 软件学报, 2012, 23(12): 3175–3186. RAO Jun, WU Bin, DONG Yuxiao. Parallel link prediction in complex network using mapreduce[J]. Journal of software, 2012, 23(12): 3175–3186. [15] COHEN E. All-distances sketches[M]//KAO M Y. Encyclopedia of Algorithms. New York: Springer, 2016: 2320-2334. [16] BATAGELJ V, MRVAR A. Pajek datasets[EB/OL]. 2006 http://vlado.fmf.uni-lj.si/pub/networks/data/default.html. [17] BU Dongbo, ZHAO Yi, CAI Lun, et al. Topological structure analysis of the protein–protein interaction network in budding yeast[J]. Nucleic acids research, 2003, 31(9): 2443-2450. [18] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440–442. [19] PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk: online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2014: 701-710 [20] BREITKREUTZ B J, STARK C, REGULY T, et al. The bioGRID interaction database: 2008 update[J]. Nucleic acids research, 2008, 36(S1): D637-D640. [21] 作者简介： 尤洁，女，1991 年生，硕士研究 生，主要研究方向为数据与知识 工程。 李劲，男，1975 年生，副教授，中 国人工智能学会不确定性人工智能专 委会委员，主要研究方向为数据与知 识工程。 张赛，女，1994 年生，硕士研究 生，主要研究方向为数据与知识工程。 ·768· 智 能 系 统 学 报 第 14 卷