Abstract
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 a variant of the popular SIR 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 an 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 non-trivial 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.
Introduction
In our hyper-connected world, a single spark can trigger a wildfire. Whether it’s a malicious rumor on social media, a computer virus tearing through the Internet, or a failure cascading across a power grid, the "network effect" often amplifies isolated risks into global instabilities. But once the damage is done, how do we look at the aftermath and point to the person—or node—who started it all?
In their paper, "Rumors in a Network: Who’s the Culprit?", Devavrat Shah and Tauhid Zaman tackle this "needle in a haystack" problem using a novel approach they call Rumor Centrality.
Problem Formulation
While researchers have spent decades studying how rumors spread (the forward problem), very little work has addressed the inverse problem: source identification. Given a snapshot of a network where some nodes are "infected" and others are not, can we work backward to find the original source? This is incredibly difficult because spreading processes are inherently noisy and probabilistic. Traditional network metrics often fail to capture the specific "causal history" required to find the starting point.
The authors model rumor spreading using a variant of the popular SIR model called the Susceptible-Infected (SI) model. In this setup, once a node is infected, it stays infected and can pass the rumor to its neighbors at a random time (governed by an exponential distribution).
The Core Innovation: Rumor Centrality
The authors define Rumor Centrality ($R(v, G)$) for a node $v$ as the number of distinct "permitted permutations"—valid chronological orders in which the rumor could have spread—starting from that node to produce the observed infected subgraph.
For Trees
For tree structures, the authors derive a succinct mathematical formula for rumor centrality based on subtree sizes. They also provide a highly efficient $O(N)$ message-passing algorithm that allows every node in a network to calculate its own rumor centrality simultaneously.
For General Graphs
Since counting permutations in complex graphs is computationally "hard" (#P-complete), they introduce a BFS Heuristic. They approximate the likelihood by looking at the Breadth-First Search tree rooted at each candidate node, effectively treating the "fastest" spreading path as the most likely one.
Key Insights and Results
The authors validated their estimator across several types of networks, including synthetic small-world and scale-free models, as well as real-world datasets like the Internet AS Network and the U.S. Electric Power Grid.
The Phase Transition of Detection
The authors discovered a fundamental limit to our ability to find "culprits." On a simple line of nodes, the probability of finding the source drops to zero as the network grows. However, on "expanding" trees (where nodes have 3 or more connections), there is a strictly positive probability of finding the exact source, no matter how large the network becomes.
Rumor vs. Distance Centrality
On trees, rumor centrality is equivalent to the well-known "distance centrality" (finding the node closest to all others). However, on general graphs, rumor centrality is superior because it leverages more of the network's structural information beyond just the shortest paths. In small-world network simulations, rumor centrality correctly identified the source 16% of the time, compared to only 2% for distance centrality.
Real-World Performance
On the U.S. power grid and Internet AS networks, the estimator consistently found the source either exactly or within just a few "hops" of the true origin, significantly outperforming random guessing.
Conclusion and Future Work
The authors acknowledge that their BFS heuristic, while powerful for heterogeneous networks, can degrade performance in very regular networks by amplifying slight, random heterogeneities. Future directions include refining the heuristic to understand its performance bounds and generalizing the model to account for heterogeneous spreading rates, reflecting the complexities of social and biological systems.
Summary updated