杂网络链路预测.pdf

第39卷第5期 电子科技大学学报 Vbl．39NO．5 of Electronic 2010年9月 Journal of Scienceand ofChina University Technology Sep．2010 复杂网络链路预测 吕琳媛 (弗里堡大学物理系瑞士弗里堡 CH．1700) 【摘要】网络中的链路预测是指如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生连接的可 能性．预测那些已经存在但尚未被发现的连接实际上是一种数据挖掘的过程，而对于未来可能产生的连边的预测则与网络的 演化相关．传统的方法是基于马尔科夫链或者机器学习的，往往考虑节点的属性特征。该类方法虽然能够得到较高的预测精 度，但是由于计算的复杂度以及非普适性的参数使其应用范围受到限制。另一类方法是基于网络结构的最大似然估计，该类 方法也有计算复杂度高的问题。相比上述两种方法，基于网络结构相似性的方法更加简单。通过在多个实际网络中的实验发 现，基于相似性的方法能够得到很好的预测效果，并且网络的拓扑结构性质能够帮助选择合适的相似性指标．该文综述并比 较了若干有代表性的链路预测方法，展望了若干重要的开放性问题。 关键词复杂网络；链路预测；最大似然估计；概率模型：相似性指标 中图分类号TP391 文献标识码A doi：10．3969a．issn．1001．0548．2010．05．002 LinkPredictionon Networks Complex LO Lin-yuan Switzerland (DepartmentofPhysics，UniversityofFribourg CH·1700) Fribourg of AbstractLink aimsat the1ikelihoodoftheexistencelinksbetweennodes．The predictionestimating ofexistentunknownlinksissimilartothedata the offuturelinks predicting yet miningprocess．whilepredicting relatestothenetworkevolution．ThetraditionalmethodsarebasedonMarkovChainsandmachine which leaming involvethenodeattributes thesemethodscan usually information．Although givegoodprediction，thehigh limitstheir in basedonmaximum computationalcomplexity applicationslarge—scalesyrstems．Theapproaches Ilkelihpod alsoSUf诧rthis