Back to Videos
This is a video about Fundamental limitations of Network Reconstruction

Fundamental limitations of Network Reconstruction

April 15, 2016
Presenters: Marco Tulio Angulo
Length: 32 minutes 59 seconds

Watch Video 


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.

In this talk, I will discuss our recent work on deriving the necessary conditions to reconstruct any desired property of the interaction matrix. These conditions characterize how uncertain can we be about the coupling functions of the system (that characterize how nodes interact), and how informative does the measured temporal data need to be. 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. In other words, reconstructing less information (e.g., adjacency pattern instead of edge-weights) does not make the network reconstruction problem easier. Revealing these fundamental limitations shed light on the design of better network reconstruction algorithms, which offer practical improvements over existing methods.

Joint work with Yang-Yu Liu (Harvard), Lászlo Barabási (Northeastern), Gabor Lippner (Northeastern) and Jaime Moreno (UNAM, Mexico).