The Method And Application Of Link Prediction Based On Similarity

Link Prediction based on the similarity of pair nodes is studied in this thesis,which contains both the prediction for unknown links(are missing or hidden in the recording process)and the future links(are likely to exist in the future).Aim at link prediction method and its application,we present two new local similarity indexes based on node pairs similarity.To consider its predicted function for important links,we apply Link Prediction to the recovery process of a crash in some networks by predicting their important links.At first,we present a new local similarity measure,Local Community Structure(LCS)measure,for link prediction inspired by the community structure in networks.Under the premise of local information on networks,LCS measure characterizes the aggregation relationship between any two nodes and their common neighbors.According to compute and compare the values of AUC for CN?AA?RA and LCS in seven real networks,we find that the accuracy of LCS is better than the other three measures in the networks with big clustering coefficient.On the basis of the construction of the above LCS measure,we define the similarity between two nodes x and y with the help of the tightness between another node y and neighbors of x,then CS measure is proposed.The CS measure combines with ideas and skills of previous measures,the data experiment demonstrates that it can achieve higher predicted accuracy than other measures in most real networks.Link prediction algorithm not only can be utilized to predict the missing links of networks,also can be used to discover hidden links and vital links in the networks.For the study of exploring important links,we focus on the actual background of the power networks.Some special links in the power system networks play a critical role in the restoration process of a large area breakout,which is the primary idea of the proposed network reconfiguration strategy based on the analysis of the abnormal links.We first rank the abnormalities of these tangible links via Link Prediction algorithms,so as to establish a skeleton-network recovery strategy aimed at prioritizing restoring of nodes with high abnormalities.Then we can recover another links according to their significance.The strategy has practical significance,not only can connect the power generator quickly,but also restore important routes timely.