Source-linked AI summary
Reconstructing propagation networks with natural diversity and identifying hidden sources
Zhesi Shen, Wen-Xu Wang, Ying Fan, Zengru Di, Ying-Cheng Lai
TL;DR
Reconstructing stochastic propagation networks and locating hidden spreading sources from limited time series remains difficult. The paper adapts compressed sensing to binary spreading dynamics and reports accurate network reconstruction across many model and real-network settings, including hidden-source localization. The framework is not guaranteed to work for non-Markovian spreading processes.
Problem
Reconstructing propagation networks and identifying spreading sources from limited measurements is challenging, particularly for stochastic epidemic and information-diffusion dynamics.
Method
The paper casts stochastic spreading dynamics, including binary time series, into a compressed-sensing framework for reconstructing network interactions and locating hidden sources.
Results
The framework achieves full reconstruction of inhomogeneous interactions from small amounts of binary data and can locate externally inaccessible hidden sources with high confidence.
Takeaways & Limitations
The approach provides a framework for tracing epidemic invasion and information diffusion in complex networked systems.
Takeaways & Limitations
The current reconstruction framework may fail for non-Markovian spreading processes.
Abstract
from arXiv · showhide
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.
Identifying Hidden Source
The paper addresses reconstruction of stochastic propagation networks and hidden-source localization from limited time-series data. It develops a compressed-sensing framework for binary spreading dynamics, extending beyond earlier approaches that required early diffusion information or tree-like routes.
- Motivation: Epidemic spreading and information diffusion motivate reconstructing the hosting networks and identifying spreading sources from limited measurements.The challenge is heightened by virus mutations, heterogeneous-network dynamics, and incomplete monitoring.
- Prior approaches: Earlier source-inference methods decode tree-like diffusion routes using information from the early spreading stage and time delays.Without immediate diffusion information, this tree-structure approach is less applicable.
- Framework: The paper develops a general compressed-sensing framework to reconstruct complex propagation networks from time series.The framework targets stochastic spreading processes, including binary time series, where existing compressed-sensing formulations were not directly applicable.
- Framework: The central technical contribution is a nontrivial transformation that represents stochastic spreading dynamics within the compressed-sensing paradigm.The authors apply the framework to susceptible-infected-susceptible and contact-process epidemic models.
- Hidden-source identification: The framework is designed to locate a hidden source using post-outbreak time series even when the source is externally inaccessible.The reconstruction framework is first presented for outbreaks without a hidden source, then used to locate hidden sources.
Results
Compressed sensing reconstructs an unknown vector from linear measurements, including when the measurement count is much smaller than the vector dimension. The method relies on sparsity and convex optimization.
- Compressed sensing: Compressed sensing reconstructs a vector X from linear measurements Y through a measurement matrix Φ.The formulation uses Y = Φ · X.
Y = Φ · X, (1)
The framework casts stochastic spreading-network reconstruction as a compressed-sensing problem using binary nodal time series, then extends inference to heterogeneous rates and hidden-source localization. Across model and real networks, reconstruction remains accurate with relatively small data and is robust to noise and missing observations.
- Framework: Compressed sensing reconstructs each node’s sparse neighboring vector from relatively few binary time-series observations, enabling recovery of the full directed topology.The method forms reconstruction equations from base strings and solves for sparse link and infection-rate vectors.
- Evaluation: SREL and SRNC separately measure recovery of existent links and null connections, with full reconstruction requiring both success rates to reach 100%.The evaluation also tracks true-positive and false-positive rates because sparsity makes the two success categories distinct.
- Reconstruction accuracy: Nearly perfect reconstruction emerges once the normalized number of base strings exceeds a relatively small threshold, with a gap separating links from null connections.For example, n̂_t = 0.1 leaves overlap, whereas n̂_t = 0.4 creates an explicit separation usable for thresholding.
- Reconstruction accuracy: Mutual-inference conflicts between node neighborhoods vanish when success rates reach 100%, guaranteeing accurate reconstruction of the entire network.At smaller data amounts, inconsistent edge assessments can reduce whole-network accuracy.
- Data requirements: The minimum relative time-series length needed for at least 95% success decreases considerably as network size increases, despite a slight increase in absolute series length.Shared strings can belong to multiple base strings, improving the relative data requirement as N grows.
- Robustness: With 25% of nodal states flipped by noise, both SIS and CP dynamics still achieve about 80% success rates across different network topologies.High success rates also remain mostly unchanged when the fraction of unobservable nodes increases from zero to 25%.
- Heterogeneous rates: After topology reconstruction, individual infection and recovery rates can be estimated from binary nodal time series to characterize heterogeneous immunity and support targeted vaccination.The reproduced infection rates agree quite well with true values with small prediction errors.
- Hidden-source localization: A hidden source can be localized because its immediate neighbors have much larger σ values than other nodes, allowing a cutoff to identify them.The source-localization procedure operates after reconstructed adjacency matrices are obtained.
Discussion
The framework reconstructs epidemic-propagation networks from binary time series and supports identifying hidden sources for targeted control. Its scope includes diverse network interactions and spreading dynamics, but non-Markovian processes may fall outside the current framework.
- Discussion: The framework reconstructs complex propagation networks from binary time series using compressed sensing.It converts network inference into sparse-signal reconstruction solved with standard compressed-sensing algorithms.
- Discussion: It is designed to recover network structure, natural diversity in nodal characteristics, and hidden sources with low data requirements.The authors report rigorous compressed-sensing guarantees and extremely accurate reconstruction across many epidemic-process and network-structure combinations.
- Discussion: The reconstructed information can support targeted vaccination, quarantine, and source isolation in epidemic spreading.The paper also frames source identification as relevant to rumor diffusion and information spreading.
- Discussion: The current reconstruction framework may fail for non-Markovian spreading processes.The authors identify this as a motivation for developing more general approaches.
Methods
The method estimates infection probabilities from repeated nodal-state configurations, then converts the resulting relationships into sparse linear systems solved by compressed sensing. Repeating this locally reconstructs network connections and subsequently estimates heterogeneous infection rates.
- Methods: SIS and CP dynamics model infection and recovery, with λi and δi varying across individuals to represent natural diversity.A hidden source is treated as infected for all time in the simulations.
- Methods: The method constructs Ym×1 = Φm×(N−1) · X(N−1)×1, where X contains possible links to node i and is sparse.Y and Φ are derived from time-series observations, while compressed sensing solves for X.
- Methods: When node i is susceptible and neighboring-state strings match, next-step states are treated as i.i.d. Bernoulli trials to estimate infection probability.The procedure uses normalized Hamming distance and the law of large numbers, enlarging the unknown neighborhood to all other nodes.
- Methods: Thresholds ∆ and Θ select approximately matching strings and multiple base strings, producing enough linearly independent equations for reconstruction.The resulting equations are assembled across time instants to recover each node’s local connection structure.
- Methods: After neighborhoods are reconstructed, infection rates are estimated by grouping observations according to the number of infected neighbors and averaging the resulting values.The procedure applies to networks whose structure has been successfully reconstructed.
- Methods: For CP dynamics, λtrue_i is inferred from time-series states after successful reconstruction of all links.The method uses the satisfied next-state observations and corresponding reconstruction equations.
- Methods: The analyses use model and real networks described in the supplementary materials and Table 1.
G H
The framework converts selected binary time-series strings into a compressed-sensing reconstruction of node neighborhoods, then evaluates its data requirements, robustness, and hidden-source localization.
- Reconstruction framework: Binary strings are grouped around base strings using normalized Hamming-distance thresholds before constructing Y and Φ.The example uses Δ = 3/7 and Θ = 3/7 to select and separate informative strings.
- Reconstruction framework: Averaged next-state and neighboring-string values form Y and Φ, enabling recovery of each neighboring vector X from Y = Φ · X.Each node’s neighborhood can be reconstructed independently, allowing extension to directed links.
- Data requirements: The required relative time-series length n_min,t decreases as network size N increases while maintaining at least 95% success, despite a slight increase in absolute length.This scaling is attributed to strings being shareable across different base strings.
- Hidden-source localization: Immediate neighbors of an inaccessible hidden source have much larger structural variance σ than other nodes, allowing them to be identified by a cutoff.The example uses four neighboring nodes and reconstructs adjacency matrices from multiple accessible-node data segments.