Finding Rumor Sources on Random Graphs

Devavrat Shah, Tauhid ZamanarXiv 2012

Abstract

Identifying the source of information diffusion in a network is a fundamental challenge in epidemiology, cybersecurity, and social media analysis. While "rumor centrality" has been proposed as a maximum likelihood estimator for source detection, its theoretical guarantees were previously limited to highly symmetric regular trees and exponential spreading times. This paper establishes the effectiveness of rumor centrality for generic random trees and arbitrary spreading time distributions. By establishing a connection between network diffusion and multi-type continuous-time branching processes (generalized Polya’s urns), we provide precise quantification of detection probabilities. Our results demonstrate the universality of rumor centrality in tree-like graphs, showing that the probability of correct detection remains bounded away from zero even in heterogeneous environments.

Introduction

When a rumor, a computer virus, or a contagious disease spreads through a network, observers often only have access to a "snapshot" of the infected population at a single point in time. The inverse problem—identifying the original source or "Patient Zero"—is critical for containing outbreaks or understanding the origins of information.

In recent years, "rumor centrality" has emerged as a leading method for this task. Originally introduced by Shah and Zaman, rumor centrality serves as a Maximum Likelihood (ML) estimator under the Susceptible-Infected (SI) model. However, early proofs of its efficacy relied on the assumption of $d$-regular trees (where every node has the same degree) and exponential spreading times. This paper addresses the gap between these idealized models and the "messy" reality of heterogeneous networks and unpredictable spreading speeds.

Methodology: From Combinatorics to Branching Processes

Previous analyses of rumor centrality were largely combinatorial, making them difficult to generalize to irregular structures. This work introduces a novel analytical framework based on multi-class Markov branching processes, also known as generalized Polya’s urns.

Instead of viewing the infected graph as a static object, the authors model the growth of the infected set as a stochastic process. In this view, the spread of a rumor is mathematically equivalent to a branching process where different "types" of nodes represent different branches of the tree. This connection allows the application of classical probability theory to modern network problems, enabling the calculation of exact detection probabilities for a much wider class of graphs.

Key Insights and Universality

The central finding of this research is the universality of rumor centrality. The estimator is surprisingly robust; even though it was derived for a specific, simple case, it remains effective in complex, heterogeneous environments.

1. Exact Detection Probabilities

The paper provides the exact value for $\alpha_d$, the probability of correctly identifying the source in any $d$-regular tree. A striking result is the behavior of this probability as the network grows more complex. As the degree $d$ of the tree approaches infinity, the probability of correct detection converges to: $$\lim_{d \to \infty} \alpha_d = 1 - \ln(2) \approx 0.306$$ This confirms that even in very large, dense trees, the source can be identified with a significant, non-zero probability.

2. Exponential Error Decay

A crucial practical concern is what happens when the estimator is wrong. The authors prove that the probability of the estimator picking a node that is $k$ steps away from the true source decays exponentially ($\exp(-\Theta(k))$). This implies that even when rumor centrality misses the exact source, the predicted node is likely to be in the immediate neighborhood of "Patient Zero."

3. Robustness to Irregularity

The research extends these findings to "generic" random trees and "locally tree-like" graphs, such as sparse Erdos-Renyi or random regular graphs. As long as the graph does not contain too many short loops, the branching process approximation holds, and the probability of detection remains strictly above zero regardless of the spreading time distribution.

Discussion and Limitations

While this work significantly broadens the theoretical foundation for rumor centrality, some limitations remain. The analysis is primarily "tree-centric." While many real-world sparse networks are locally tree-like, the results may not directly apply to highly "loopy" or dense social networks with high clustering coefficients.

Furthermore, the study focuses on the SI model, where nodes do not recover. In epidemiological contexts, the Susceptible-Infected-Recovered (SIR) model is often more appropriate. Whether the branching process connection can be extended to models with node recovery remains an open question for future research.

Conclusion

By linking network diffusion to the theory of Polya's urns, this paper provides a rigorous mathematical justification for the use of rumor centrality in diverse settings. The discovery that detection probability remains bounded away from zero for generic random trees suggests that rumor centrality is a powerful, near-universal tool for source detection in sparse networks.

Summary updated

Abstract

We consider the problem of detecting the source of a rumor (information diffusion) in a network based on observations about which set of nodes possess the rumor. In a recent work [10], this question was introduced and studied. The authors proposed rumor centrality as an estimator for detecting the source. They establish it to be the maximum likelihood estimator with respect to the popular Susceptible Infected (SI) model with exponential spreading time for regular trees. They showed that as the size of infected graph increases, for a line (2-regular tree) graph, the probability of source detection goes to 0 while for d-regular trees with d ≥ 3 the probability of detection, say α[subscript d], remains bounded away from 0 and is less than 1/2. Their results, however stop short of providing insights for the heterogeneous setting such as irregular trees or the SI model with non-exponential spreading times.
\n
\nThis paper overcomes this limitation and establishes the effectiveness of rumor centrality for source detection for generic random trees and the SI model with a generic spreading time distribution. The key result is an interesting connection between a multi-type continuous time branching process (an equivalent representation of a generalized Polya's urn, cf. [1]) and the effectiveness of rumor centrality. Through this, it is possible to quantify the detection probability precisely. As a consequence, we recover all the results of [10] as a special case and more importantly, we obtain a variety of results establishing the universality of rumor centrality in the context of tree-like graphs and the SI model with a generic spreading time distribution.
BibTeX
@misc{shah2012finding,
  author = {Devavrat Shah and Tauhid Zaman},
  title = {{Finding Rumor Sources on Random Graphs}},
  year = {2012},
}
Figure