基于链路预测和零模型的演化网络结构分析

Our project combines link prediction algorithms, null models and time series analysis to analyse the evolving network structure of real world systems. Networks of real world systems are directed, and have an evolving structure which consistently features a quantity of isolated nodes. In addition, many engineering networks include tree-like substructures. However, despite the prevalence of these features, the majority of traditional link prediction and null model algorithms ignore structural evolution, isolated nodes and tree-like structures. In addition, most established link prediction algorithms neglect the role of link directions. Because they exclude fundamental properties of networks, many previous studies of link prediction and null models lack physical meaning. In contrast, in our project we aim not only to study static network structures, but also to harness link prediction algorithms, null models and the time series analysis to understand the evolving network structures of real world systems. We will apply our results to enhance and optimise link prediction techniques, and develop improved network models. Our project has both theoretical significance and wide applicability. By revealing the principles underlying the evolution of network structures, our project can lead to refined link prediction algorithms and network models, which we will apply to real world systems.structures of real world systems. We will apply our results to enhance and optimise link prediction techniques, and develop improved network models. Our project has both theoretical significance and wide applicability. By revealing the principles underlying the evolution of network structures, our project can lead to refined link prediction algorithms and network models, which we will apply to real world systems.

本课题将以链路预测、零模型和时间序列为工具，对现实世界系统中网络结构的演化特性展开深入研究。现实世界系统中的网络通常都存在一定数量的孤立节点，且网络结构具有演化特性和方向特性，部分工程网络还包含大量的树型结构。然而，大部分传统的链路预测算法和零模型构造算法均忽略了网络演化问题、孤立节点问题和树型结构问题，几乎所有的链路预测算法都未考虑连边方向的作用，从而缺乏一定的物理意义。因此，本课题的特色在于不单纯地进行传统静态网络的结构分析，而是结合链路预测算法、零模型构造算法和时间序列分析来研究现实世界系统中网络结构的演化特性，并补充完善链路预测问题。本课题具有广泛的应用前景和重要的理论意义，不仅能够将链路预测算法和网络生成模型更好地应用于实践，提高预测的准确性及模型的适配性；还可以揭示现实世界系统中网络结构的演化原理，进而完善链路预测算法和网络生成模型理论。

链路预测的技术原理最早源起于应用数学，而后进入社会学、统计物理、计算机和网络科学领域，并随着人工智能的兴盛而成为研究热点。从网络科学的视角来看，链路预测是通过已观测到的网络结构信息来预测节点对之间的不确定关系。在传统的研究中，人们往往关注的是常规网络的静态结构，而忽视了具有特殊结构的稀疏网络和动态演化网络的链路预测问题。本项目主要针对类树状网络(一种典型的稀疏网络)和具有时变特征的演化网络进行了研究，首先分析了推特上的社交数据、自来水管道数据及性关系数据等稀疏网络数据，提出了针对类树状网络的高精度算法，并使用基础零模型（网络子图）分析了算法的稳定性，使用扰乱网络同配特性的零模型分析了算法的普适性。在此基础上，本项目提出了能够同时生成类树状和社团结构的网络增长模型，并很好地适配了SARS-Cov-2单倍型进化网络。本项目分析了具有显著时效特征的学术网络，包括科学家合作网络及基金项目合作网络，此类网络的节点会动态增减。针对会产生新节点的演化网络，本项目提出了比传统方法预测精度更高的链路预测算法，并发现越相似的基金项目越有可能联合资助同一项目。最后，我们发现稀疏网络中还存在着一种特殊的局部结构--长路径或者环状结构，即有很多度小的节点会组成一条步数很大的路径，并进一步研究了此类网络的链路预测算法。