Robustness of link prediction under network attacks

Abstract

While link prediction in networks has been a hot topic over the years, its robustness has not been well discussed in literature. In this paper, we study the robustness of some mainstream link prediction methods under various kinds of network attack strategies, including the random attack (RDA), centrality based attacks (CA), similarity based attacks (SA), and simulated annealing based attack (SAA). Through the variation of precision, a typical evaluation index of link prediction, we find that for the SA and SAA, a small fraction of link removals can significantly reduce the performance of link prediction. In general, the SAA has the highest attack efficiency, followed by the SA and then CA. Interestingly, the performance of some particular CA strategies, such as the betweenness based attacks (BA), are even worse than the RDA. Furthermore, we discover that a link prediction method with high performance probably has lower attack robustness, and the vice versa.

11 pages, 4 figures

References in corpus (6)

• Hierarchical structure and the prediction of missing links in networks
• Predicting Missing Links via Local Information
• Effective and Efficient Similarity Index for Link Prediction of Complex Networks
• Small vulnerable sets determine large network cascades in power grids
• Power-law Strength-Degree Correlation From a Resource-Allocation Dynamics on Weighted Networks
• Link Prediction in Complex Networks: A Mutual Information Perspective