  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.
