链路预测方法与网络结构的相关性
2021-10-01
来源:步旅网
第27卷第l2期 2017年12月 计算机技术与发展 COMPU rER rECHNOLOGY AND DEVELOPMENT Vo1.27 No.12 Dec. 2017 链路预测方法与网络结构的相关性 李旗旗,徐敏 (南京航空航天大学计算机科学与技术学院,江苏南京211106) 摘要:作为数据挖掘的一个分支,链路预测经过多年研究,已经提出了多种链路预测方法。基于网络结构的链路预测方 法因为在相似结构的网络中具有普适性,在近年来得到了广泛关注。然而,由于每个复杂网络的结构不同,链路预测方法 的预测准确度差别较大,同一种链路预测方法不可能在所有网络中都获得理想的预测效果。研究链路预测方法的准确度 和网络结构的相关性可以在已知一个复杂网络结构的情况下,选择合适的链路预测方法,也可以为链路预测的改进提供 理论依据。通过实验计算出常见链路预测方法在每个网络上的预测准确度,发现链路预测方法的预测准确度在不同结构 的网络中是不同的,结合网络的结构对实验结果进行分析,并据此提出了一种简单的链路预测方法选择方案。 关键词:复杂网络;链路预测;网络结构;相似性 中图分类号:TP393 文献标识码:A 文章编号:1673-629X(2017)12-0057-04 doi:10.3969/j.issn.1673-629X.0127.12.013 Correlation between Link Prediction Method and Network Structure LI Qi-qi.XU Min (School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics, Nanjing 211106,China) Abstract:As a branch ofdammining,link prediction has been studiedmany yearsinthe computerfield,and a variety oflik pmdnicfion methods are proposed.The lik nprediction method based On network structure has been widely concerned in recent years,because it is common in he tnetwork with similar structure.However,due tO the iferentd stnlcture of complex networks,the prediction accuracy of he tlik prnedictionmethodisdiferent,andthe samelik prnedictionmethod Can’t getthe desiredresultsin all networks.Analyzingthe corre— lation of network structure andthe accuracy oflink predictionmethod Can helptO choose a rightlik predinctionmethodfor a given net- work,and provietdhetheoretical basisforimprovinglink prediction.The prediction accuracy ofthelink predi ̄ionmethodis calculated by the experiment,andthe results showthatit existsdiferenceinthediferentnetwork structure.Analyzing experimentalresuls tcombined witl1the network slructnre.a simpleselection oflik predinctionmethodis proposed, Key words:complex networs;lkik prnediction;network sllalcmre;similarity O 引 言 自然界中大量的复杂系统都可以通过各种各样的 网络表现出来。一个典型的网络包含了一定数量的节 离”就是社交网络的一个独特网络结构。通过网络的 结构和属性,可以尝试去预测网络在下一个时间段的 变化,从而为实际生产提供正确的指导和建议。链路 预测就是一个很好的选择。 点和连接这些节点的边,其中节点表示的是一个真实 系统中的个体,而边则代表了个体之间的某种关系。 如果两个个体中存在某种关系,那么对应的两个节点 之间就存在一条连边。 复杂网络中的链路预测通过计算网络中尚未连边 的两个节点之间在未来产生连边的概率达到预测的目 的…。其研究思路和方法主要基于马尔可夫链和机器 今天,在生活中存在各种各样的复杂网络,比如社 交网络、生物网络、技术网络等,每一个网络都有自己 独特的网络结构和属性。社交网络中著名的“六度分 收稿日期:2016—12-11 修回日期:2O17一o4—19 学习。Sarukkai使用马尔可夫链对网络进行了链路预 测和路径分析 。之后学者对基于马尔可夫链的链路 预测方法进行了扩展,但是在这其中的很多方法都用 网络出版时间:2017-08-01 敏,博士,副教授,研究方向为模 基金项目:国家“973”重点基础研究发展计划项目(2014CB744900) 作者简介:李旗旗(1991一),男,硕士研究生,CCF会员(F_,200041166G),研究方向为机器学习、链路预测;徐式识别、机器学习。 网络出版地址:hup://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1557.078.html ・58・ 计算机技术与发展 第27卷 到了网络的节点信息。不少研究表明,使用节点信息 进行链路预测可以获得比较好的结果 ,但是现实中 很多网络都难以获得节点信息,而且即使获得了节点 信息,也不能保证信息的可靠性。因此,国内外学者越 来越关注基于网络结构的链路预测方法 。相比节点 属性信息,网络的结构更加可靠。然而,链路预测方法 在某种程度上都有自己的局限性,并不能在所有网络 上都有很好的预测准确度,所以对于一个已知网络,如 何寻找到一个合适的链路预测方法是很重要的。 1链路预测方法 用G( ,E)表示一个无向网络,其中 表示节点 集,E表示边集。G[t,t。]表示G在[t,t ]时间段的情 况,那么在(t。,t ]时间段G的情况就是G(t。,t ]。链 路预测关注的就是如何预测网络G从[t,t ]到(t , t ]的变化。 链路预测经过多年的研究,提出了各种各样的方 法。选择其中常用的l0种方法,为了能更好地介绍这 些方法,首先介绍一些在文章中使用的符号。其中, ,),表示节点,Ⅳ表示网络中节点的数量。k 和k 表示 节点 和Y的度数,F( )和F(y)分别表示节点 和 y的邻居节点集合。 基于局部信息的相似性方法是指仅通过节点的局 部信息(如节点的度和最近邻等)就可以计算出相似 度的方法。这种方法的优势在于时间复杂度低,适用 于大型的网络应用。 1.1共同邻居(CN) 共同邻居是一种比较简单的链路预测方法,其基 本假设为:如果两个尚未连边的节点有更多的共同邻 居,那么它们更倾向于连边。这种假设很容易理解,比 如在社交网络中,如果两个陌生人有很多共同的朋友, 那么他们将来成为朋友的概率也很大 。又比如, Newman等发现在科学家合作网络中,如果两个科学家 的共同合作伙伴很多,那么他们将来也很有可能会合 作 。其定义为: s =f( )n f(y) (1) 1.2 Salton 该方法是基于CN方法并且考虑连边两个端点节 点度的影响 。它的定义为: (2) 1.3 Jaccard 100多年前被提出,用于计算集合的相似度…。 它的定义为: s = (3) 1.4大度节点有利(Hub Promoted Index。HPI) HPI方法 的定义为: arin{k ,k } (4) 由于分母只有度比较小的节点决定,所以度比较 大的节点更容易和其他节点形成较高的相似性。 1.5大度节点不利(Hub Depressed Index,HDI) 其定义与HPI相似,只是分母取节点度数的较大 值㈨。 J。xy:也 (5) max{k , } 1.6 Adamic-Adar(AA) 其思想是度小的共同邻居节点的贡献大于度大的 共同邻居节点 。例如,在微博网络中,受关注较多 的人往往是某个领域的专家或者名人,因此共同关注 他们的人之间可能并不拥有特别相似的兴趣。相反, 如果两个人共同关注了一个粉丝很少的人(非专家), 那么说明这两个人确实具有相同的兴趣爱好或者重叠 的社交圈,因此有更高概率相连。 (6) m 1.7 Resource-Allocation(RA) 考虑网络中没有直接相连的两个节点 和Y,从 可以传递一些资源到Y,而在此过程中,它们的共同邻 居就成为传递的媒介n 。 假设每个媒介都有一个单位的资源并且平均分配 传给它的邻居,则y可以接收到的资源就可以定义为 节点 和Y的相似度,即: s ∑ (7) 当网络的平均度较小时,RA和AA区别不大;但 是当平均度较大时,就有很大区别了。 1.8局部路径(Local Path,LP) LP方法在CN方法的基础上考虑了三阶路径的 影响,其定义为: s =A 2+0 : (8) 其中,o【为可调参数;A为网络的邻接矩阵,A 表 示节点 和Y之间路径长度为3的路径长度。当Ol为 0时,LP指标就退化为CN指标。实验中选取的 值 为0.001。 1.9 Katz Katz方法考虑了网络的所有路径 ,其定义为: s =∑卢 I pathl,y l= +J8 (A ) +…(9) 其中,卢用来调节高阶路径的贡献。当卢值很小 时,高阶路径的贡献也就很小了,此时Katz的预测结 果接近于局部路径方法。 第12期 李旗旗等:链路预测方法与网络结构的相关性 ・59・ 2实验数据与评价方法 为了比较每一种方法的准确度,实验中选取了7 能被用来预测 。为了保证在抽样后训练集仍然保 持连通,实验中采用的划分策略是,在随机抽样的基础 上加入网络连通性判断机制,即首先在给定的网络中 选取一条边,然后判断这条边的两个节点在删除这条 组提取自真实网络的数据集,实验结果通过AUC值进 行评价。 2.1数据集 边之后是否仍然可以连通,如果可以则将该边加入测 试集,否则放弃,然后重新随机抽取一条边。 使用AUC来衡量链路预测方法的准确度。AUC 是指ROC曲线下的面积,在信号探测理论中,ROC曲 线用来评价某种分类器的分类效果 。这种方法同 样可以用来衡量链路预测方法的准确度。 USAir:网络中的每个节点对应一个机场,如果在 两个机场之间存在一条直达航线,那么两个机场之间 存在一条连边。 NS:这个网络是由M.Newman在2006年收集的, 其中包含了在网络科学领域的科学家发表的论文。网 络中的节点表示科学家,两个节点之间存在连边说明 两个科学家合作发表过论文。 对所有未观察到的连边进行排名,AUC的值可以 理解为:在测试集中随机选择一条连边的得分高于随 机选择的一条不存在的边的概率。在算法的实现中, 通常是计算每个未观察到的连边的得分,而不是给出 一Power:美国西部电网,是由Watts和Strogatz收集 的。节点表示变电站或者换流站,连边表示它们之间 有高压线。 Router:Internet路由层次网络,每个节点表示一个 个有序的列表,因为后者需要更大的时间复杂度。 然后,每次从测试集中随机选取一条连边,再随机从不 存在的连边中选取一条连边,比较它们的得分。如果 在n次实验中,有n 次前者的分数更高,n 次两者分 数相同,那么AUC的值为: AUC: ± : n 路由器,如果两个路由器之间可以直接进行数据包交 换,则它们之间存在一条连边。 Yeast:蛋白质相互作用网络,节点表示蛋白质,边 表示它们之间的相互作用。 Wiki—vote:维基百科中的活跃用户可以被提名为 (10) 管理员,当一个用户被提名时,维基百科会组织选举, 获得支持最多的用户晋升为管理员。用户表示节点, 选举行为对应于网络中的边,如果用户A给用户B投 票,那么就有一条边从A指向B。 从表达式中可以看出,随机选择法的AUC值约为 0.5,所以一个链路预测算法的AUC值大于0.5的程 度就是该算法比随机算法精确的程度。在实验中,为 了减少随机抽样对结果的影响,AUC的计算采取多次 计算求平均值的方法。 Facebook:Facebook数据集是通过其应用从调查 的参与者中收集到的,节点表示用户,边表示两个用户 之间的好友关系。 2.2评价方法 一3实验结果与分析 实验中计算了每个链路预测方法在所有7个网络 数据集上的预测准确度,结果显示为AUC值。表1是 个时间序列中的预测意味着要将数据集按照时 间戳分为训练集和测试集,其中训练集视为已知的信 息,测试集视为未知信息,这个集合中的所有信息都不 每种链路预测方法的准确度。 表1链路预测方法的准确度(AUC值) 可以看出,l0种链路预测方法基本上都给出了好 于随机选择方法的预测效果,并且基于共同邻居的方 法(CN、Salton、Jaccard、HPI、HDI、AA、RA)预测准确度 相差不多,在CN基础上考虑连边的两个端点度的影 响整体表现不如CN,AA和RA方法的准确度相比于 其他方法有较小的提升。 ・60・ 计算机技术与发展 第27卷 但是也可以看出一些特例,比如在Power和Rout. eY网络中,除了Katz,其他方法的预测准确度都比较一 般;在Facebook和Wiki—vote网络中,Katz方法在JB= 0.01时AUC值很低,在.8=0.001时预测效果很好。 针对实验结果的一些现象,将根据网络结构分析 这些现象的原因。表2是在实验中使用的网络的一些 结构信息。 表2网络结构信息 SMton、Jaccard等方法在USAir和Wiki—vote上的 预测效果和CN有比较明显的差距,可能的原因是这 两个网络中存在比较明显的“富人俱乐部现象”,即度 数大的节点相对于度数小的节点更容易和其他度数大 的节点形成连边,而SMton等方法惩罚了连边中两个 端点的度数,在一定程度上对预测结果起到了消极 作用。 Power和Router网络的聚类系数很小,说明节点 之间的紧密程度很低,它们的平均度很小也说明了这 一点。因此,这两个网络中的两个节点之间的共同邻 居节点个数也很少,无法为这两个节点是否相似提供 足够的证据,这也就是为什么基于共同邻居的方法预 测结果都不好的原因。基于路径的预测算法受这个问 题的影响较小,可以看到LP和Katz的预测结果都不 错。唯一值得注意的是,LocMP对于Power的预测结 果不是很好,这是因为LP只是考虑了三阶路径,而 Power网络不仅稀疏而且直径很大,仅考虑三阶路径 性能提升有限。 Katz由于考虑了全路径,所以它在所有的网络上 都有比较好的表现,当然这也意味着Katz方法的时间 复杂度远远高于其他方法。在Wiki—vote和Facebook 中,Katz在参数JB=0.01时出现了比较明显的异常情 况,这恰好体现了Katz方法的一个明显问题。根据 Katz的公式可以看到,其时间复杂度相当高,这对于稍 微大型的网络都是无法接受的,但是在口小于邻接矩 阵最大特征值的倒数的情况下,Katz的公式可以根据 级数收敛转化为: S=(J一 )~一, (11) 而矩阵求逆的时间复杂度为O(N3)量级,从而大 大减少了时间开支。Facebook和Wiki—vote的邻接矩 阵的最大特征值均小于0.01而大于0.001,而实验中 使用的是转化之后的公式,因此导致Katz预测结果的 异常。 另外,Yeast网络的聚类系数同样很小,但是CN、 AA等方法也得到了比较不错的预测效果,可能的原 因有两个: (1)Yeast和Power、Router相比平均度较大,根据 聚类系数的定义,节点的度数会在一定程度上抑制包 含该节点的三角形的个数对聚类系数的贡献。如果一 个节点的度很大,即使包含它的三角形个数很多,也会 表现出较低的聚类系数; (2)Yeast网络中度数较小的节点都有比较大的 聚类系数,由于度数较大的节点聚类系数较小,导致整 体的聚类系数较小,但是节点对之间有足够的共同邻 居节点来证明它们之间的相似性。 根据上述分析,对于一个结构已知的网络,一种简 单的链路预测方法推荐方案描述如下: (1)对于聚类系数和平均度较小的网络,采用基 于路径的方法,其中Katz方法在大多数情况下获得了 较好的效果。需要注意的是,Katz方法在使用之前要 计算|lB的取值上限,LP方法虽然仅考虑了局部路径, 但是没有参数的限制。 (2)对于聚类系数和平均度较大的网络,基于共 同邻居的方法能够获得较好的结果,并且在时间复杂 度上要优于基于路径的方法。 (3)在基于共同邻居的方法中,CN、AA和RA可 以作为优先选择的方法,AA和RA在异配性比较强的 网络中会显示出比CN更好的预测效果。 4结束语 文中介绍了10种链路预测方法,并且在7个真实 网络中比较了它们的预测准确度。实验结果表明,对 于平均度和聚类系数较小的网络,基于共同邻居的方 法往往不能给出一个很好的预测效果,但是Katz可以 获得很好的预测准确度。 同时还发现,社交网络的邻接矩阵的最大特征值 的倒数往往较小。在这种情况下,对Katz方法的参数 值的选取有一定限制,此时可以考虑使用基于局部路 径的方法。可以看到,在链路预测中,获得一个网络的 结构对于寻找一个合适的链路预测方法很有帮助。 参考文献: [1] 吕琳嫒.复杂网络链路预测[J].电子科技大学学报,2010, 39(5):651~661. (下转第66页) ・66・ 计算机技术与发展 第27卷 mensions via hashing[C]//International conference on very large data bases.[s.1.]:Morgan Kaufmann Publishers Inc., 2000:5 l8—529. [18]Hastie T,Tibshirani R.Diseriminant adaptive nearest neighbor classiifcation[J].IEEE Trnsaactions on Patten Anarlysis& Machine Intelligence,1996,18(6):607-616. [19]Yang Y,Pedel ̄en J O.A comparative study on feature selee— [9]Weiss Y,Torrlaba A,Fergus R.Spectral hashing[C]//Con— ference on nenrM iformatnion processing systems.Vancouver, tion in text categorization[C]//Fourteenth international con— ference on machine learning.[s.1.]:Morgan Kanfmann Pub— lishers Inc.,1997:412—420. British Columbia,Canada:[s.n.],2008:1753—1760. [10]Gong Y,Lazebnik S,Gordo A,ct a1.Iterative quantization:a procrustean approach to learning binary codes for large-scale [20]Krizhevsky A.Learning multiple layers of features from tiny images[D].Toronto:University ofToronto,2009. [21]Oliva A,Torralba A.Modeling the shape of the scene:a holis- image retrieval[J].IEEE Transactions on Pattern Analysis& Machine Intelligence,2013,35(12):2916-2929. [11]Salakhutdinov R,Hinton G.Semantic hashing[J].Internation- la Journal of Approximate Reasoning,2009,50(7):969-978. tic representation of the spaital envelope[J].International Journal of Computer Vision,2001,42(3):145-175. [12]Hinton G E,Osindero S,Yw T.A fast learning algorithm for deep beliefnets[J].Neural Computation,2006,18(7):1527- 1554. [22]Jeyakumar V,Rubinov A M,Wu Z Y.Non-convex quadratic minimization problems with quadratic constraints:global opti— mality conditions[J].Mathematical Programming,2007,1 10 (3):521-541. [23]Jegou H,Douze M,ehmiSd C.Product quantization orf nearest [13]曲建岭,杜辰飞,邸亚洲,等.深度自动编码器的研究与展 望[J].计算机与现代化,2014(8):128—134. [14]Huang G B,Zhu Q Y,Siew C K.Extreme learning machine: neighbor search[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(1):117-128. theoyr and applications[J].Neurocomputing,2006,70(1-3): 489-501. [24]耿丽娟,李星毅.用于大数据分类的KNN算法研究[J].计 琳,等.神经网络极速学习方法研究 [15]邓万宇,郑庆华,陈算机应用研究,2014,31(5):1342—1344. [25]Price A L,Patterson N J,Plenge R M,et 1.Praincipal compo— nents analysis corrects for stratiifcation in genome-wide asso— [J].计算机学报,2010,33(2):279—287. [16]邓万宇,杨丽霞.基于Spark的OS—ELM并行化算法[J]. 西安邮电大学学报,2016,21(2):101—104. [17]Carreira-Perpi6n M A,Wang W.Distributed optimization of elation studies[J].Nature Genetics,2006,38(8):904. [26]Carreira-Perpinan M A,Raziperehikolaei R.Hashing with bi— nary autoencoders[C]//IEEE conference on computer vision and pattern recognition.[s.1.]:IEEE,2015:557-566. deeply nested systems[C]I/AISTATS.[s.I.]:[s.n.], 2014. (上接第60页) [2]Sarukkai R R.Link prediction and path analysis using Markov chains[J].Computer Networks,2000,33(1—6):377—386. [3] 刘大伟,吕元娜,余智华.一种改进的复杂网络链路预测算 法[J].小型微型计算机系统,2016,37(5):1071—1074. [4]傅颖斌,陈羽中.基于链路预测的微博用户关系分析[J]. 计算机科学,2014,41(2):201—205. ization of modularity in metabolic networks[J].Science, 2002,297(5586):1551. Zhou T,Lu L,Zhang Y C.Predicting missing links via local in— [1O] fomatrion[J].Physics ofCondensed Matter,2009,71(4):623 -630. [11] Adamic L A,Adar E.Friends and neighbosr on the web[J]. Social Networks,2003,25(3):21 1—230. [5]丁兆云,贾焰,周斌,等.社交网络影响力研究综述 [12] Ou Q,Jin Y D,Zhou T,et a1.Power-law strength-degree cor- relation from resource—-allocation dynamics on weighted net-・ [J].计算机科学,2014,41(1):48—53. [6] Newman M E J.Clustering and preferential attachment in works[J].Physical Review E,2007,75:021 102. Katz L.A new status index derived from sociometric analysis [13] growing networks[J].Physical Review E,2001,64(2): 025102. [J].Psychometrika,1953,18(1):39—43. Ln L.Zhou T.Link prediction in complex networks:a survey [14] [7] Salton G,Mcgill M J.Introduction to modern ifnormation re. trieval[M].[s.1.]:McGraw—Hill,1983. [J].Physica A Statisticla Mechanics&Its Applications, 2011,390(6):1150—1170. [8] Jaceard P.Etude de la distribution lforlae dans une portion des Alpes et du Jura『J].Bulletin De La Societe Vaudoise Des [15] Fawcett T.Introduction to ROC analysis[J].Patten Recrogni— tion Lettes,r2006,27(8):861-874. Sciences Naturelles,1901,37(142):547—579. [9]Ravasz E,Somera A L,Mongru D A,et a1.Hierarchical organ-