Rumor Source Detection with Multiple Observations : Fundamental Limits and Algorithms

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal

57 Scopus Citations
View graph of relations

Author(s)

  • Zhaoxu Wang
  • Wenxiang Dong
  • Wenyi Zhang
  • Chee Wei Tan

Detail(s)

Original languageEnglish
Pages (from-to)1-13
Journal / PublicationPerformance Evaluation Review
Volume42
Issue number1
Publication statusPublished - Jun 2014

Conference

Title2014 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2014)
PlaceUnited States
CityAustin
Period16 - 20 June 2014

Abstract

This paper addresses the problem of a single rumor source detection with multiple observations, from a statistical point of view of a spreading over a network, based on the susceptible-infectious model. For tree networks, multiple sequential observations for one single instance of rumor spreading cannot improve over the initial snapshot observation. The situation dramatically improves for multiple independent observations. We propose a unified inference framework based on the union rumor centrality, and provide explicit detection performance for degree-regular tree networks. Surprisingly, even with merely two observations, the detection probability at least doubles that of a single observation, and further approaches one, i.e., reliable detection, with increasing degree. This indicates that a richer diversity enhances detectability. For general graphs, a detection algorithm using a breadth-first search strategy is also proposed and evaluated. Besides rumor source detection, our results can be used in network forensics to combat recurring epidemic-like information spreading such as online anomaly and fraudulent email spams.

Research Area(s)

  • Graph networks, Inference algorithms, Maximum likelihood detection, Multiple observations, Rumor spreading

Citation Format(s)

Rumor Source Detection with Multiple Observations : Fundamental Limits and Algorithms. / Wang, Zhaoxu; Dong, Wenxiang; Zhang, Wenyi; Tan, Chee Wei.

In: Performance Evaluation Review, Vol. 42, No. 1, 06.2014, p. 1-13.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)22_Publication in policy or professional journal