Research On Link Prediction Algorithm Based On Non-negative Matrix Factorization And Its Application

Link prediction is the most effective tool to study the prediction and restoration of missing links in complex networks.Link prediction aims to find the missing and future links between two unconnected nodes according to the known network node or structure information(such as node attributes,node clustering,link weight,local and global structure information,etc.).Link prediction includes three aspects:first,it can predict the missing links in the network;second,it can analyze the evolution of the network,namely,it can predict the possible future links in the network;finally,it can identify spurious links and eliminate random noise.Therefore,link prediction has not only great theoretical value but also extensive application value.In the past decade,a large number of link prediction algorithms based on differ-ent theories have been proposed to perform link prediction tasks on different types of networks and achieve better performance.However,link prediction still encounters the following challenges:first,the real world undirected and unweighted network data always encounter the challenges of high-dimensional,sparse,spurious links and random noise,and the existing methods can not deal with these problems at the same time;Secondly,almost all of the existing weighted network link prediction methods only consider the strength of the link weight and ignore the network weighted topol-ogy information;in addition,the existing directed network link prediction algorithms only consider the strength of the link direction and ignore the local and global topol-ogy information;Finally,the potential structure of the real world network is always complex such as multi-layer,while most of the existing methods only consider the shallow structure information of the network.Based on the above analysis,this thesis proposes the related methods to solve the above problems by using nonnegative matrix factorization and extended framework.The main contributions of this thesis are listed as follows:First,in undirected unweighted networks,the existing methods cannot simulta-neously deal with high-dimensional,sparseness,spurious links and random noise,a link prediction algorithm based on robust nonnegative matrix factorization via man-ifold regularization and sparse learning is proposed.The local similarity and global clustering information are calculated by the hot kernel function and k-medoids algo-rithm respectively.Then,map the adjacency matrix and the local similarity matrix to the low-dimensional latent space through robust nonnegative matrix factorization,and use the?_2,1norm constraint factor matrix to identify spurious links.Comparing ten real undirected unweighted networks with local similarity,nonnegative matrix factorization prediction algorithm and network embedding method,the results show that the performance of our method is significantly improved in predicting missing links,identifying false links,eliminating random noise and robustness.Secondly,weight link and network topology are two important features of weighted network link prediction.This paper fuses the above two types of infor-mation and proposes a link prediction model based on graph regularized weighted nonnegative matrix factorization.In this paper,the weighted nonnegative matrix de-composition is applied to link prediction for the first time.The adjacency matrix of weighted network is mapped to the potential space of low dimension,and the weighted cosine similarity is used to obtain the network local structure similarity,which is combined with the graph regularization to maintain the local information.Compared with the link prediction algorithm based on the weighted structure simi-larity and the existing nonnegative matrix decomposition prediction algorithm on the eight weighted networks,the experimental results show that the proposed method has high quality performance in predicting missing links,weight prediction and robust-ness.Then,in directed networks,most of the existing link prediction algorithms only consider the link direction information and ignore the network local and global infor-mation,a link prediction algorithm based on nonnegative matrix factorization via node influence and asymmetric link clustering coefficient is proposed.The model uses the asymmetric link clustering coefficient method to calculate the link direction cluster-ing coefficient between nodes to maintain local structural information,and uses the PageRank algorithm to calculate the influence information of each node of the net-work to maintain global structural information.Then,these two types of information are combined with nonnegative matrix factorization to form a unified link prediction model.Comparing 9 indicators based on directed local similarity and nonnegative matrix factorization prediction algorithm on 10 real directed networks respectively,the results show that the model obtains higher prediction accuracy.Finally,all existing link prediction algorithms based on nonnegative matrix de-composition are shallow models,a link prediction algorithm fused structure and sparsity-constrained via deep nonnegative matrix factorization is proposed.The model uses the common neighbor method to calculate the network structure similarity,and maps adjacency matrix to the low-dimensional latent space through deep nonneg-ative matrix factorization to effectively capture the observable link and the hidden layer structure information.Since each hidden layer may contain random noise from the decomposition process,the?_2,1norm is used to constrain the factor matrix of each hidden layer to eliminate random noise and uncorrelated features.Finally,a unified link prediction model is formed by integrating the topology and sparse constraint in-formation and the deep nonnegative matrix factorization model.Compared with a total of 14 indicators based on classic algorithms based on non-network embedding and network embedding on 8 multi-layer networks,the results show that the method proposed in this paper achieves high-quality performance with a small number of iterations.