Fundamental limitations of network reconstruction from temporal data.
Inferring properties of the interaction matrix that characterizes how nodes 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.
Institute of Mathematics, Universidad Nacional Autónoma de México, Juriquilla 76230, México.
Marco Tulio
0000-0002-9802-8567
MT
Angulo
Institute of Engineering, Universidad Nacional Autónoma de México, CdMx 04510, México.
Jaime A
JA
Moreno
Department of Mathematics, Northeastern University, Boston MA 02115, USA.
Gabor
G
Lippner
Center for Complex Networks Research, Northeastern University, Boston MA 02115, USA.|Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Boston, MA 02115, USA.|Center for Network Science, Central European University, Budapest 1052, Hungary.
Albert-László
AL
Barabási
Center for Cancer Systems Biology, Dana-Farber Cancer Institute, Boston, MA 02115, USA yyl@channing.harvard.edu.|Channing Division of Network Medicine, Brigham and Women's Hospital, Boston, MA 02115, USA.|Harvard Medical School, Boston, MA 02115, USA.
Yang-Yu
0000-0003-2728-4907
YY
Liu
D001330:Electronic Data Processing; D008962:Models, Theoretical
network reconstruction; networked systems; system identification