Precision as a measure of predictability of missing links in real networks

Predicting missing links in real networks is an important open problem in network science to whichconsiderable efforts have been devoted, giving as a result a vast plethora of link prediction methods in theliterature. In this work, we take a different point of view on the problem and focus on predictability insteadof prediction. By considering ensembles defined by well-known network models, we prove analytically thateven the best possible link prediction method, given by the ensemble connection probabilities, yields a limitedprecision that depends quantitatively on the topological properties—such as degree heterogeneity, clustering, andcommunity structure—of the ensemble. This suggests an absolute limitation to the predictability of missing linksin real networks, due to the irreducible uncertainty arising from the random nature of link formation processes.We show that a predictability limit can be estimated in real networks, and we propose a method to approximatesuch a bound from real-world networks with missing links. The predictability limit gives a benchmark to gaugethe quality of link prediction methods in real networks