基于信息论的复杂网络链路预测研究

Link prediction based on network structure is a new research area in the field of data mining. Although some new algorithms have been proposed, the basic theory is still missing. In this project, we will use the information theory to study the theory and algorithms of link prediction and related network predictability. First, this project will use the information theory as the tool to find the effect of network structure on link prediction. A theoretic framework will be built to help us understand how the information of network structure can be used to make a better prediction. Second, based on such a theoretic framework, traditional link prediction algorithms will be revisited. And some new algorithms will be then proposed based on the information theory. Thirdly, the link predictability will also be studied in the framework of information theory. Some parameters will be defined to measure the predictability of networks. In summary, this project aims to build a more complete theory for link prediction in complex networks. It will find theoretic and practical applications in the era of big data.

基于网络结构特性的链路预测作为数据挖掘领域的研究方向之一，已有一定的研究成果，然而在理论基础方面仍显薄弱。本项目拟结合信息论这一理论工具，研究链路预测相关的理论、算法以及网络的可预测性问题。首先，本项目拟从信息论的角度出发，重新思考网络结构在链路预测中的作用，形成基于信息论的链路预测理论框架，从理论上帮助我们更加深刻地认识链路预测效果与网络结构之间的关系。其次，我们将采用上述框架分析比较现有的典型链路预测算法，从信息量的角度对现有算法设计进行总结；在此基础上，在信息论框架下设计出效果更好的预测算法。第三，我们将从信息论的角度考虑网络的可预测性指标，给出衡量网络可预测性的具体参数，揭示网络结构与网络可预测性之间的关系。本项目旨在为链路预测建立比较完善的理论框架。在大数据技术迅猛发展的背景下，本项目的研究具有重要的理论意义和实际应用价值。

链路预测技术可以帮助我们寻找网络中实际存在但还未发现、或目前不存在但未来极有可能出现的连边。为了更加系统有效地进行链路预测，本项目将链路预测问题和信息论中信息量的定义进行比较，找出它们的相似之处，从而将链路预测算法的设计问题转化为信息量的计算问题，得到基于信息论的链路预测框架。此框架具有较强的普适性，它既可用于已知一种网络结构信息的情况，也可用于已知多种结构信息的情况；既可用于无权网络，也可用于加权网络。而且，由于引入了信息论这一理论工具，从理论层面保证了这一类链路预测算法的有效性。在此框架的指导下，我们针对不同的应用场景及不同的已知网络结构信息，设计了相应的链路预测算法，并通过和经典预测算法的比较验证了它们的性能。在分析链路预测性能的过程中，我们发现同一个算法在不同的网络中可能会表现出很不相同的性能。由此出发，我们探讨了复杂网络结构对网络性能的影响。针对不同链路预测算法用到的网络结构信息不同，我们分析比较了采用二阶信息和采用三阶信息的算法在不同簇系数网络中的预测效果，展示了网络结构对预测性能的影响。针对网络中不同连边所表现出的重要性不同，我们提出了一种新的连边重要度评价指标。此外，我们还考虑不同的实际网络和不同的应用场景，研究了网络结构对网络鲁棒性的影响。通过本项目的资助，课题组共发表论文14篇，培养毕业研究生3名。项目负责人及参与项目的研究生多次参加国内国际相关学术会议并做口头报告，与国内外同行交流紧密，取得了一定的学术影响力。