复杂网络链路预测

摘要：

网络中的链路预测是指如何通过已知的网络结构等信息预测网络中尚未产生连边的两个节点之间产生连接的可能性.预测那些已经存在但尚未被发现的连接实际上是一种数据挖掘的过程,而对于未来可能产生的连边的预测则与网络的演化相关.传统的方法是基于马尔科夫链或者机器学习的,往往考虑节点的属性特征.该类方法虽然能够得到较高的预测精度,但是由于计算的复杂度以及非普适性的参数使其应用范围受到限制.另一类方法是基于网络结构的最大似然估计,该类方法也有计算复杂度高的问题.相比上述两种方法,基于网络结构相似性的方法更加简单.通过在多个实际网络中的实验发现,基于相似性的方法能够得到很好的预测效果,并且网络的拓扑结构性质能够帮助选择合适的相似性指标.该文综述并比较了若干有代表性的链路预测方法,展望了若干重要的开放性问题.

关键词：复杂网络、链路预测、最大似然估计、概率模型、相似性指标

所属期刊栏目：39

分类号：TP391(计算技术、计算机技术)

资助基金：瑞士国家科学基金200020-121848;国家自然科学基金11075031

在线出版日期：2010-11-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：651-661