Revealing the predictability of intrinsic structure in complex networks

Jiachen Sun, Ling Feng, Jiarong Xie, Xiao Ma, Dashun Wang, Yanqing Hu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Structure prediction is an important and widely studied problem in network science and machine learning, finding its applications in various fields. Despite the significant progress in prediction algorithms, the fundamental predictability of structures remains unclear, as networks’ complex underlying formation dynamics are usually unobserved or difficult to describe. As such, there has been a lack of theoretical guidance on the practical development of algorithms for their absolute performances. Here, for the first time, we find that the normalized shortest compression length of a network structure can directly assess the structure predictability. Specifically, shorter binary string length from compression leads to higher structure predictability. We also analytically derive the origin of this linear relationship in artificial random networks. In addition, our finding leads to analytical results quantifying maximum prediction accuracy, and allows the estimation of the network dataset potential values through the size of the compressed network data file.

Original languageEnglish (US)
Article number574
JournalNature communications
Volume11
Issue number1
DOIs
StatePublished - Dec 1 2020

ASJC Scopus subject areas

  • Chemistry(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Physics and Astronomy(all)

Fingerprint Dive into the research topics of 'Revealing the predictability of intrinsic structure in complex networks'. Together they form a unique fingerprint.

Cite this