Robustness of Link-prediction Algorithm Based on Similarity and Application to Biological Networks

Abstract

Many algorithms have been proposed to predict missing links in a variety of real networks. These studies focus on mainly both accuracy and efficiency of these algorithms. However, little attention is paid to their robustness against either noise or irrationality of a link existing in almost all of real networks. In this paper, we investigate the robustness of several typical node-similarity-based algorithms and find that these algorithms are sensitive to the strength of noise. Moreover, we find that it also depends on networks' structure properties, especially on network efficiency, clustering coefficient and average degree. In addition, we make an attempt to enhance the robustness by using link weighting method to transform un-weighted network to weighted one and then make use of weights of links to characterize their reliability. The result shows that proper link weighting scheme can enhance both robustness and accuracy of these algorithms significantly in biological networks while it brings little computational effort.

11 pages, 4 figues

References in corpus (11)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Efficient Behavior of Small-World Networks
• Assortative mixing in networks
• Evolution of networks
• Link Prediction in Complex Networks: A Survey
• Characterization of complex networks: A survey of measurements
• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• Missing and spurious interactions and the reconstruction of complex networks
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks