  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.

Social and Information Networks;Physics and Society