Fast rumor source identification via random walks

We consider the problem of inferring the source of a rumor in a given large network. We assume that the rumor propagates in the network through a discrete time susceptible-infected model. Input to our problem includes information regarding the entire network, an infected subgraph of the network observed at some known time instant, and the probability of one-hop rumor propagation. We propose a heuristic based on the hitting time statistics of a surrogate random walk process that can be used to approximate the maximum likelihood estimator of the rumor source. We test the performance of our heuristic on some standard synthetic and real-world network datasets and show that it outperforms many centrality-based heuristics that have traditionally been used in rumor source inference literature. Through time complexity analysis and extensive experimental evaluation, we demonstrate that our heuristic is computationally efficient for large, undirected and dense non-tree networks.