复杂网络链路预测.pdf

《复杂网络链路预测.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第39卷第5期电子科技大学学报Vol.39No.52010年9月JournalofUniversityofElectronicScienceandTechnologyofChinaSep.2010复杂网络链路预测吕琳媛(弗里堡大学物理系瑞士弗里堡CH-1700)【摘要】网络中的链路预测是指如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生连接的可能性。预测那些已经存在但尚未被发现的连接实际上是一种数据挖掘的过程，而对于未来可能产生的连边的预测则与网络的演化相关。传统的方法是基于马尔科夫链或者机器学习的，往往考虑节点的属性特征。该类方法虽然能够得到较高的

2、预测精度，但是由于计算的复杂度以及非普适性的参数使其应用范围受到限制。另一类方法是基于网络结构的最大似然估计，该类方法也有计算复杂度高的问题。相比上述两种方法，基于网络结构相似性的方法更加简单。通过在多个实际网络中的实验发现，基于相似性的方法能够得到很好的预测效果，并且网络的拓扑结构性质能够帮助选择合适的相似性指标。该文综述并比较了若干有代表性的链路预测方法，展望了若干重要的开放性问题。关键词复杂网络;链路预测;最大似然估计;概率模型;相似性指标中图分类号TP391文献标识码Adoi:10.3969/j.issn.1001-0548.2010.05.002LinkPre

3、dictiononComplexNetworksLÜLin-yuan(DepartmentofPhysics,UniversityofFribourgFribourgSwitzerlandCH-1700)AbstractLinkpredictionaimsatestimatingthelikelihoodoftheexistenceoflinksbetweennodes.Thepredictingofexistentyetunknownlinksissimilartothedataminingprocess,whilethepredictingoffuturelinks

4、relatestothenetworkevolution.ThetraditionalmethodsarebasedonMarkovChainsandmachinelearningwhichusuallyinvolvethenodeattributesinformation.Althoughthesemethodscangivegoodprediction,thehighcomputationalcomplexitylimitstheirapplicationsinlarge-scalesystems.Theapproachesbasedonmaximumlikelih

5、oodapproximationalsosufferthisshortcoming.Anothergroupofmethodsisbasedonthenodesimilaritythatisdefinedsolelybasedonthenetworkstructure.Extensiveexperimentsonmanyrealnetworksshowthatthesimilarity-basedmethodscangivegoodpredictionwhilewithlowercomputationalcomplexitycomparingwiththeabovetw

6、okindsofmethods.Thisarticleintroducesandcomparesmanyrepresentativelinkpredictionmethods,andoutlinessomeimportantopenproblems,whichmaybevaluableforrelatedresearchdomains.Keywordscomplexnetworks;linkprediction;maximumlikelihoodapproximation;probabilisticmodel;similarityindex网络中的链路预测(linkpr

7、ediction)，既包含了对方法还有很多，如文献[5]利用网络的拓扑结构信息未知链接(existentyetunknownlinks)的预测，也包含以及节点的属性，建立了一个局部的条件概率模型了对未来链接(futurelinks)的预测。链路预测作为数进行预测。文献[6]基于节点的属性定义了节点间的据挖掘领域的研究方向之一在计算机领域已有较深相似性，可以直接用于进行链路预测。虽然应用节入的研究，研究的思路和方法主要基于马尔科夫链点属性等外部信息的确可以得到很好的预测效果，和机器学习。文献[2]应用马尔科夫链进行网络的链但是很多情况下，信