Abstract:

Link prediction is a crucial problem in social network analysis. Most of the traditional link prediction methods find the missing links or predict the future links merely based on astatic structure of a network, ignoring its dynamics. In order to utilize the dynamic information of the network better and achieve a more preferable result, in this paper, a method with consideration of the network evolution is proposed. A machine learning technique is used to model the change of the structural characteristics in networks. A classifier is trained for each structural feature and a final ensemble result is obtained by weighting all the classifiers. The experimental results in three real collaboration networks show that the proposed method outperforms the traditional static link prediction method and a related dynamic link prediction method, which demonstrates that the results of link prediction are much facilitated with the dynamic information of the network. Moreover, the experimental result also shows that different structural characteristics have different abilities to describe the network dynamics.

Key words: link prediction, machine learning, dynamic network, social network analysis, ensemble learning, supervised learning

摘要： 链接预测是社会网络分析领域的关键问题。传统的链接预测方法大多针对社会网络的静态结构预测隐含的链接或者将来可能产生的链接，而忽视了网络在动态演变过程中的潜在信息。为了能更好地利用网络演变的动态信息，从而取得更好的链接预测效果，提出了一种基于网络结构演变规律的链接预测方法。该方法使用机器学习技术对网络结构特征的动态变化信息进行训练，学习每种结构特征的变化并得到一个分类器，为每个分类器加权得到最终集成的结果。在三个现实的合著者网络数据集上的实验结果表明，该方法的性能要高于静态链接预测方法和一个相关的动态链接预测方法。这说明，网络结构演变信息有助于提高链接预测效果。此外，实验还表明，不同的结构特征对网络动态变化的刻画能力也有所差别。

关键词: 链接预测, 机器学习, 动态网络, 社会网络分析, 集成学习, 监督学习