Reconstructing propagation networks with natural diversity and identifying hidden sources

Abstract

Our ability to uncover complex network structure and dynamics from data is fundamental to understanding and controlling collective dynamics in complex systems. Despite recent progress in this area, reconstructing networks with stochastic dynamical processes from limited time series remains to be an outstanding problem. Here we develop a framework based on compressed sensing to reconstruct complex networks on which stochastic spreading dynamics take place. We apply the methodology to a large number of model and real networks, finding that a full reconstruction of inhomogeneous interactions can be achieved from small amounts of polarized (binary) data, a virtue of compressed sensing. Further, we demonstrate that a hidden source that triggers the spreading process but is externally inaccessible can be ascertained and located with high confidence in the absence of direct routes of propagation from it. Our approach thus establishes a paradigm for tracing and controlling epidemic invasion and information diffusion in complex networked systems.

20 pages and 5 figures. For Supplementary information, please see http://www.nature.com/ncomms/2014/140711/ncomms5323/full/ncomms5323.html#t

References in corpus (23)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Epidemic spreading in scale-free networks
• Hierarchical structure and the prediction of missing links in networks
• Prediction and predictability of global epidemics: the role of the airline transportation network
• Efficient Immunization Strategies for Computer Networks and Populations
• Thresholds for epidemic spreading in networks
• Exact Controllability of Complex Networks
• Absence of epidemic threshold in scale-free networks with connectivity correlations
• Understanding the spreading patterns of mobile phone viruses
• Controlling edge dynamics in complex networks
• Controlling complex networks: How much energy is needed?
• Locating the Source of Diffusion in Large-Scale Networks
• Predicting catastrophes in nonlinear dynamical systems by compressive sensing
• Revealing Network Connectivity From Dynamics
• High-accuracy approximation of binary-state dynamics on networks
• Phase transitions in contagion processes mediated by recurrent mobility patterns
• Epidemic threshold for the SIS model on networks
• Noise bridges dynamical correlation and topology in coupled oscillator networks
• On the Convexity of Latent Social Network Inference
• Non mean-field behavior of the contact process on scale-free networks
• Network reconstruction from random phase-resetting
• Spreading of sexually transmitted diseases in heterosexual populations

Cited by in corpus (38)

• Data Based Identification and Prediction of Nonlinear and Complex Dynamical Systems
• Robust Reconstruction of Complex Networks from Sparse Data
• Network reconstruction and community detection from dynamics
• Progresses and Challenges in Link Prediction
• Events Determine Spreading Patterns: Information Transmission via Internal and External Influences on Social Networks
• A General Deep Learning Framework for Network Reconstruction and Dynamics Learning
• A statistical inference approach to structural reconstruction of complex networks from binary time series
• Link prediction based on path entropy
• Effects of human dynamics on epidemic spreading in Côte d'Ivoire
• Evaluating the effect of city lock-down on controlling COVID-19 propagation through deep learning and network science models
• Expectation-Maximizing Network Reconstruction and MostApplicable Network Types Based on Binary Time Series Data
• Detecting Hidden Units and Network Size from Perceptible Dynamics
• A universal data based method for reconstructing complex networks with binary-state dynamics
• Epidemic spreading driven by biased random walks
• Network reconstruction from infection cascades
• Finding nonlinear system equations and complex network structures from data: a sparse optimization approach
• Suppressing traffic-driven epidemic spreading by adaptive routing strategy
• Universal structural estimator and dynamics approximator for complex networks
• Suppressing traffic-driven epidemic spreading by use of the efficient routing protocol
• Machine learning for predictive estimation of qubit dynamics subject to dephasing
• Variational Bayesian Weighted Complex Network Reconstruction
• Diffusion on hierarchical systems of weakly-coupled networks
• Inferring Network Structure with Unobservable Nodes from Time Series Data
• Machine Discovery of Partial Differential Equations from Spatiotemporal Data
• Network Reconstruction and Prediction of Epidemic Outbreaks for NIMFA Processes
• Information Evolution in Complex Networks
• A comparative study of similarity-based and GNN-based link prediction approaches
• Reconstructing dynamics of complex systems from noisy time series with hidden variables
• Predicting Dynamics on Networks Hardly Depends on the Topology
• Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network
• Fundamental limitations of network reconstruction
• Global and partitioned reconstructions of undirected complex networks
• Reconstruction of Delay Differential Equation via Learning Parameterized Dictionary
• Reconstructing propagation networks with temporal similarity metrics
• The spreading ability of nodes towards localized targets in complex networks
• Social Diffusion Sources Can Escape Detection
• Data based reconstruction of complex multiplex networks
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay