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 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 using the susceptible-infected (SI) model. When analyzing the performance of the MAP estimator, the a priori suspect set and its associated connectivity in the network bring about new ingredients to the problem. For this purpose, we propose to use local rumor center, which is a generalized concept based on the notion of rumor centrality, to identify the source from suspects. For regular tree-type networks with node degree δ, we characterize P c (n), the correct detection probability of the source estimator upon observing n infected nodes, in both the finite and asymptotic regimes. First, when the suspect set degenerates into the entirety of the network, so that every infected node belongs to the suspect set, lim n→∞ P c (n) grows from 0.25 to 0.307 as δ increases from three to infinity, a result first established in Zaman (2011, 2012) via a different approach with more mathematical machinery; furthermore, P c (n) monotonically decreases with n and increases with δ even in the finite-n regime. Second, when the suspect nodes form a connected subgraph of the network, lim n→∞ P c (n) significantly exceeds the a priori probability if δ ≥ 3, and reliable detection is achieved as δ becomes sufficiently large; furthermore, P c (n) monotonically decreases with n and increases with δ. Third, when there are only two suspect nodes, lim n→∞ P c (n) is at least 0.75 if δ ≥ 3; and P c (n) increases with the distance between the two suspects. Fourth, when there are multiple suspect nodes, among all possible connection patterns, that all the suspects form a single connected subgraph of the network achieves the smallest detection probability for the MAP source estimator. Our analysis leverages ideas from the Pólya'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.
al. also studied the problem of rooting the rumor source with the SI model and demonstrate similar results of asymptotic source detection probability on regular tree-type networks REF .
Rooting out the Rumor Culprit from Suspects
2013 IEEE International Symposium on Information Theory
2013 IEEE International Symposium on Information Theory
Computer Science Mathematics