Functional Robustness provides a new paradigm for structural predictability in complex networks

The important research issue within complex networks is link prediction, which greatly advances the field of biological systems, social relationship mining, mobile trajectory prediction, and recommendation systems. Numerous research efforts in this field focus on the development of various link prediction algorithms, but there is little work that delves into the difficulty of link prediction given networks. Quantifying the predictability of complex networks, i.e., the highest accuracy in link prediction, can help us understand the degree of regularity within the network itself. Previous methods measure network predictability from an entropic perspective, where high degree of randomness implies low predictability. However, they are constrained by challenges such as limited precision, inadepuate distinction from algorithmic methods, and, most critically, an incomplete understanding of why networks can be predicted.

In this proposal, we aim to quantify network predictability from the perspective of network functional robustness. We hypothesize that networks with higher functional robustness to structural perturbations are associated with higher predictability. While previous research on network predictability typically originated from information theory or data mining perspectives, our approach will be grounded in network functionality and aim at understanding the fundamental reasons behind network predictability.

Specifically, we will first establish a connection between functional robustness and the structural parameter space. A larger parameter space signifies that the functionality is less sensitive to structural perturbation. That is, when facing disruptions in links, minor parameter variations do not result in significant changes in network functionality. Second, we will delve into the fundamental reasons why networks can be accurately predicted, exploring the intrinsic connections between network functional robustness and predictive performance. Third, we will quantify individual link predictability for finer-grained measurement of network predictability and controllable manipulation of network predictability. Finally, based on the proposed network predictability paradigm, we will propose new link prediction algorithms with enhanced predictive performance.

This series of studies in this proposal will provide us with new theories and comprehensive tools for network predictability, advancing the field of complex network science.