Abstract: Link prediction, which aims at recommending potential links between network nodes, is an important step to understand and study the characteristics of social networks. With the development of social networks, many networks contain rich node attributes. This paper focuses on using both network structure and node attributes to predict links. Based on the assumption that two nodes in the network may be connected because they are close in the network, or may be linked for they have similar attributes, a new random walk model for link prediction by combining network structure and node attributes is proposed. First, two different graphs and transition matrices are created for new iteration rule. Second, the model is simplified for calculation and then a fast approximation algorithm is presented. The experiment on two standard datasets reveals that this method has better performance compared with other similar methods. Meanwhile, the effect of the probability of particle walking on different graphs is analyzed and it shows that node attributes can promote the prediction ability effectively.

Key words: link prediction, social network, random walk, network structure, node attribute

摘要： 链接预测旨在推荐网络中潜在的链接，是理解和研究社会网络特征的重要一步。随着社会网络的发展，许多网络中包含了大量的节点属性信息。研究集中在结合网络结构和节点属性信息来进行链接预测。网络中的两个节点既可能因为结构上相邻形成新链接，也可能因为属性相似产生联系，基于此假设提出了一种新的融合网络结构和节点属性的随机游走模型用于链接预测。首先建立了两个不同的网络图以及转移概率矩阵用于新的迭代规则，而后再简化该模型用于计算并提出了一种近似的快速算法。在两个标准数据集上进行的实验表明该方法较同类方法有明显的效果提升，同时进一步分析了随机游走粒子在两个网络图中游走的概率对预测结果的影响，分析结果显示节点属性可有效提高模型的预测能力。

关键词: 链接预测, 社会网络, 随机游走, 网络结构, 节点属性