Uncertainty Reduction for Stochastic Processes on Complex Networks

Many real-world systems are characterized by stochastic dynamical rules where a complex network ofinteractions among individual elements probabilistically determines their state. Even with full knowledgeof the network structure and of the stochastic rules, the ability to predict system configurations is generallycharacterized by a large uncertainty. Selecting a fraction of the nodes and observing their state may help toreduce the uncertainty about the unobserved nodes. However, choosing these points of observation in anoptimal way is a highly nontrivial task, depending on the nature of the stochastic process and on thestructure of the underlying interaction pattern. In this paper, we introduce a computationally efficientalgorithm to determine quasioptimal solutions to the problem. The method leverages network sparsity toreduce computational complexity from exponential to almost quadratic, thus allowing the straightforwardapplication of the method to mid-to-large-size systems. Although the method is exact only for equilibriumstochastic processes defined on trees, it turns out to be effective also for out-of-equilibrium processes onsparse loopy networks