2015/08/14 by Marco Tulio Angulo, Jaime A. Moreno, Angulo, Marco Tulio +5
Biochemistry, Genetics and Molecular Biology · Neuroscience · Physics and Astronomy · #Biological Physics (physics.bio-ph) #Complex Network Analysis Techniques #FOS: Electrical engineering #FOS: Mathematics #FOS: Physical sciences #Functional Brain Connectivity Studies #Gene Regulatory Network Analysis #Optimization and Control (math.OC) #Physics and Society (physics.soc-ph) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1508.03559
openalex publication_date 2015/08/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Network reconstruction is the first step towards understanding, diagnosing and controlling the dynamics of complex networked systems. It allows us to infer properties of the interaction matrix, which characterizes how nodes in a system directly interact with each other. 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 and degree sequence) can be inferred from given temporal data of individual nodes remain unknown. Here we rigorously derive necessary conditions to reconstruct any property of the interaction matrix. These conditions characterize how uncertain can we be about the coupling functions that characterize the interactions between nodes, and how informative does the measured temporal data need to be; rendering two classes of fundamental limitations of network reconstruction. 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 shed light on the design of better network reconstruction algorithms, which offer practical improvements over existing methods.