计算机科学与探索 ›› 2019, Vol. 13 ›› Issue (5): 812-821.DOI: 10.3778/j.issn.1673-9418.1805029

• 网络与信息安全 • 上一篇    下一篇

基于网络表示学习的链路预测算法

杨晓翠+,宋甲秀,张曦煌   

  1. 江南大学 物联网工程学院,江苏 无锡 214122
  • 出版日期:2019-05-01 发布日期:2019-05-08

Link Prediction Algorithm Based on Network Representation Learning

YANG Xiaocui+, SONG Jiaxiu, ZHANG Xihuang   

  1. School of Internet of Things Engineering, Jiangnan University, Wuxi, Jiangsu 214122, China
  • Online:2019-05-01 Published:2019-05-08

摘要: 网络是表达对象之间复杂联系的重要形式,广泛存在。而链路预测作为网络分析的重要方法,具有很大的研究意义和应用价值。传统的链路预测算法普遍是基于邻接矩阵的稀疏表示方案而设计,计算效率低且扩展性差。首先引入网络表示学习的概念,创新性地提出基于几何布朗运动的随机游走算法GbmRw,然后进一步设计出网络表示学习算法GBMLA,实现更具区分能力与表达能力的网络表示,最后以节点表示向量的欧式距离来表征节点之间的相似性,从而预测其链路存在的可能性。不同领域的多个网络中进行反复实验的结果表明,该算法较之于基于原始网络设计的传统算法,预测效果得到了明显的提升,也进一步肯定了网络表示学习对于链路预测工作的重要意义。

关键词: 链路预测, 几何布朗运动, 随机游走算法, 网络表示学习算法

Abstract: The network is an important form of expressing complex relationships between objects and exists extensively. Link prediction, as an important method of network analysis, has great research significance and application value. However, the traditional link prediction algorithms are generally designed based on the sparse representation scheme of the adjacency matrix. Such algorithms often have low computational efficiency and poor scalability. This paper first introduces the concept of network representation learning and innovatively proposes a random walk algorithm called GbmRw based on geometric Brownian motion, then further designs a network representation learning algorithm GBMLA to achieve a more differentiated and expressive representation of network. Finally, the Euclidean distance between the representation vectors of nodes is used to characterize their similarity, so as to predict the likelihood of the link??s existence. The results of repeated experiments in multiple networks from different domains show that compared with the traditional algorithm designed based on the original network, the proposed algorithm has obviously improved the prediction performance, which further confirms the significance of network representation learning for link prediction work.

Key words: link prediction, geometric Brownian motion, random walk algorithm, network representation learning algorithm