Rumors in a Network: Who's the Culprit?

By Devavrat Shah, Tauhid Zaman. IEEE Transactions on Information Theory, 2009

660 citations recorded by the source corpus.

We provide a systematic study of the problem of finding the source of a rumor in a network. We model rumor spreading in a network with the popular susceptible-infected (SI) model and then construct an estimator for the rumor source. This estimator is based upon a novel topological quantity which we term rumor centrality. We establish that this is a maximum likelihood (ML) estimator for a class of graphs. We find the following surprising threshold phenomenon: on trees which grow faster than a line, the estimator always has nontrivial detection probability, whereas on trees that grow like a line, the detection probability will go to 0 as the network grows. Simulations performed on synthetic networks such as the popular small-world and scale-free networks, and on real networks such as an internet AS network and the U.S. electric power grid network, show that the estimator either finds the source exactly or within a few hops of the true source across different network topologies. We compare rumor centrality to another common network centrality notion known as distance centrality. We prove that on trees, the rumor center and distance center are equivalent, but on general networks, they may differ. Indeed, simulations show that rumor centrality outperforms distance centrality in finding rumor sources in networks which are not tree-like.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/8947b48f57fe066bf3599fa64a932bc8f30aed97

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Rise and fall patterns of information diffusion: model and implications (2012, background): “Analyses of epidemics, blogs, social media, propagation and the cascades they create have attracted much interest [21, 40, 18, 33, 32, 15, 37, 9, 10, 11, 20], and recently the reverse problem (‘find who started it’) [19, 36].”
Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols (2019, neutral): “Although some work has been devoted to the design of source location strategies in speciﬁc settings [15, 16, 17], the general anonymity claim has never been studied from a pure privacy perspective, that is, independently of the very choice of a source location technique.”