动态多关系网络的链接预测研究

Link prediction in dynamic multi-relational networks is an important topic in complex network analysis. To improve the accuracy and speed of link prediction, many issues must be solved, such as the link model of the network, the method for using its temporal information and the relations between different types of links. In this project, we will study the link model of the dynamic multi-relational networks so as to reflect the dynamic, temporality and the changing of its topology structure of all links types. We will also study the effective methods to combine the attributes informatiom on the nodes with the topological information of all link types, and the methods to merge the topological information of the link types so as to solve the asymmetric problem and to remove the redundancy. To reduce the time and space comlexity of the link prediction algorithm, we will develope a fast algorithm to count the paths with differnent link types in computing the topological simlarity of the node pairs, and an augmentative method for calculating the topological simlarity of the node pairs in the evolution of the networks. Our project will intensify the understanding of the link mechanism of the dynamic multi-relational networks. The results of this project will increase the accuracy and efficiency of the link prediction algorithms, and extend its application scope. The models and algorithms obtained will have theoretical significance, and be important in applications in the areas of social network, biological network and internet analyses.

动态多关系网络的链接预测是复杂网络分析中的重要课题。为了提高链接预测的准确性和速度，对于该网络的链接模型、它的时序信息的处理、各种类型的链接之间的相关关系的处理等许多问题亟待解决。本项目拟研究动态多关系网络的链接模型，以反映其动态性、时序性以及各类链接拓扑变化；研究将顶点属性信息和各类链接的拓扑信息相结合的有效方法，让两种信息均衡地对预测结果产生影响；研究将各类链接的拓扑信息相结合的有效方法，以解决各类链接信息的不对称问题，同时去除冗余的链接类型；研究在对顶点对的拓扑相似度计算中，对多种类型的链接的路径计数问题的快速算法，和网络动态演化过程中顶点对拓扑相似度的增量式计算方法，以降低预测算法的复杂度。本项目的研究成果对深化动态多关系网络链接机制的理解，提高链接预测的精度和效率，扩大其应用范围有着重要的理论意义和应用价值，其模型和算法有利于解决社会网络、生物网络、互联网分析等领域的应用问题。

复杂网络的链接预测可以作为准确分析复杂网络结构的有力辅助工具。在实际应用中，它对一些个体之间未来或潜在的关系作出预测，有着非常重要的意义。在多关系的动态网络的链接预测中，为了提高链接预测的准确性和速度，我们需要解决对该网络的链接描述模型、它的时序信息的处理、各种类型的链接之间的相关关系的处理等许多问题。在本项目中，通过我们在动态多关系网络的链接方面进行的研究工作，提出了描述动态网络进化的模型，提出了在此模型上的动态网络链接预测的快速有效的方法,并对模型应用实际网络数据进行实验验证。我们提出将各类链接的拓扑信息和顶点的属性信息相结合的有效的方法，将它们有机地融合,提高了链接预测的精度。针对具有多类链接的网络，我们提出对指定的类型的链接进行预测的有效方法。提出了动态多关系网络的链接预测算法，该方法利用链接的稀疏性优化对katz指标的计算，利用增量式算法对动态网络预测结果进行更新，能够取得具有更高精确度的预测结果。我们提出了复杂网络链接预测各类新方法，有效降低了算法的复杂度、提高链接预测的精度，如基于蚁群优化的预测方法、基于参数选择的预测算法、基于空间映射思想的预测算法，基于路径抽样的预测方法等。我们还针对二部网络链接预测、对感兴趣的顶点的链接预测等特殊问题提出相应的高效的预测算法。实验结果表明,我们提出的各种链接预测方法可以有效地提高链接预测的质量。我们将本项目的理论成果应用到生物信息学、社会网络分析、网络推荐等应用领域，取得了较好的社会效益和经济效益。我们将复杂网络链接预测算法运用到网络推荐方面，提出了基于二部网络链接预测、基于信息传播、基于时序信息链接预测等各种推荐算法。我们将链接预测的成果应用于生物网络的预测方面，提出了蛋白质相互作用预测、关键蛋白质预测等高效方法，取得了很好的结果。本项目的研究成果有利于解决社会网络、生物网络、互联网分析等领域的应用问题，对于拓展对动态多关系网络链接机制的理解、提高链接预测的精度和效率、扩大其应用范围有着重要的理论意义和应用价值。