基于拓扑相似性的动态网络链路预测方法

摘要

复杂网络作为建模分析复杂系统的有效工具，正吸引着众多学者的研究兴趣，真实世界的复杂系统通常随着时间不断演化改变，而本文研究的动态网络恰好能够合理刻画这种动态特性。对动态网络将来某时刻边的预测，即动态网络链路预测问题，在诸如在线产品推荐、社交网络好友推荐或生物分子功能交互检测等领域中具有极大的应用背景和实用价值。
　　目前，大部分链路预测工作都集中在静态网络上，其中基于共同邻居(Common Neighbor, CN)相似性的链路预测方法最为人们熟知，由于其计算简单且时间复杂度低，还经常被扩展到动态网络链路预测上，如CN-last和CN-all方法，然而这两种方法忽略了动态网络中边的时序性这个重要信息，使得其预测准确性不够理想。本文给出了广义共同邻居(Generalized Common Neighbor, GCN)的定义，用来计算两个顶点在动态网络中广义上的共同邻居个数，结合边的时序性，给出了三种基于广义共同邻居的相似性计算方法，包含GCN-E, GCN-L和GCN-IL，基于广义共同邻居相似性，提出了一个动态网络链路预测的方法，这种方法保留了共同邻居复杂度低的特点，同时有效利用了动态网络的时序性信息，可以提高预测准确性。
　　本文在人工合成数据和真实网络数据上，对提出的动态网络链路预测方法进行了实验研究。实验结果表明，本文提出的GCN-E、GCN-L和GCN-IL三种方法得到的预测准确度相差不大。而与CN-last和CN-all方法相比时，预测效果有明显提升，如GCN-E在所有实验的三个数据集上都能取得最高的预测准确度。