复杂网络链路预测

Link Prediction on Complex Networks

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

Link prediction aims at estimating the likelihood of the existence of links between nodes.The predicting of existent yet unknown links is similar to the data mining process,while the predicting of future links relates to the network evolution.The traditional methods are based on Markov Chains and machine learning which usually involve the node attributes information.Although these methods can give good prediction,the high computational complexity limits their applications in large-scale systems.The approaches based on maximum likelihood approximation also suffer this shortcoming.Another group of methods is based on the node similarity that is defined solely based on the network structure.Extensive experiments on many real networks show that the similarity-based methods can give good prediction while with lower computational complexity comparing with the above two kinds of methods.This article introduces and compares many representative link prediction methods,and outlines some important open problems,which may be valuable for related research domains.