Research ArticleINFERENCE

Inferring propagation paths for sparsely observed perturbations on complex networks

See allHide authors and affiliations

Science Advances  21 Oct 2016:
Vol. 2, no. 10, e1501638
DOI: 10.1126/sciadv.1501638


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.

  • Complex networks
  • inference
  • perturbed systems
  • belief propagation

This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercial license, which permits use, distribution, and reproduction in any medium, so long as the resultant use is not for commercial advantage and provided the original work is properly cited.

View Full Text

Stay Connected to Science Advances