Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Predictability of missing links in complex networks   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.

5
The categories of this paper are: gr-qc
11
The categories of this paper are: hep-lat
30
The categories of this paper are: q-alg
18
The categories of this paper are: econ
0
The categories of this paper are: hep-ph
20
The categories of this paper are: acc-phys
29
The categories of this paper are: funct-an
10
The categories of this paper are: q-bio
7
The categories of this paper are: hep-th
12
The categories of this paper are: nucl-th
28
The categories of this paper are: alg-geom
25
The categories of this paper are: patt-sol
21
The categories of this paper are: adap-org
15
The categories of this paper are: nucl-ex
2
The categories of this paper are: math
8
The categories of this paper are: hep-ex