Measuring the robustness of link prediction algorithms under noisy environment

Peng Zhang, Xiang Wang, Futian Wang, An Zeng* and Jinghua Xiao

[Scientific Reports 6, 18881 (2016)]

http://www.nature.com/articles/srep18881

复杂网络链路预测算法的鲁棒性

摘要

链路预测算法的核心是估算网络中任意两点之间存在连边的可能性。至今，很多高精度的链路预测算法已经被提出。然而，这些算法的精确性都是在无噪音信息下的网络中估算的。当网络可观测的连边信息不再准确的情况下，这些链路预测算法的预测精度会如何变化是一个重要的问题，至今尚未解决。在本文中，我们系统的研究了现有的22种链路预测算法精度受网络中缺失连边，虚假连边，重连连边的影响。我们发现缺失连边比虚假和重连连边对预测精度影响更大，我们还提出了一个指标来定量化这种影响。在这些链路预测算法中，我们发现一些算法虽然精度略低，但是它们能在存在噪音信息的网络中表现稳定。

Abstract:

Link prediction in complex networks is to estimate the likelihood of two nodes to interact with each other in the future. As this problem has applications in a large number of real systems, many link prediction methods have been proposed. However, the validation of these methods is so far mainly conducted in the assumed noise-free networks. Therefore, we still miss a clear understanding of how the prediction results would be affected if the observed network data is no longer accurate. In this paper, we comprehensively study the robustness of the existing link prediction algorithms in the real networks where some links are missing, fake or swapped with other links. We find that missing links are more destructive than fake and swapped links for prediction accuracy. An index is proposed to quantify the robustness of the link prediction methods. Among the twenty-two studied link prediction methods, we find that though some methods have low prediction accuracy, they tend to perform reliably in the “noisy” environment.