Predictability of complex networks
Proceedings of the National Academy of Sciences · 28.04.2026 · 123 (17)
DOI: 10.1073/pnas.2535161123 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the National Academy of Sciences, online erschienen am 20.04.2026. Verfasst von Fei Jing und 3 weiteren Autor:innen. Beteiligte Einrichtung: Musketeers Foundation Institute of Data Science, The University of Hong Kong, Hong Kong 999077, China. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 29 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: MOST | National Natural Science Foundation of China (NSFC).
Abstract (Originalsprache)
We establish network predictability theory by mapping link prediction onto a spin glass model, where network partitions correspond to spin configurations, and predictability equals the system’s average energy. Using the cavity method from statistical physics, we prove that global predictability decomposes into individual link contributions, enabling an efficient local sampling algorithm that reduces the computational complexity of evaluating individual link contributions from being dependent on the entire network to only its local neighborhood, scaling with the average degree. We derive exact results for canonical network models: Erdös–Rényi networks exhibit universal predictability of 0.5 regardless of algorithm choice, establishing the random baseline, while structured networks show predictability controlled by their prior parameters. We introduce the predictability index, which quantifies the maximum achievable performance without information loss and accurately predicts algorithm performance under random division. Analysis of real networks validates our framework, revealing how degree heterogeneity and structural patterns govern predictability. This physics-based approach provides both theoretical insights into link prediction limits and practical tools for assessing network reconstruction potential, with implications for applications from biological network inference to social network analysis.
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Musketeers Foundation Institute of Data Science, The University of Hong Kong, Hong Kong 999077, China.
- Department of Pharmacology and Pharmacy, The University of Hong Kong, Hong Kong 999077, China.
- Center for Digital Communication Studies, Zhejiang University, Hangzhou 310058, China.
- International Research Center of Complexity Sciences, Hangzhou International Innovation Institute, Beihang University, Hangzhou 311115, China.
- School of Computer, Qinghai Normal University, Xining, Qinghai 810008, China.
- Dipartimento di Fisica, Sapienza Università di Roma, Roma 00185, Italy.
ORCID-Profile: Qingpeng Zhang, Giorgio Parisi
Förderung
- MOST | National Natural Science Foundation of China (NSFC)
Zitieren
APA
Jing, F., Zhang, Z. K., Zhang, Q., & Parisi, G. (2026). Predictability of complex networks. Proceedings of the National Academy of Sciences, 123(17). https://doi.org/10.1073/pnas.2535161123
Vancouver
Jing F, Zhang ZK, Zhang Q, Parisi G. Predictability of complex networks. Proceedings of the National Academy of Sciences. 2026;123(17). doi:10.1073/pnas.2535161123
BibTeX
@article{Jing2026,
author = {Jing, Fei and Zhang, Zi-Ke and Zhang, Qingpeng and Parisi, Giorgio},
title = {Predictability of complex networks},
journal = {Proceedings of the National Academy of Sciences},
year = {2026},
volume = {123},
number = {17},
doi = {10.1073/pnas.2535161123}
}
EUVIMED