Robustness of Link Prediction Under Network Attacks

Link prediction in networks has been a hot topic over the years, while its robustness has not been well discussed in the network literature. In this brief, we study the robustness of mainstream link prediction methods under various kinds of network attacks, including random attack (RDA), centrality based attack (CA), similarity based attack (SA), and simulated annealing based attack (SAA). In 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 significantly degenerates the performance of link prediction. In general, SAA has the highest attack efficiency, followed by the SA and then the CA attack. Interestingly, the performance of some particular CA strategies, such as the betweenness based attack (BA), are even worse than the RDA attack. Furthermore, we discover that the link prediction method with high performance probably has low attack robustness, and vice versa.