一种融合社区关系及共同邻居社区信息的链路预测算法

Link prediction algorithm combining with community relations and community information of common neighbors

共同邻居的相似性指标因其只利用了网络的局部信息使得预测效果不理想,而网络的社区信息包含了节点的网络结构特征,有助于提高链路预测算法的准确性。为了提升预测精度,引入社区结构信息,提出了一种融合社区关系和共同邻居的社区信息的链路预测算法。算法首先采用DeepWalk和Node2vec图嵌入算法进行社区划分,即利用深度学习模型Skip-Gram训练得到的短随机游走节点序列的节点嵌入向量来划分社区,从而获得包含更多网络拓扑信息的高质量社区;然后,通过定义社区间的边关系提出了社区的相似性模型;最后,结合节点的相似性、节点所处社区的相似性、节点共同邻居的社区信息三者来度量两个未知节点的链接概率。实验在USAir等6个不同领域的真实网络上进行,与CN指标等4组基线相比,AUC指标最高提升了2.3%,表明社区结构信息对提升链路预测的效果起着重要的作用。

The performance of CN-based similarity index is not satisfied due to only taking into account the local information of a network. The community information contains the network structure features of nodes, which can be adopted to improve the prediction accuracy. Therefore, a community-based link prediction algorithm using the community structure information is proposed to address the problem. Employing community relations and community information of common neighbors, it was developed in an attempt to improve the prediction precision. Firstly, two graph embedding methods--DeepWalk and Node2 vec were employed, that is, a deep learning model, i.e. Skip-Gram was adopted to train the nodes’ sequences generated from short random walk and then the acquired embedding vectors of nodes were used in communities division to obtain high quality communities that contain more network topology information. Then, the similarity model of communities was proposed via defining the edge relationship between communities. Finally, the similarity of nodes, the similarity between the communities where the nodes are located, and the community information of the nodes’ common neighbors were integrated into the suggested algorithm to evaluate the link probability of two unknown nodes. Finally, experiments on six real-world networks like USAir are conducted, and the AUC of the suggested method is increased about 2.3% at most compared with four benchmark algorithms including CN. Thus it shows that community structure information plays an important role when predicting the latent links.