A statistical inference approach to structural reconstruction of complex networks from binary time series

Abstract

Complex networks hosting binary-state dynamics arise in a variety of contexts. In spite of previous works, to fully reconstruct the network structure from observed binary data remains to be challenging. We articulate a statistical inference based approach to this problem. In particular, exploiting the expectation-maximization (EM) algorithm, we develop a method to ascertain the neighbors of any node in the network based solely on binary data, thereby recovering the full topology of the network. A key ingredient of our method is the maximum likelihood estimation of the probabilities associated with actual or non-existent links, and we show that the EM algorithm can distinguish the two kinds of probability values without any ambiguity, insofar as the length of the available binary time series is reasonably long. Our method does not require any {\em a priori} knowledge of the detailed dynamical processes, is parameter free, and is capable of accurate reconstruction even in the presence of noise. We demonstrate the method using combinations of distinct types of binary dynamical processes and network topologies, and provide a physical understanding of the underlying reconstruction mechanism. Our statistical inference based reconstruction method contributes an additional piece to the rapidly expanding "toolbox" of data based reverse engineering of complex networked systems.

arXiv comment5 figures,accepted by Physical Review E

References in corpus (26)

• Emergence of scaling in random networks
• Epidemic processes in complex networks
• Evolutionary games on graphs
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Scale-free brain functional networks
• Voter Model on Heterogeneous Graphs
• The backbone of the climate network
• An efficient and principled method for detecting communities in networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Predicting catastrophes in nonlinear dynamical systems by compressive sensing
• Revealing Network Connectivity From Dynamics
• Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
• Model-free reconstruction of neuronal network connectivity from calcium imaging signals
• Reconstructing propagation networks with natural diversity and identifying hidden sources
• Community detection, link prediction, and layer interdependence in multilayer networks
• Inferring Network Topology from Complex Dynamics
• Identification of core-periphery structure in networks
• Noise bridges dynamical correlation and topology in coupled oscillator networks
• Revealing networks from dynamics: an introduction
• Robust Reconstruction of Complex Networks from Sparse Data
• Estimating the number of communities in a network
• Network reconstruction from random phase-resetting
• Dynamics of competing ideas in complex social systems
• A universal data based method for reconstructing complex networks with binary-state dynamics
• Reverse engineering of complex dynamical networks in the presence of time-delayed interactions based on noisy time series

Cited by in corpus (7)

• Network reconstruction and community detection from dynamics
• Expectation-Maximizing Network Reconstruction and MostApplicable Network Types Based on Binary Time Series Data
• Universal structural estimator and dynamics approximator for complex networks
• Variational Bayesian Weighted Complex Network Reconstruction
• Tensor product algorithms for inference of contact network from epidemiological data
• Reconstruction of Delay Differential Equation via Learning Parameterized Dictionary
• Reconstructing networks from simple and complex contagions