TY - JOUR
T1 - Fundamental limitations of network reconstruction from temporal data
AU - Angulo, Marco Tulio
AU - Moreno, Jaime A.
AU - Lippner, Gabor
AU - Barabási, Albert László
AU - Liu, Yang Yu
N1 - Publisher Copyright:
© 2017 The Author(s) Published by the Royal Society. All rights reserved.
PY - 2017/2/1
Y1 - 2017/2/1
N2 - 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.
AB - 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.
KW - Network reconstruction
KW - Networked systems
KW - System identification
UR - http://www.scopus.com/inward/record.url?scp=85015180773&partnerID=8YFLogxK
U2 - 10.1098/rsif.2016.0966
DO - 10.1098/rsif.2016.0966
M3 - Article
C2 - 28148769
AN - SCOPUS:85015180773
SN - 1742-5689
VL - 14
JO - Journal of the Royal Society Interface
JF - Journal of the Royal Society Interface
IS - 127
M1 - 20160966
ER -