Fundamental limitations of network reconstruction from temporal data

Marco Tulio Angulo, Jaime A. Moreno, Gabor Lippner, Albert László Barabási, Yang Yu Liu

Research output: Contribution to journalArticlepeer-review

Abstract (may include machine translation)

Inferring properties of the interaction matrix that characterizes hownodes in a networked system directly interact with each other is a well-known network reconstruction problem. Despite a decade of extensive studies, network reconstruction remains an outstanding challenge. The fundamental limitations governing which properties of the interaction matrix (e.g. adjacency pattern, sign pattern or degree sequence) can be inferred from given temporal data of individual nodes remain unknown. Here, we rigorously derive the necessary conditions to reconstruct any property of the interaction matrix. Counterintuitively, we find that reconstructing any property of the interaction matrix is generically as difficult as reconstructing the interaction matrix itself, requiring equally informative temporal data. Revealing these fundamental limitations sheds light on the design of better network reconstruction algorithms that offer practical improvements over existing methods.

Original languageEnglish
Article number20160966
JournalJournal of the Royal Society Interface
Volume14
Issue number127
DOIs
StatePublished - 1 Feb 2017

Keywords

  • Network reconstruction
  • Networked systems
  • System identification

Fingerprint

Dive into the research topics of 'Fundamental limitations of network reconstruction from temporal data'. Together they form a unique fingerprint.

Cite this