EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

Predictability of complex networks

Fei Jing, Zi-Ke Zhang, Qingpeng Zhang iD, Giorgio Parisi iD

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).

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

algorithmic performancecavity methodspin glasses

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}
}
Kostenlos starten →