Toward link predictability of complex networks

Significance Quantifying a network's link predictability allows us to ( i ) evaluate predictive algorithms associated with the network, ( ii ) estimate the extent to which the organization of the network is explicable, and ( iii ) monitor sudden mechanistic changes during the network's evolution. The hypothesis of this paper is that a group of links is predictable if removing them has only a small effect on the network's structural features. We introduce a quantitative index for measuring link predictability and an algorithm that outperforms state-of-the-art link prediction methods in both accuracy and universality. This study provides fundamental insights into important scientific problems and will aid in the development of information filtering technologies.