Rooting out the Rumor Culprit from Suspects
arXiv:1301.6312 · doi:10.1109/ISIT.2013.6620711
Abstract
Suppose that a rumor originating from a single source among a set of suspects spreads in a network, how to root out this rumor source? With the a priori knowledge of suspect nodes and an observation of infected nodes, we construct a maximum a posteriori (MAP) estimator to identify the rumor source using the susceptible-infected (SI) model. The a priori suspect set and its associated connectivity bring about new ingredients to the problem, and thus we propose to use local rumor center, a generalized concept based on rumor centrality, to identify the source from suspects. For regular tree-type networks of node degree δ, we characterize Pc(n), the correct detection probability of the estimator upon observing n infected nodes, in both the finite and asymptotic regimes. First, when every infected node is a suspect, Pc(n) asymptotically grows from 0.25 to 0.307 with δ from 3 to infinity, a result first established in Shah and Zaman (2011, 2012) via a different approach; and it monotonically decreases with n and increases with δ. Second, when the suspects form a connected subgraph of the network, Pc(n) asymptotically significantly exceeds the a priori probability if δ>2, and reliable detection is achieved as δ becomes large; furthermore, it monotonically decreases with n and increases with δ. Third, when there are only two suspects, Pc(n) is asymptotically at least 0.75 if δ>2; and it increases with the distance between the two suspects. Fourth, when there are multiple suspects, among all possible connection patterns, that they form a connected subgraph of the network achieves the smallest detection probability. Our analysis leverages ideas from the Polya's urn model in probability theory and sheds insight into the behavior of the rumor spreading process not only in the asymptotic regime but also for the general finite-n regime.
Submitted to IEEE Transactions on Information Theory
References in corpus (2)
Cited by in corpus (27)
- Rooting out the Rumor Culprit from Suspects
- How to Identify an Infection Source with Limited Observations
- Identifying spatial invasion of pandemics on metapopulation networks via anatomizing arrival history
- Infection Spreading and Source Identification: A Hide and Seek Game
- Epidemic Source Detection in Contact Tracing Networks: Epidemic Centrality in Graphs and Message-Passing Algorithms
- Bayesian Inference of Spreading Processes on Networks
- Choosing among alternative histories of a tree
- On the Universality of Jordan Centers for Estimating Infection Sources in Tree Networks
- Effector Detection in Social Networks
- Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
- On the Properties of Gromov Matrices and their Applications in Network Inference
- Network connectivity under a probabilistic node failure model
- Schemes of Propagation Models and Source Estimators for Rumor Source Detection in Online Social Networks: A Short Survey of a Decade of Research
- Detection of Rumors and Their Sources in Social Networks: A Comprehensive Survey
- Statistical inference framework for source detection of contagion processes on arbitrary network structures
- Identification of Source of Rumors in Social Networks with Incomplete Information
- Source Localization in Networks: Trees and Beyond
- Rumor Source Detection under Querying with Untruthful Answers
- Multiple Infection Sources Identification with Provable Guarantees
- Morphological Inversion of Complex Diffusion
- Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process
- Necessary and Sufficient Budgets in Information Source Finding with Querying: Adaptivity Gap
- Diffusion Source Identification on Networks with Statistical Confidence
- Network infection source identification under the SIRI model
- Network Topology Inference Using Information Cascades with Limited Statistical Knowledge
- Information Source Finding in Networks: Querying with Budgets
- Back to the Source: an Online Approach for Sensor Placement and Source Localization