Information-Theoretic Limits of Complex Network Reconstruction
Why there is a hard ceiling on how well a hidden interaction network can be recovered from data, independent of the reconstruction algorithm used. Students learn the notion of reconstructability - the fraction of a network's structural information that is recoverable - expressed as an information-theoretic upper bound on the mutual information between the true graph and any reconstruction, and the reconstruction index, a model-selection quantity that estimates this limit from data and predicts reconstruction error without knowing the true network.
On the reconstruction limits of complex networks Charles Murphy,1, 2, ∗Simon Lizotte,1, 2 Fran¸cois
Theoretical study of the fundamental limits of network reconstruction - inferring a system's hidden interaction graph from indirect, noisy observations such as time series. Building on reconstructabi…