复杂网络链路预测

第39卷第5期电子科技大学学报Vol.39No.52010年9月JournalofUniversityofElectronicScienceandTechnologyofChinaSep.2010复杂网络链路预测吕琳媛(弗里堡大学物理系瑞士弗里堡CH-1700)【摘要】网络中的链路预测是指如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生连接的可能性。预测那些已经存在但尚未被发现的连接实际上是一种数据挖掘的过程，而对于未来可能产生的连边的预测则与网络的演化相关。传统的方法是基于马尔科夫链或者机器学习的，往往考虑节点的属性特征。该类方法虽然能够得到较高的预测精度，但是由于计算的复杂度以及非普适性的参数使其应用范围受到限制。另一类方法是基于网络结构的最大似然估计，该类方法也有计算复杂度高的问题。相比上述两种方法，基于网络结构相似性的方法更加简单。通过在多个实际网络中的实验发现，基于相似性的方法能够得到很好的预测效果，并且网络的拓扑结构性质能够帮助选择合适的相似性指标。该文综述并比较了若干有代表性的链路预测方法，展望了若干重要的开放性问题。关键词复杂网络;链路预测;最大似然估计;概率模型;相似性指标中图分类号TP391文献标识码Adoi:10.3969/j.issn.1001-0548.2010.05.002LinkPredictiononComplexNetworksLÜLin-yuan(DepartmentofPhysics,UniversityofFribourgFribourgSwitzerlandCH-1700)AbstractLinkpredictionaimsatestimatingthelikelihoodoftheexistenceoflinksbetweennodes.Thepredictingofexistentyetunknownlinksissimilartothedataminingprocess,whilethepredictingoffuturelinksrelatestothenetworkevolution.ThetraditionalmethodsarebasedonMarkovChainsandmachinelearningwhichusuallyinvolvethenodeattributesinformation.Althoughthesemethodscangivegoodprediction,thehighcomputationalcomplexitylimitstheirapplicationsinlarge-scalesystems.Theapproachesbasedonmaximumlikelihoodapproximationalsosufferthisshortcoming.Anothergroupofmethodsisbasedonthenodesimilaritythatisdefinedsolelybasedonthenetworkstructure.Extensiveexperimentsonmanyrealnetworksshowthatthesimilarity-basedmethodscangivegoodpredictionwhilewithlowercomputationalcomplexitycomparingwiththeabovetwokindsofmethods.Thisarticleintroducesandcomparesmanyrepresentativelinkpredictionmethods,andoutlinessomeimportantopenproblems,whichmaybevaluableforrelatedresearchdomains.Keywordscomplexnetworks;linkprediction;maximumlikelihoodapproximation;probabilisticmodel;similarityindex收稿日期：2010-07-18基金项目：瑞士国家科学基金(200020-121848)；国家自然科学基金(11075031)作者简介：吕琳媛(1984-)，女，博士生，主要从事信息物理，包括链路预测、推荐算法以及网络结点排序等方面的研究.网络中的链路预测(linkprediction)，既包含了对未知链接(existentyetunknownlinks)的预测，也包含了对未来链接(futurelinks)的预测。链路预测作为数据挖掘领域的研究方向之一在计算机领域已有较深入的研究，研究的思路和方法主要基于马尔科夫链和机器学习。文献[2]应用马尔科夫链进行网络的链路预测和路径分析。之后，文献[3]将基于马尔科夫链的预测方法扩展到自适应性网站(adaptivewebsites)的预测中。此外，文献[4]提出一个回归模型在文献引用网络中预测科学文献的引用关系，方法不仅用到了引文网络的信息，还有作者信息、期刊信息以及文章内容等外部信息。应用节点属性的预测方法还有很多，如文献[5]利用网络的拓扑结构信息以及节点的属性，建立了一个局部的条件概率模型进行预测。文献[6]基于节点的属性定义了节点间的相似性，可以直接用于进行链路预测。虽然应用节点属性等外部信息的确可以得到很好的预测效果，但是很多情况下，信息的获得是非常困难的，甚至是不可能的，如很多在线系统的用户信息都是保密的。另外，即使获得了节点的属性信息，也很难保证信息的可靠性，即属性是否反映了节点的真实情况，如在线社交网络中，很多用户的注册信息都是虚假的。更进一步，在能够得到节点属性的精确信息的情况下，如何鉴别出哪些信息对网络的链路预电子科技大学学报第39卷652测是有用的，哪些信息是没用的，仍然是个问题。最近几年，基于网络结构的链路预测方法受到越来越多的关注。相比节点的属性信息而言，网络的结构更容易获得，也更加可靠。同时，该类方法对于结构相似的网络具有普适性，从而避免了对不同网络需要机器学习获得一些特定的参数组合。文献[7]提出了基于网络拓扑结构的相似性定义方法，并分析了若干指标对社会合作网络中链路预测的效果。另外一类链路预测方法是基于网络结构的最大似然估计。2008年，文献[8]提出了一种利用网络的层次结构进行链路预测的方法，并在具有明显层次结构的网络中表现很好。此外，利用随机分块模型[9]预测网络缺失边和错误边的链路预测方法。值得一提的是，该篇文章第一次提到网络错误连边(spuriouslinks)的概念，即在网络已知的链接中很可能存在一些错误的链接，比如人们对蛋白质相互作用关系的错误认知。链路预测问题受到来自不同领域、拥有不同背景的科学家的广泛关注，首先是因其重大的实际应用价值。如在生物领域研究中，蛋白质相互作用网络和新陈代谢网络，节点之间是否存在链接，或者说是否存在相互作用关系，是需要通过大量实验结果进行推断的。已知的实验结果仅仅揭示了巨大网络的冰山一角。仅以蛋白质相互作用网络为例，酵母菌蛋白质之间80%的相互作用不为人们所知[11]，而对于人类自身，人们知道的仅有可怜的0.3%[12-13]。由于揭示该类网络中隐而未现的链接需要耗费高额的实验成本，如果能够事先在已知网络结构的基础上设计出足够精确的链路预测算法，再利用预测的结果指导试验，就有可能提高实验的成功率，从而降低实验成本，并加快揭开该类网络真实面目的步伐。实际上，社会网络分析中也会遇到数据不全的问题，链路预测同样可以作为准确分析社会网络结构的有力的辅助工具[14-15]。除了帮助分析数据缺失的网络，链路预测算法还可以用于分析演化网络。如近几年在线社交网络发展非常迅速[16]，链路预测可以基于当前的网络结构预测哪些现在尚未结交的用户“应该是朋友”，并将此结果作为“朋友推荐”发送给用户。如果预测足够准确，显然有助于提高相关网站在用户心目中的地位，从而提高用户对该网站的忠诚度。另外，链路预测的思想和方法，还可以用于在已知部分节点类型的网络(partiallylabelednetworks)中预测未标签节点的类型，如用于判断一篇学术论文的类型[17]或者判断一个手机用户是否产生了切换运营商(如从移动到联通)的念头[18]。另外文献[10]所提出的对网络中的错误链接的预测，对于网络重组和结构功能优化也有重要的应用价值，如在很多构建生物网络的实验中存在暧昧不清甚至自相矛盾的数据[19]，就有可能应用链路预测的方法对其进行纠正。链路预测研究不仅具有广泛的实际应用价值，也具有重要的理论研究意义，特别是对一些相关领域理论方面的推动和贡献。近年来，随着网络科学的快速发展，其理论上的成果为链路预测搭建了一个研究的平台，使得链路预测的研究与网络的结构与演化紧密联系起来。因此，对于预测的结果更能够从理论的角度进行解释。与此同时，链路预测的研究也可以从理论上帮助人们认识复杂网络演化的机制。针对同一个或者同一类网络，很多模型都提供了可能的网络演化机制[20-21]。由于刻画网络结构特征的统计量非常多，很难比较不同的机制孰优孰劣。链路预测机制有望为演化网络提供一个简单统一且较为公平的比较平台，从而大大推动复杂网络演化模型的理论研究。另外，如何刻画网络中节点的相似性也是一个重大的理论问题[22]，该问题和网络聚类等应用息息相关[23]。类似，相似性的度量指标数不胜数，只有能够快速准确地评估某种相似性定义是否能够很好地刻画一个给定网络节点间的关系，才能进一步研究网络特征对相似性指标选择的影响，因此，链路预测可以起到核心技术的作用。链路预测问题本身也带来了有趣且有重要价值的理论问题，就是通过构造网络系综(networkensemble)，并借此利用最大似然估计方法进行链路预测的可能性和可行性研究，对链路预测本身以及复杂网络研究的理论基础的建立和完善起到推动和借鉴作用。1问题描述与评价方法定义(,)GVE为一个无向网络，其中V为节点集合，E为边集合。网络总的节点数为N，边数为M。该网络共有(1)/2NN-个节点对，即全集U。给定一种链路预测的方法，对每对没有连边的节点对(x,y)(\UEÎ)赋予一个分数值Sxy，然后将所有未连接的节点对按照该分数值从大到小排序，排在最前面的节点对出现连边的概率最大。为了测试算法的准确性，将已知的连边E分为训练集ET和测试集EP两部分。在计算分数值时只能使用测试集中的信息。显然，TPEEE=U，且TEIPE=Æ。在此，将属于U但不属于E的边定义为不第5期吕琳媛:复杂网络链路预测653存在的边。衡量链路预测算法精确度的指标有AUC、Precision和RankingScore共3种。它们对预测精确度衡量的侧重点不同：AUC(areaunderthereceiveroperatingcharacteristiccurve)从整体上衡量算法的精确度[24]；Precision只考虑对排在前L位的边是否预测准确[25]；而RankingScore更多考虑对所预测的边的排序[26]。AUC可以理解为在测试集中的边的分数值有比随机选择的一个不存在的边的分数值高的概率，也就是说，每次随机从测试集中选取一条边与随机选择的不存在的边进行比较，如果测试集中的边的分数值大于不存在的边的分数值，就加1分；如果两个分数值相等，就加0.5分。独立地比较n次，如果有n¢次测试集中的边的分数值大于不存在的边的分数，有n¢¢次两分数值相等，则AUC定义为：0.5AUCnnn¢¢¢+=显然，如果所有分数都是随机产生的，AUC=0.5。因此AUC大于0.5的程度衡量了算法在多大程度上比随机选择的方法精确。Precision定义为在前L个预测边中被预测准确的比例。如果有m个预测准确，即排在前L的边中有m个在测试集中，则Precision定义为：PrecisionmL=显然，Precision越大预测越准确。如果两个算法AUC相同，而算法1的Precision大于算法2，说明算法1更好，因为其倾