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 (10)

• 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
• Understanding the spreading patterns of mobile phone viruses
• Revealing Network Connectivity From Dynamics
• Phase transitions in contagion processes mediated by recurrent mobility patterns
• Noise bridges dynamical correlation and topology in coupled oscillator networks
• On the Convexity of Latent Social Network Inference
• Spreading of sexually transmitted diseases in heterosexual populations

Cited by in corpus (15)

• Progresses and Challenges in Link Prediction
• 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
• Epidemic spreading driven by biased random walks
• Finding nonlinear system equations and complex network structures from data: a sparse optimization approach
• Inferring Network Structure with Unobservable Nodes from Time Series Data
• 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
• Inference for Network Structure and Dynamics from Time Series Data via Graph Neural Network
• Reconstructing propagation networks with temporal similarity metrics
• Reconstruction of Delay Differential Equation via Learning Parameterized Dictionary
• Temporal similarity metrics for latent network reconstruction: The role of time-lag decay
• Social Diffusion Sources Can Escape Detection