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.

5 figures,accepted by Physical Review E

References in corpus (12)

• 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
• The backbone of the climate network
• Revealing Network Connectivity From Dynamics
• Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
• Reconstructing propagation networks with natural diversity and identifying hidden sources
• Community detection, link prediction, and layer interdependence in multilayer networks
• Identification of core-periphery structure in networks
• Noise bridges dynamical correlation and topology in coupled oscillator networks
• Revealing networks from dynamics: an introduction

Cited by in corpus (6)

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