Title: Uncertainty Reduction for Stochastic Processes on Complex Networks,
Abstract: Many real-world systems are characterized by stochastic dynamical rules where
a complex network of interactions among individual elements probabilistically
determines their state. Even with full knowledge of the network structure and
of the stochastic rules, the ability to predict system configurations is
generally characterized by a large uncertainty. Selecting a fraction of the
nodes and observing their state may help to reduce the uncertainty about the
unobserved nodes. However, choosing these points of observation in an optimal
way is a highly nontrivial task, depending on the nature of the stochastic
process and on the structure of the underlying interaction pattern. In this
paper, we introduce a computationally efficient algorithm to determine
quasioptimal solutions to the problem. The method leverages network sparsity to
reduce computational complexity from exponential to almost quadratic, thus
allowing the straightforward application of the method to mid-to-large-size
systems. Although the method is exact only for equilibrium stochastic processes
defined on trees, it turns out to be effective also for out-of-equilibrium
processes on sparse loopy networks.