Research On Relationship Recommander Systerms Based On Link Prediction

Relationship recommendation is a sub-research field of information recommendation, especially focus on person to person recommendation of social networks. With the development of Facebook, Twitter, Sina weibo, Renren, the relationship between people in the social network is the most important feature for these online platforms. How to recommend the fit people to the others based on the converged different research field is the new challenged direction for all researchers.Link prediction, which is to predict and estimate the unknown or missing link through the node information or network structure, is the most important problem for graph mining. Social network is a specific kind of complex network, but there are many different attributes of social network, such as social behavior or some social characters. The main contribution of this paper is to setup the framework of person to person recommendation based on the graph model, which is always to be used to describe the whole networks. The node social attributes such as gender, personal historical relationship, personal actions are included for the link prediction, as well as the whole social network structure. All the link prediction are developed based on the ERGM/P*(Exponential Random Graph Models, ERGM) models, which is to model and estimate the coefficients of the whole real network, and then use the estimated coefficients and configurations to predict links and recommend the relationships.The main research work and contributions of the paper are listed as followed:(1) The link perdition method based ERGM were introduced to the person to person recommendation system. The ERGM method was usually to describe the network structure. We found the maximum likelihood estimation algorithm based on MCMC sample used to estimate ERGM coefficients was essentially to generate the Markov chain according to transition probability. After estimating the best coefficients η, we can use it to get the link probability rank of the unconnected nodes in the whole network. The recommendation of different people was based on the link probability rank.(2) The great advantage of ERGM for link prediction is not only the whole network description, but also the node attributes included. Compared with the other link prediction method, such as local information method, topology method etc, the ERGM method can give more accuracy result. We collect the real scientist collaboration network data and design the experiment to prove this method is more feasible not only on the theory, but also on the practices. The reasonable configurations of network and the optimal coefficients in ERGM are most important for precise result.(3) There are lots of configurations in the ERGM theoretical framework. The other innovation of our work is to test some new configurations according to the different network, such as gwesp\gwdsp, which are high order structure configurations to describe the details of network. The comparison experiments were carried out based on the scientist collaboration network and the small clique of WEIBO. It proved that we can use the same parameters to simulate the same property social networks; this was called paralleled transition of parameters for different network. The big trouble of ERGM put into the practice is the computation complexity. We can use to the paralleled transition to resolve this problem.(4) The ERGM method is based on the input observed network to get the configurations and coefficients. Because the real social networks are always dynamic, the configurations and coefficients based on observed network can not predict all of the future. We design the experiments to test and resolve this problem. We called this missing link prediction, which is to delete one link of the current networks each time (the test missing link included two and twenty links), and then calculate the accuracy rate of predicting the missing links. As a result, with the increase of missing link, the accuracy of the prediction was dropping down. This will give the significent reference to the application of ERGM in the dynamic network.(5) After the theoretical and experimental research, we use the ERGM link prediction approach to person to person recommendation on Sina WEIBO platform. We fetched the real WEIBO data to test the efficiency of this method. We first used the closed community data to do the recommendation in the small clique. And then we used the ERGM method to predict the potential links in the whole network, but the segmentation of community should be done firstly.The recommendation system based on ERGM link prediction approach can use any attribute of network and nodes to predict links. The research work proved that it is more efficiency than other trational prediction methods.