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 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 focus on predictability instead of prediction. By considering ensembles defined by well-known network models, we prove analytically that even the best possible link prediction method, given by the ensemble connection probabilities, yields a limited precision that depends quantitatively on the topological properties—such as degree heterogeneity, clustering, and community structure—of the ensemble. This suggests an absolute limitation to the predictability of missing links in 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 approximate such a bound from real-world networks with missing links. The predictability limit gives a benchmark to gauge the quality of link prediction methods in real networks.

Figure 1

Dependence of the OS predictability curve on topological structure. For every model, we have generated five ensembles with different model parameters and computed the corresponding theoretical OS predictability curve. (a) Soft configuration model as a function of the exponent of the degree distribution, $\gamma$. To avoid unnecessary fluctuations, the degree distribution includes a natural cutoff. (b) ${\mathbb{S}}^1$ model as a function of $\beta$, which regulates the mean local clustering coefficient. In this case, as well as in (c), the degree distribution exponent has been set to $\gamma =2.5$. (c) Degree-corrected stochastic block model as a function of the number of blocks, $N_b$, with $\lambda =0.5$. The black dashed curve in (b) and (c) shows the OS curve for the sCM for $\gamma =2.5$, i.e., the green curve in (a).

Figure 2

Precision as a function of the fraction of missing links for different link prediction methods on different network ensembles. (a)–(c) For each ensemble and value of the fraction of missing links $q$, we generated 10 networks $G$ and, for each one of them, we generated 100 incomplete networks $G_{\mathrm{obs}}$ on which the link prediction methods were applied. The shaded areas represent the standard deviation of the results. The OS curves correspond to the theoretical limit computed through numerical simulations which implement the optimal strategy. In all cases, we have set $N=1000$ nodes. Also, we have set $\langle k\rangle =10$ and power-law degree distributions with exponent $\gamma =2.5$. (a) Soft configuration model. (b) ${\mathbb{S}}^1$ model with $\beta =1.5$. (c) Degree-corrected stochastic block model with $\lambda =0.5$ and 7 equiprobable blocks. (d)–(f) Comparison between the simulated OS predictability curve and the structural consistency index [7] (details in SM [13]).

Figure 3

Precision as a function of the fraction of missing links for different link prediction methods on eight real-world networks. For each network and value of the fraction of missing links $q$, we generated 100 incomplete networks $G_{\mathrm{obs}}$ on which we applied the link prediction methods. The $p_{ij}$ curves correspond to the precisions given by the simulations of the optimal strategy using the ranking of the inferred probabilities using the original networks. (a)–(d) Using the ${\mathbb{S}}^1$ model. (e)–(h) Using the dc-SBM model. In all plots, the shaded areas represent the standard deviation of the results, which is typically larger for smaller networks.

Figure 4

Inference of predictability on eight different real-world networks. The dashed curves show the mean precisions given by the $p_{ij}$, that is, the OS predictability curves, as in Fig. 3. For each network, we considered ten incomplete networks with $q_0=0.1$, and for each incomplete network we computed its inferred predictability. The solid curves and shaded areas represent the average and standard deviation of such estimations over the ten incomplete networks.