Inferring propagation paths for sparsely observed perturbations on complex networks
arXiv:1801.01179 · doi:10.1126/sciadv.1501638
Abstract
In a complex system, perturbations propagate by following paths on the network of interactions among the system's units. In contrast to what happens with the spreading of epidemics, observations of general perturbations are often very sparse in time (there is a single observation of the perturbed system) and in "space" (only a few perturbed and unperturbed units are observed). A major challenge in many areas, from biology to the social sciences, is to infer the propagation paths from observations of the effects of perturbation under these sparsity conditions. We address this problem and show that it is possible to go beyond the usual approach of using the shortest paths connecting the known perturbed nodes. Specifically, we show that a simple and general probabilistic model, which we solved using belief propagation, provides fast and accurate estimates of the probabilities of nodes being perturbed.
References in corpus (20)
- Hierarchical organization of modularity in metabolic networks
- Functional cartography of complex metabolic networks
- Identification of influential spreaders in complex networks
- Community detection algorithms: a comparative analysis
- The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
- Self-similar community structure in organisations
- Dynamical and correlation properties of the Internet
- Prediction and predictability of global epidemics: the role of the airline transportation network
- Efficient Immunization Strategies for Computer Networks and Populations
- Missing and spurious interactions and the reconstruction of complex networks
- Modeling the Worldwide Spread of Pandemic Influenza: Baseline Case and Containment Interventions
- Velocity and hierarchical spread of epidemic outbreaks in scale-free networks
- Locating the Source of Diffusion in Large-Scale Networks
- A Poissonian explanation for heavy-tails in e-mail communication
- Inferring the origin of an epidemic with a dynamic message-passing algorithm
- Bayesian inference of epidemics on networks via Belief Propagation
- Systemic delay propagation in the US airport network
- Spreading paths in partially observed social networks
- A Novel Methodology to Estimate Metabolic Flux Distributions in Constraint-Based Models
- A weighted belief-propagation algorithm to estimate volume-related properties of random polytopes