On the impossibility of localizing multiple rumor sources in a line graph

Sam Spencer, Rayadurgam Srikant

Research output: Contribution to journalConference articlepeer-review


Here we examine the problem of rumor source identification in line graphs. We assume the SI model for rumor propagation with exponential waiting times. We consider the case where a rumor originates from two sources simultaneously, and evaluate the likelihood function for the given observations given those sources. As the size of the infected region grows arbitrarily large, we show that unlike the single source case, where the likelihood function concentrates near the midpoint of the infected region, the support of the likelihood function in this case remains widely distributed over the middle half of the infected region. This makes the rumor sources impossible to localize with high probability on any scale smaller than that of the infection size itself.

Original languageEnglish (US)
Article number2825262
Pages (from-to)66-68
Number of pages3
JournalPerformance Evaluation Review
Issue number2
StatePublished - Sep 16 2015
Event33rd International Symposium on Computer Performance, Modeling, Measurement, and Evaluation, IFIP WG 7.3 Performance 2015 - Sydney, Australia
Duration: Oct 19 2015Oct 21 2015

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this