Finding rumor sources on random trees

DOI10.1287/OPRE.2015.1455MaRDI QIDQ2830756zbMATH OpenOpenAlexFDO

Authors Devavrat Shah, Tauhid Zaman

Publication date 31 October 2016

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.6230

zbMATH Keywords

information diffusionnetworksrumorssource detection

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15)

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 emph{when} these nodes became infected. In a recent work citep{ref:rc} this rumor source detection problem was introduced and studied. The authors proposed the graph score function {em 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$ while for $d$-regular trees with $dgeq3$ the probability of detection, say $alph{a}_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 non-exponential 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 {em universality} of rumor centrality in the context of tree-like graphs and the SI model with a generic spreading time distribution.

Recommendations

• Rumor source detection for rumor spreading on random increasing trees
• Stochastic rumors on random trees
• Rumor spreading in random evolving graphs
• Rumor spreading in random evolving graphs
• Randomized rumor spreading revisited
• Randomized Rumor Spreading in Dynamic Graphs
• A novel approach for detecting multiple rumor sources in networks with partial observations
• An Algorithmic Framework for Estimating Rumor Sources With Different Start Times
• scientific article; zbMATH DE number 6783407
• Rumor spreading on random regular graphs and expanders

Cites work

• Broadcasting on trees and the Ising model.
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• On finite exponential moments for branching processes and busy periods for queues
• On the conductance of order Markov chains
• Reconstruction on trees: Beating the second eigenvalue

Cited in

(21)

• Rumor identification with maximum entropy in MicroNet
• Inference and rare event simulation for stopped Markov processes via reverse-time sequential Monte Carlo
• Locating the contagion source in networks with partial timestamps
• Community-based immunization in opportunistic social networks
• Reciprocal spreading and debunking processes of online misinformation: a new rumor spreading-debunking model with a case study
• The power of adaptivity in source identification with time queries on the path
• Correlated randomly growing graphs
• Rumor source detection for rumor spreading on random increasing trees
• Finding the seed of uniform attachment trees
• Spatial-temporal deep learning model based rumor source identification in social networks
• Preface to the special issue on information and decisions in social and economic networks
• Schemes of propagation models and source estimators for rumor source detection in online social networks: A short survey of a decade of research
• Enhancing maximum likelihood estimation of infection source localization
• Diffusion in Random Networks: Impact of Degree Distribution
• Epicenter of random epidemic spanning trees on finite graphs
• Root estimation in Galton–Watson trees
• Uncertainty in Study of Social Networks: Robust Optimization and Machine Learning
• Degree centrality and root finding in growing random networks
• Archaeology of random recursive dags and Cooper-Frieze random networks
• Source detection on graphs
• Estimating the history of a random recursive tree

This page was built for publication: Finding rumor sources on random trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830756)