Robust reconstruction of sparse network dynamics

Abstract Reconstructing the network interaction structure from multivariate time series is an important problem in multiple fields of science. When the network dynamics is represented as a linear combination of multivariate polynomials, the reconstruction can be formulated as an optimisation problem. For large networks, this optimisation problem does not always have a unique solution, leading to wrong reconstruction. We propose the Ergodic Basis Pursuit (EBP) method, which leverages the statistical properties of the network dynamics to accurately reconstruct sparse networks. The key idea is that the restricted isometry property of the associated library matrix—a crucial condition for ensuring unique reconstruction—can be derived from the ergodic properties of the network dynamics. We show that when the data length scales quadratically with node degree and logarithmically with network size the reconstruction is unique. Compared to traditional methods, the EBP reconstructs sparse networks using significantly less data and is robust to noise. We validate its effectiveness using experimental time series from optoelectronic networks.