2. 云南省软件工程重点实验室,云南 昆明 650091
2. Key Laboratory in Software Engineering of Yunnan Province, Kunming 650091, China
图上的链路预测是指通过已有的网络拓扑结构和节点属性信息等预测网络中尚未产生连边的两个节点之间产生链接的可能性,或者是已经产生但是并未发现的链接信息,是图数据挖掘的重要方向之一,受到广泛的关注。
当前,关于链路预测的研究方法主要包括3种:1)基于极大似然估计的方法。该方法将网络链接看作是内在层次的反映,采用极大似然估计进行预测。但该方法的预测准确性与样本数据量有关,高质量的预测需要大的样本数据,导致计算复杂度高,不适用于大规模网络[1-2];2)基于概率模型方法。通过建立可调参数模型再现网络的结构和关系特征,将预测问题转化为预测边的属性问题进行预测,此类方法具有较高预测精度,但预测过程中涉及到非普适性的参数和节点属性信息,使得应用范围受限,计算复杂度高[3];3)基于节点相似性预测方法[4-14]。假设节点之间存在链接的可能性与节点之间的相似性紧密相关,通过预测节点之间的相似性来进行链路预测。其中,基于节点相似性模型的预测方法由于方法简单,链接预测质量较好等成为目前主流的链接预测方法。
但是,基于节点相似性的预测方法,其计算复杂度为
针对已有研究工作的不足,本文在保证链路预测质量的前提下,降低预测算法的计算复杂性角度,提出基于图勾勒[16]的链路预测算法。首先,基于图勾勒技术对现有的链路预测方法进行扩展,定义了基于ADS(all-distances sketches)结构的链路预测相似性度量指标,提出了基于图勾勒的链路预测算法,将一般链路预测算法的计算复杂度由
给定无向图
下面分别给出本文中采用的3种节点间相似度度量指标及定义:
定义1 Common Neighbor(CN)[5]:如果图中两个节点拥有的共同邻居节点越多,那么这两个节点就越相似,则它们之间存在或者未来发生链接的可能性就越大。相似度定义为
$ S_{xy}^{{\rm{CN}}} = \left| {\varGamma \left( x \right) \cap \varGamma \left( y \right)} \right| $ | (1) |
式中:
定义2 Adamic Adar(AA)[6]:AA在CN的基础上,赋予邻居节点权重,它认为共同邻居节点的节点度对相似度也有影响,共同邻居节点度越大,它对节点相似度的贡献越小,反之,共同邻居节点度越小,它对节点的相似度的贡献越大。因此在求相似度的公式中,对共同邻居节点度赋予一个惩罚因子。其相似度定义为
$ S_{xy}^{{\rm{AA}}} = \mathop \sum \limits_{z \in \varGamma \left( x \right) \cap \varGamma \left( y \right)} \frac{1}{{\log\left( {{d_z}} \right)}} $ | (2) |
式中:
定义3 Resource Allocation(RA)[7]:RA从资源分配的角度考虑节点相似性。它认为没有直接相连的两个节点,资源可以从一个节点传递到另一个节点,它们的共同邻居节点是两个节点传递资源的媒介,每一个媒介都有一个单位的资源,它将自己的资源平均分配给它的邻居节点,另一个节点接收到的资源数就是这两个节点的相似度。其相似度定义为
$ S_{xy}^{\rm{{RA}}} = \mathop \sum \limits_{z \in \varGamma \left( x \right) \cap \varGamma \left( y \right)} \frac{1}{{{d_z}}} $ | (3) |
评估指标:链路预测结果的衡量指标主要包括Precision(准确率)[17]和AUC(曲线下面积)[18],Precision针对局部结果进行评估,AUC基于全局进行评估,本文讨论的是整体性能,故以AUC作为预测精度的评估标准。AUC的值越高,则链路预测整体性能较好。
定义4 对于边集进行数据划分,有E =
${\rm{AUC}} = \frac{{{n'} + 0.5{n''}}}{n}$ | (4) |
ADS(all-distances sketches)是定义在图节点上的数据摘要结构。通过对图中各节点的可达邻居节点集进行抽样,抽样结果与原节点的集合构成了该节点的Sketch结构。在大图上,基于ADS可有效进行节点相似关系,中心度等度量计算[16]。
定义5 节点
${\rm{ADS}}\left( v \right) = \{ \left( {u, d\left( {v, u} \right)} \right)|r\left( u \right) < K_r^{\rm th}\left( {N\left( {v, u} \right)} \right)\} $ | (5) |
式中:
例1 图的ADS结构如图1所示,该图为有向图带权图。节点上的数值为勾勒ADS结构所对应生成的0 ~ 1的随机数。
![]() |
Download:
|
图 1 图的ADS示例 Fig. 1 An illustration of ADS in a graph |
图中每个节点的ADS结构是一个集合。以节点1为例,ADS(1)(
$ \begin{aligned} {\rm{ADS}}\left( 1 \right) = \{ \left( {1, 0} \right), \left( {2, 8} \right), \left( {3, 9} \right), \left( {4, 18} \right), \left( {6, 18} \right){\rm{\} }}\qquad\quad\\ {\rm{ADS}}\left( 2 \right) = {\text{\{ (2, 0), (5, 8), (4, 10), (6, 10), (3, 10)\} }}\qquad\\ {\rm{ADS}}\left( 5 \right) \!\!=\!\! \{ (5, 0), \!(8, 10), \!(7, 19), \!(6, 28),\! (1, 29),\! (3, 38),\! (4, 47)\} \end{aligned} $ |
从给出的
ADS是对节点的全局邻居节点进行抽样,而CN、AA、RA 3种算法的默认情况是基于1跳邻居进行计算的,故为了排除多跳邻居对相似度的影响,基于节点的ADS结构的链路预测算法中也只考虑一跳邻居节点。基于1跳邻居的ADS的大小永远不大于节点的1跳邻居数,所以在求两个集合的相似度时,运算量也相应减少。在AA算法和RA算法中还涉及到求共同邻居节点的度,其他相似性度量指标也涉及到节点中心度的计算等,这个过程中需要耗费大量的计算时间,而ADS抽样的过程中会过滤掉一部分的邻居节点,故在一定程度上减少了部分求节点度、中心度的运算量。
对图勾勒后,得到的ADS结构不再是单一的节点集、边集所构成的图数据,而是由节点及其部分邻居节点构成的集合,这部邻居节点包括了一跳至多跳另据节点,还带有相应的可达距离,故ADS需要根据自身结构定义合适的相似性指标,具体定义如下:
定义6 基于ADS的CN度量指标(ADS-CN)定义如下:
$ S_{xy}^{{\rm{ADS - CN}}} = \left| {{\rm{ADS}}{{\left( x \right)}_1} \cap {\rm{ADS}}{{\left( y \right)}_1}} \right| $ | (6) |
式中:
定义7 基于ADS的AA度量指标(ADS-AA)如下:
$ S_{xy}^{{\rm{ADS - AA}}} = \mathop \sum \limits_{z \in {\rm{ADS}}{{\left( x \right)}_1} \cap {\rm{ADS}}{{\left( y \right)}_1}} \frac{1}{{{\rm{log}}\left( {{d_z}} \right)}} $ | (7) |
式中:
定义8 基于ADS技术扩展的RA度量指标(ADS-RA)定义如下:
$ S_{xy}^{{\rm{RA}}} = \mathop \sum \limits_{z \in {\rm{ADS}}{{\left( x \right)}_1} \cap {\rm{ADS}}{{\left( y \right)}_1}} \frac{1}{{{d_z}}} $ | (8) |
公式中符号含义同定义6。
2.1 基于ADS勾勒技术的链路预测算法首先简要介绍链路预测算法的基本思想,链路预测算法首先将待预测数据集
基于ADS勾勒技术的链路预测算法的具体描述如算法1。
分析算法1的时间复杂度。首先,由文献[16]可知,对于图中的一个节点
算法1 基于ADS勾勒技术的链路预测算法
输入
输出 AUC值。
1) 切割边集E为训练集Er和测试集Ep,
2)
3)
//找出训练集中不存在连边的结点对集合
4)
5)
//得到
6)
//得到
7)
8)
9) a:从
10)
11)
12)
13)
14)
为提高链路预测算法的执行效率,在算法1基础上,进一步提出了基于Spark的并行化的链路预测算法。该算法具体描述如算法2。算法2的执行过程与算法1一致,但算法2将算法1中的每一步骤采用弹性分布式数据集(RDD)进行了实现。基于RDD表示,采用对RDD的Map-reduce并行化操作有效提升链接预测算法的执行效率。RDD转换和操作细节详见算法2中的描述。
算法2 基于Spark的并行化链路预测算法
输入
输出 AUC值。
//创建边集
1)
//创建训练集
2)
//创建测试集
3)
//找出训练集中不存在连边的结点对集合
4)
//求出各顶点的邻居节点
5)
6)
//求出各结点的节点度
(7)
//求结点x, y的相似度
8)
9)
10)
11)
表1给出了本文实验数据集统计信息。其中,
![]() |
表 1 实验数据集拓扑结构信息 Tab.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计算公式中的
ADS勾勒技术是对原数据的一种抽样方法,通过抽样达到降低计算复杂度的目的,但是由于它只是对数据的近似勾勒,所以用勾勒的结果进行数据的分析与挖掘,在精度上会有一定的损失,是不可避免的,但是损失一定范围内的精度,却提升了较大的计算效率。
实验结果已经表明,基于ADS的链路预测方法在
图2~4分别给出了USAir97、Yeast、Grid数据集基于CN、AA、RA3种相似性度量指标的两种算法的执行效率。从图中可以看出基于ADS勾勒技术的链路预测算法执行时间均低于原链路预测算法的执行时间,由于链路预测算法不涉及到
![]() |
Download:
|
图 2 CN、AA、RA度量指标运行时间对比(USAir97) Fig. 2 CN, AA, RA metrics comparison of run time (USAir97) |
![]() |
Download:
|
图 3 CN、AA、RA度量指标运行时间对比(Yeast) Fig. 3 CN,AA,RA metrics comparison of run time (Yeast) |
![]() |
Download:
|
图 4 CN、AA、RA度量指标运行时间对比(Grid) Fig. 4 CN,AA,RA metrics comparison of run time (Grid) |
图5~7给出了3个数据集在两种算法下的预测精度,实验结果显示,基于ADS的链路预测算法的预测精度随着
![]() |
Download:
|
图 6 CN、AA、RA 度量指标 AUC 对比 (Yeast) Fig. 6 Comparison of the CN,AA,RA metrics AUC (Yeast) |
从表1中可以看出USAir97数据集节点远小于Yeast数据集和Grid数据集,但是图中结果显示USAir97数据集较为理想的预测结果对应的
图5和图6中精度的变化逐渐上升最后趋于稳定,但是图7中精度的变化有波动,在千分之一上下波动,存在原因可能有两个:1)计算AUC过程中抽取的次数不够所造成的误差;2)ADS节点随机值变化过程中产生的误差。
![]() |
Download:
|
图 5 CN,AA,RA度量指标AUC对比(USAir97) Fig. 5 Comparison of the CN, AA, RA metrics AUC (USAir97) |
![]() |
Download:
|
图 7 CN、AA、RA度量指标AUC对比(Grid) Fig. 7 comparison of the CN,AA,RA metrics AUC (Grid) |
DeepWalk[20]是一种基于随机游动的网络表示学习方法。通过DeepWalk可获得图中节点的向量化表示,进而可基于向量点积进行链接预测。在真实图数据上将本文方法与基于DeepWalk的链接预测方法进行了实验对比。测试数据为蛋白质交互网络[21](protein-Protein Interactions)。该数据包括19 706 个节点、390 633 条边。采用CN-ADS与DeepWalk在算法执行时间和AUC值上进行了比较。其中DeepWalk的参数设置为:向量学习模型为Skip-Gram,向量维数设为64。实验结果如图8、9所示。从图8、9结果可知,小
![]() |
Download:
|
图 8 PPI数据集上CN-ADS与DeepWalk的时间对比 Fig. 8 Time comparison of CN-ADS and DeepWalk on PPI |
![]() |
Download:
|
图 9 PPI数据集上CN-ADS与DeepWalk的AUC对比 Fig. 9 AUC comparison of CN-ADS and DeepWalk on PPI |
本文针对大规模网络数据在链路预测中存在时间复杂度高、运算量大等问题,对现有的链路预测方法进行扩展,结合现有的图勾勒技术,提出了基于ADS技术的链路预测方法,根据勾勒的结果结合现有的预测方法,定义了基于ADS结构的链路预测方法,在算法预测精度和预测时间中取得了较好的折衷,并在真实网络数据中验证了算法的有效性。
本文是基于局部信息相似度进行链路预测的,更精确的预测方法是基于全局信息进行预测的,如何更好地在图勾勒技术的基础上基于全局信息定义预测方法,是将来展开的要点之一。此外,为验证图勾勒技术在链路预测问题上面的有效性,本文是通过实验数据进行验证分析的,缺少严谨的理论证明,后续工作将会致力于从理论方面证明图勾勒技术对链路预测的有效性。
[1] |
吕琳媛. 复杂网络链路预测[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. DOI:10.3969/j.issn.1001-0548.2010.05.002 ( ![]() |
[2] |
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. DOI:10.1038/nature06830 (![]() |
[3] |
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. (![]() |
[4] |
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.
(![]() |
[5] |
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. (![]() |
[6] |
ADAMIC L A, ADAR E. Friends and neighbors on the Web[J]. Social networks, 2003, 25(3): 211-230. DOI:10.1016/S0378-8733(03)00009-1 (![]() |
[7] |
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. DOI:10.1103/PhysRevE.80.046122 (![]() |
[8] |
ZHOU Tao, Lü Linyuan, ZHANG Yicheng. Predicting missing links via local information[J]. The European physical journal B, 2009, 71(4): 623-630. DOI:10.1140/epjb/e2009-00335-8 (![]() |
[9] |
KATZ L. A new status index derived from sociometric analysis[J]. Psychometrika, 1953, 18(1): 39-43. DOI:10.1007/BF02289026 (![]() |
[10] |
LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J]. Physical review E, 2006, 73: 026120. DOI:10.1103/PhysRevE.73.026120 (![]() |
[11] |
KLEIN D J, RANDIĆ M. Resistance distance[J]. Journal of mathematical chemistry, 1993, 12(1): 81-95. DOI:10.1007/BF01164627 (![]() |
[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, 19(3): 355-369. DOI:10.1109/TKDE.2007.46 (![]() |
[13] |
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. DOI:10.1016/S0169-7552(98)00110-X (![]() |
[14] |
JEH G, WIDOM J. SimRank: a measure of structural-context similarity[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Edmonton, Alberta, Canada, 2002: 538–543.
(![]() |
[15] |
饶君, 吴斌, 东昱晓. 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. ( ![]() |
[16] |
COHEN E. All-distances sketches[M]//KAO M Y. Encyclopedia of Algorithms. New York: Springer, 2016: 2320-2334.
(![]() |
[17] |
BATAGELJ V, MRVAR A. Pajek datasets[EB/OL]. 2006 http://vlado.fmf.uni-lj.si/pub/networks/data/default.html.
(![]() |
[18] |
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.
(![]() |
[19] |
WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393(6684): 440-442. DOI:10.1038/30918 (![]() |
[20] |
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
(![]() |
[21] |
BREITKREUTZ B J, STARK C, REGULY T, et al. The bioGRID interaction database: 2008 update[J]. Nucleic acids research, 2008, 36(S1): D637-D640.
(![]() |