Reconstructing complex networks without time series.

Abstract

In the real world there are situations where the network dynamics are transient (e.g., various spreading processes) and the final nodal states represent the available data. Can the network topology be reconstructed based on data that are not time series? Assuming that an ensemble of the final nodal states resulting from statistically independent initial triggers (signals) of the spreading dynamics is available, we develop a maximum likelihood estimation-based framework to accurately infer the interaction topology. For dynamical processes that result in a binary final state, the framework enables network reconstruction based solely on the final nodal states. Additional information, such as the first arrival time of each signal at each node, can improve the reconstruction accuracy. For processes with a uniform final state, the first arrival times can be exploited to reconstruct the network. We derive a mathematical theory for our framework and validate its performance and robustness using various combinations of spreading dynamics and real-world network topologies.