Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (15): 153-161.DOI: 10.3778/j.issn.1002-8331.1905-0271

Previous Articles     Next Articles

Research on Link Prediction Method Based on Deep Non-negative Matrix Factorization

CAI Fei, ZHANG Xin, MU Xiaohui, CHEN Jie, CAI Xun   

  1. 1.College of Surveying and Geo-Informatics, Shandong Jianzhu University, Jinan 250101, China
    2.College of Computer Science and Technology, Shandong University, Jinan 250101, China
  • Online:2020-08-01 Published:2020-07-30

深度非负矩阵分解的链路预测方法研究

蔡菲,张鑫,牟晓慧,陈杰,蔡珣   

  1. 1.山东建筑大学 测绘地理信息学院,济南 250101
    2.山东大学 计算机科学与技术学院,济南 250101

Abstract:

Link prediction is predicting latent edges or unknown edge according to the existing network structure information and it has become one of the hot topics in complex networks. Traditional non-negative matrix factorization has been used in link prediction directly projects the original network into the latent space. However, non-negative matrix factorization can not fully characterize the deep latent structure information of complex networks. As a result, the prediction ability in sparse networks is limited. Aiming at the above problems, this paper proposes link prediction method based on Deep Non-negative Matrix Factorization(DNMF). DNMF forms a multi-level network structure learning model through the multiple factorization of the coefficient matrix. By multiple factorization of the coefficient matrix, the objective function of deep latent feature model can be obtained. Pre-decomposition results are obtained by layer decomposition and then the training parameters can be adjusted as a whole. The similarity matrix can be obtained by the different basis matrices and coefficients matrix. DNMF method can guarantee the expression of deep structure of the real network information, at the same time, it can get much richer and more comprehensive network structure information. Experiments on ten typical real networks show that the proposed method has competitive performances than state-of-the-art link prediction methods.

Key words: complex networks, deep non-negative matrix factorization, link prediction, latent feature

摘要:

链路预测是根据现有的网络结构信息预测潜在的边,其已成为复杂网络中的热点之一。在链路预测中,传统非负矩阵分解直接将原始网络映射到隐空间中,不能充分挖掘复杂网络的深层隐结构信息,导致在稀疏网络中预测能力有限。针对以上问题,提出一种基于深度非负矩阵分解的链路预测方法(Deep Non-negative Matrix Factorization,DNMF)。通过对系数矩阵多次分解,得到一组基矩阵和一个系数矩阵相乘,进而构建深度隐特征模型的目标函数。采用两阶段法去调整训练参数,即在预训练阶段通过逐层分解作为预分解结果,在微调阶段整体微调训练参数。根据微调训练后的基矩阵和系数矩阵,计算网络相似矩阵。该方法可以在保证真实网络的深层隐结构信息表达的同时使其可以获得更加全面的网络结构信息。通过对10个典型实际网络进行实验,表明该方法比现有经典链路预测方法具有更好的预测性能。

关键词: 复杂网络, 深度非负矩阵分解, 链路预测, 隐特征