2019/01/31 by Guillermo García-Pérez, García-Pérez, Guillermo, Roya Aliakbarisani +5
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #FOS: Physical sciences #Graph theory and applications #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #Statistical Mechanics (cond-mat.stat-mech) #cond-mat.stat-mech #cs.SI #physics.soc-ph
paper · pdf · doi:10.48550/arxiv.1902.00035
arxiv created 2019/01/31 · openalex publication_date 2019/01/31 · arxiv updated 2019/02/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Predicting missing links in real networks is an important problem in network science to which considerable efforts have been devoted, giving as a result a vast plethora of link prediction methods in the literature. In this work, we take a different point of view on the problem and study the theoretical limitations to the predictability of missing links. In particular, we hypothesise that there is an irreducible uncertainty in link prediction on real networks as a consequence of the random nature of their formation process. By considering ensembles defined by well-known network models, we prove analytically that even the best possible link prediction method for an ensemble, given by the ranking of the ensemble connection probabilities, yields a limited precision. This result suggests a theoretical limitation to the predictability of links in real complex networks. Finally, we show that connection probabilities inferred by fitting network models to real networks allow to estimate an upper-bound to the predictability of missing links, and we further propose a method to approximate such bound from incomplete instances of real-world networks.