Research On Complex Network Link Prediction Algorithm Based On Information Entropy

Link prediction,as one branch of data mining,has raised concerns in various fields because of its significance and potential applications.Link prediction is to estimate the existence possibility of links between disconnected nodes based on the network structures and node attributes.Recently,with the rapid development of complex network theory,topology-based link prediction algorithms have been the research focus.The main contributions of this thesis are as follows:Firstly,we give descriptions of complex networks,including statistical properties and models of single-layer networks,weighted networks and multiplex networks respectively.Secondly,we show the background and recent progress about link prediction and the existing typical algorithms;Thirdly,we analyze and introduce entropy of a path,and propose a new similarity index,namely Path Entropy(PE)index.Empirical experiments demonstrate that PE index outperforms the mainstream of link predictors.Then,we further quantify the contribution of a path with both path entropy and path weight,and propose a weighted prediction index,namely Weighted Path Entropy(WPE).Empirical experiments show that WPE achieves higher prediction accuracy than existing weighted indices.We consider the heterogeneity of link in networks,discuss link prediction problem in multiplex networks,and provide a feasible prediction model in multiplex network based on path entropy.Finally,to evaluate link prediction methods in very large complex networks,we focus on hot areas of networks and propose a fast algorithm based on the parallel computing scheme to obtain all node pairs with CN values larger than the lower bound.Furthermore,we propose a general measurement,called self-predictability,to quantify the performance of similarity indices in link prediction,which can also indicate the link predictability of networks with respect to given similarity indices.