Finding Rumor Sources on Random Trees

Devavrat Shah () and Tauhid Zaman ()
Additional contact information
Devavrat Shah: Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Tauhid Zaman: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2016, vol. 64, issue 3, 736-755

Abstract: We consider the problem of detecting the source of a rumor which has spread in a network using only observations about which set of nodes are infected with the rumor and with no information as to when these nodes became infected. In a recent work ( Shah and Zaman 2010 ), this rumor source detection problem was introduced and studied. The authors proposed the graph score function 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 times for regular trees. They showed that as the size of the infected graph increases, for a path graph (2-regular tree), the probability of source detection goes to 0 and for d -regular trees with d ≥ 3 the probability of detection, say α d , remains bounded away from 0 and is less than 1/2. However, their results stop short of providing insights for the performance of the rumor centrality estimator in more general settings such as irregular trees or the SI model with nonexponential spreading times.This 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 continuous time branching process and the effectiveness of rumor centrality. Through this, it is possible to quantify the detection probability precisely. As a consequence, we recover all previous results as a special case and obtain a variety of novel results including the universality of rumor centrality in the context of tree-like graphs and the SI model with a generic spreading time distribution.

Keywords: rumors; networks; source detection; information diffusion (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2015.1455 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:64:y:2016:i:3:p:736-755

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().