A Comprehensive Comparision Of Network Similarities For Link Prediction And Spurious Link Elimination

Many social,biological,and information systems are naturally described by complex network where nodes represent individuals,proteins,genes,computers and so on,and links denote the relations between nodes.Hence,network analysis has become a crucial focus in many fields including biology,technology and so on.The link prediction problem in complex network has extensive application.For example,the detection of strangers and recommendation of friends in online social network of friends,the prediction of the coauthorships in the scientist network of cooperation and so on.Moreover,the link prediction algorithms can solve the problem of nodes' label classification,discovering the anomalous email and so forth.In recent years,the problem of identifying missing interactions in complex networks has gradually attracted people's attention.Link prediction is realized by estimating the likelihood of the existence of a link between two nodes according to the observed links and nodes,attributes.Similar approaches have also been employed to identify and remove spurious links in networks which is crucial for improving the reliability of network data.In network science,the likelihood for two nodes having a connection strongly depends on their structural similarity.The key to address these two problems thus becomes how to objectively measure the similarity between nodes in networks.In the literature,numerous similarity metrics have been proposed and their accuracy has been discussed independently in previous works.In this paper,we systematically compare the perfomance of 18 similarity metrics in both link prediction and spurious link elimination from qualitative and quantitative perspectives.Furthermore,considering the existence of noise links in the network we compare the robustness of the 18 algorithms on these two problems.The main achievements made are as follows:(1)We present the difference in performance of the algorithms between the link prediction and spurious links elimination,and propose an index to quantify the performance difference of the algorithms.The existing similarity algorithms are proposed for the link prediction problem.However,there still lack effective algorithms for identifying missing interactions.Hence,people directly apply the link prediction algorithms to identify spurious links despite the different performance between these two problems.In this paper,we take a comprehensive comparision of the 18 algorithms' AUCl and AUCs reflect the difference in performance.Interestingly,some methods have high prediction accuracy and they tend to perform low accuracy in identification spurious interaction.Furthermore,the algorithms'performance of identifying spurious interactions is more stable.In addition,the quantitative index of difference of performance ?(AUCl,AUCs)is to some degree correlated with the average shortest path length(d).It indicates that in denser networks,a good link prediction algorithm would also work well in spurious link identification problem.(2)In addition to the algorithms' accuracy AUC,the robustness is also a very important index to evaluate the performance of the algorithms.Therefore,we consider the existence of noise links in the network and contrast the robustness of the 18 algorithms.In this paper,we computes the robustness of the algorithms in recognition spurious links and compares it in the link prediction.By investigating the trend of the AUCl and AUCs values with the varing of the ratio of noise,we find that the 18 algorithms are more sensitive to noise in link prediction and shows stronger robustness in the recognition spurious links.The experiment results are further illustrated that methods can be classified into several clusters according to their behaviors.This work is useful for guiding future use of these similarity metrics for different purposes.Besides,this paper could help us to have a more comprehensive understanding of the identification spurious link.