The Research Of Link Prediction Algorithm Based On Matrix Completion

In recent years,with the rapid development of Web2.0 technology and the development of social networks,the analysis of complex networks has become an important research task for researchers.The link prediction problem of complex networks as a research direction of complex network analysis,in the aspect of social networks,biological information network,food network and other closely related to human life has important application value.Therefore,this paper studies the problem of link prediction.Link prediction plays a very important role in data mining,which aims to estimate the possibility of the existence of links between two unconnected nodes according to the information of network structure.As an important part of data mining,link prediction has been studied for many years.It is divided into two types: one predicts unknown links;another predicts future links.The first is devoted to the discovery of a link that should be present but not discovered,and the second is dedicated to predicting links that are not present in the existing network but may occur in the future.This paper focuses on predicting unknown links.The existing link prediction algorithms can be divided into four categories: 1.the topological structure based;2.social theory based;3.machine learning based;4.matrix analysis based.This paper studied the first and fourth method.Put forward the following points:1.In this paper,we propose a new similarity measure method,which is the improvement of link prediction algorithm based on topology structure and combines CN algorithm and RA algorithm together,called CN-RA.This method fully consider the influence of the number of common neighbors in the social network and a single common neighbor node to node similarity.Compared with CN algorithm,RA algorithm and other benchmark topology based algorithm,CN-RA algorithm obtains a better prediction effect.2.In this paper,we propose a multi feature fusion based link prediction framework.Inspired by the original link prediction method based on matrix completion,we deeply study the Augmented Lagrange Multiplier method--ALM.We use adjacency matrix to represent social network.Because of the low rank of social network adjacency matrix,we use the augmented Lagrange multiplier method to optimize the adjacency matrix,and then solve the link prediction problem.Based on this method,this paper presents a multi feature fusion based link prediction framework,which combines the features of topology and low rank.The experimental results show that the proposed framework can perform better than the traditional topology based method and the ALM algorithm.At the same time,the framework can also be extended,and other features(such as node attribute information,social information)can be involved,and then analyze link prediction problem the dynamic network.This paper did experiments on the above two points,using three real data sets,respectively USAir data set and Net Science data set and Jazz data set,using CN,AA,PA,RA,Jaccard as a benchmark evaluation method,experimental results using the ROC curve and AUC value to evaluate.The experimental results show that the proposed method can achieve the expected results,and the multi feature fusion based link prediction framework can significantly improve the prediction effect.