Research On Link Prediction Problem In Online Social Network

Enhancing the accuracy of link prediction is one of the fundamental issues in complex network research.Link prediction refers to how to predict the possibility of a connection between two nodes in a network that have not yet generated a connected edge through information such as a known network structure.The traditional link prediction algorithm is based on a single similarity index,including local information similarity index,global information similarity index and random walk based similarity index,so that the comprehensive information of these similarity indicators is not fully utilized.Based on the link prediction based on node similarity,this thesis propose the XGBoost algorithm and sim2 vec algorithm by comprehensively utilizing the node similarity index and some high-order features.The main research contents include:1.Research on link prediction algorithm based on single similarity index.Based on local information similarity,global information similarity and random walk based similarity index,experiments were conducted on Facebook,and the accuracy based on single similarity index was given.2.Research on link prediction algorithm based on XGBoost.This thesis regards the link prediction problem as the binary classification in machine learning,proposed the link predition base on XGBoost algorithm,we denote the label of linked sample as one,otherwise zero,then choose similarity indicators based on local information,global information and random walk similarity as input feature,considering these information comprehensively,and using AUC as model evaluation criterion.,then we make experiments on facebook datasets with XGBoost algorithm,the result shows that the AUC of this algorithm is higher that the AUC of link prediction based on similarity.3.Research on link prediction algorithm based on sim2 vec.Different from the node2 vec algorithm directly embedding the node,this thesis first calculates the node similarity index,then embedding the node similarity index,and finally uses the deep neural network to train the model,proposes the link prediction algorithm based on sim2 vec,and compared with link prediction based on single similarity index.Experiments on the Facebook dataset show that the prediction algorithm based on sim2 vec has better prediction effect.