Stochastic approximation algorithms for rumor source inference on graphs

Abstract

We revisit the classical problem of identifying the source of rumor in a network, assumed unique, treating as given the network topology and the set of rumor infected nodes. In addition, it is assumed that some partial information about the order in which the nodes were infected, is also available. Such form of information is commonly available to network monitoring agencies. Under this premise, we propose a class of estimators that is agnostic to the underlying stochastic model of rumor spread and further, generalizes other estimators popular in literature, e.g., rumor center, distance center and Jordan center. We also develop an MCMC-based stochastic approximation framework to implement this class of estimators. Results from extensive simulations on the Erdős–Rényi and Barabási–Albert random graph models indicate promising empirical performance and robustness of the proposed estimators to different graph topologies. Our stochastic approximation framework also extends easily to general statistical inference problems on graphs that are of combinatorial nature. In particular, we demonstrate a suitable modification of our framework that makes it amenable to be used for the popular problem of rank aggregation from noisy pairwise comparisons.