Link Prediction Based On Local Structure Similarity

Network is a significant tool for studying real-world complex systems.Social,transportation,biological and economic systems,can be represented by networks.Link prediction aims to find missing or future connections in networks.It is applied in guiding biological experiment,recommending friends in social networks and many other fields.The mainstream method of link prediction is based on structure similarity duo to the topology information of networks is easy to obtain.Recently,methods based on graph embedding have been studied broadly.We proposed a link prediction index based on local structural similarity,and apply the similarity index to a graph embedding method.The main research contents are as follows:(1)Defined the local structure centrality of nodes,which regards the structure feature as the node's degree divided by the sum of its neighbors' degree.Local centrality considers the contribution of neighbor nodes compared to degree centrality.The local centrality index of two nodes is normalized and substituted into the entropy calculation formula to calculate the structure similarity between the nodes.And distance between two nodes is used as the penalty factor to obtain the link prediction index named LC(Local Centrality).Then test and compare the AUC(Area Under the ROC Curve)of 13 link prediction indices on a data set of 548 networks.The results show that the proposed index is better than the common-neighbor-based indices when the network has small average distance,but not as good as Katz and other global similarity indices.As the network average distance increases,our index approaches the optimal performance,and its time complexity is greatly reduced compared to the Katz index.(2)Proposed a graph embedding method named LCE(Local Centrality Embedding)with applying the structural similarity of nodes.Node2 vec and some other graph embedding methods use random walks to generate similar nodes sequences.Based on this,we apply structural similarity in the random walk process for selecting nodes.Preferentially select neighbor nodes with similar structure to the current node as next choice.The sampled node sequences is input into the Woed2 vec model as a corpus to obtain the low-dimensional vector representations of nodes.The Euclidean distance of vectors is used to calculate the similarity scores of nodes.Compared the AUC performance of LCE algorithm with other 5 methods on 548 networks.The results show that on networks with average network distance less than 3,the performance of LCE is not as good as other methods,but on networks with average distance greater than 3,the LCE algorithm achieves the best performance.(3)Proposed a method to select an appropriate link prediction index for a given network.Link prediction indices can be divided into different types according to the characteristics they used.The upper bound or lower bound of AUC of same class of indices are the same.Therefore,as long as the upper bound of AUC is calculated,it can be judged whether to select this kind of index.In addition,if the AUC lower bound of the index is extremely low,a machine learning model can be used to predict the type of edges,which can obtain better performance.