Finding Rumor Sources on Random Graphs

Details Finding Rumor Sources on Random Graphs Finding Rumor Sources on Random Graphs

2011-10-28

arxiv.org/abs/1110.6230v2

Mathematics

Probability

Scientific paper

We consider the problem of detecting the source of a rumor (information diffusion) in a network based on observations about which set of nodes posses the rumor. In a recent work \cite{ref:rc} by the authors, this question was introduced and studied. The authors proposed {\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 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 \geq 3$ the probability of detection, say $\alpha_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. 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 multi-type continuous time branching processes (an equivalent representation of a generalized Polya's urn, cf. \cite{ref:an}) 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 \cite{ref:rc} as a special case and more importantly, we obtain a variety of results establishing the {\em universality} of rumor centrality in the context of tree-like graphs and the SI model with a generic spreading time distribution.

Affiliated with

Also associated with

No associations

Rating

Finding Rumor Sources on Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Rumor Sources on Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Rumor Sources on Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-685454