Rooting out the Rumor Culprit from Suspects
Preprint
Abstract
In this paper, we study the problem of rooting out a single rumor source: supposing that a rumor, which originates from one node among a set of suspect nodes in a network, is spreading across the network following the susceptible-infected (SI) model, how can we and how well can we identify this rumor source? With the a priori knowledge of the set of suspect nodes and a snapshot observation of infected nodes, we construct a maximum a posteriori (MAP) estimator to identify the rumor source. For regular tree-type networks, we establish exact and asymptotic results on the detection probability of the source estimator. In particular, if the network is not linear, we have the following asymptotic results of the correct detection probability: First, when every infected node belongs to the suspect set, it grows from 0.25 to 0.307 as the node degree increases from three to infinity, a result first established in [1], [2] via a different approach. Second, when the suspect nodes form a connected subgraph of the network, it significantly exceeds the a priori probability, and reliable detection is achieved as the node degree becomes large. Third, when there are only two suspect nodes, it is at least 0.75 and increases with the distance between the two nodes. Our analysis leverages ideas from the Polya's urn model and sheds insight into the behavior of the rumor spreading process.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Information Source Detection in the SIR Model: A Sample-Path-Based ApproachIEEE/ACM Transactions on Networking, 2014
- Identifying Infection Sources and Regions in Large NetworksIEEE Transactions on Signal Processing, 2013
- Locating the Source of Diffusion in Large-Scale NetworksPhysical Review Letters, 2012
- Rumors in a Network: Who's the Culprit?IEEE Transactions on Information Theory, 2011
- Spreading gossip in social networksPhysical Review E, 2007
- Bayesian Inference for Stochastic Multitype Epidemics in Structured Populations Via Random GraphsJournal of the Royal Statistical Society Series B: Statistical Methodology, 2005
- Spread of epidemic disease on networksPhysical Review E, 2002
- Epidemic Spreading in Scale-Free NetworksPhysical Review Letters, 2001
- Epidemics and percolation in small-world networksPhysical Review E, 2000
- The Mathematical Theory of Infectious Diseases and Its ApplicationsOperational Research Quarterly (1970-1977), 1977