A universal data based method for reconstructing complex networks with binary-state dynamics

Abstract

To understand, predict, and control complex networked systems, a prerequisite is to reconstruct the network structure from observable data. Despite recent progress in network reconstruction, binary-state dynamics that are ubiquitous in nature, technology and society still present an outstanding challenge in this field. Here we offer a framework for reconstructing complex networks with binary-state dynamics by developing a universal data-based linearization approach that is applicable to systems with linear, nonlinear, discontinuous, or stochastic dynamics governed by monotonous functions. The linearization procedure enables us to convert the network reconstruction into a sparse signal reconstruction problem that can be resolved through convex optimization. We demonstrate generally high reconstruction accuracy for a number of complex networks associated with distinct binary-state dynamics from using binary data contaminated by noise and missing data. Our framework is completely data driven, efficient and robust, and does not require any a priori knowledge about the detailed dynamical process on the network. The framework represents a general paradigm for reconstructing, understanding, and exploiting complex networked systems with binary-state dynamics.

References in corpus (21)

• Emergence of scaling in random networks
• Epidemic spreading in scale-free networks
• Catastrophic cascade of failures in interdependent networks
• Statistical physics of social dynamics
• Epidemic processes in complex networks
• Evolutionary games on graphs
• Hierarchical structure and the prediction of missing links in networks
• Dynamical interplay between awareness and epidemic spreading in multiplex networks
• Voter Model on Heterogeneous Graphs
• Exact Controllability of Complex Networks
• Controlling edge dynamics in complex networks
• Controlling complex networks: How much energy is needed?
• Predicting catastrophes in nonlinear dynamical systems by compressive sensing
• Revealing Network Connectivity From Dynamics
• The extreme vulnerability of interdependent spatially embedded networks
• Phase transitions in contagion processes mediated by recurrent mobility patterns
• Reconstructing propagation networks with natural diversity and identifying hidden sources
• Noise bridges dynamical correlation and topology in coupled oscillator networks
• Binary-state dynamics on complex networks: pair approximation and beyond
• Robust Reconstruction of Complex Networks from Sparse Data
• Network reconstruction from random phase-resetting

Cited by in corpus (5)

• Network reconstruction and community detection from dynamics
• A statistical inference approach to structural reconstruction of complex networks from binary time series
• Finding nonlinear system equations and complex network structures from data: a sparse optimization approach
• Universal structural estimator and dynamics approximator for complex networks
• Data based reconstruction of complex multiplex networks