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

Sam Spencer, Rayadurgam Srikant

Research output: Contribution to journalConference article

Abstract

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
Volume43
Issue number2
DOIs
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

Fingerprint

Identification (control systems)

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

On the impossibility of localizing multiple rumor sources in a line graph. / Spencer, Sam; Srikant, Rayadurgam.

In: Performance Evaluation Review, Vol. 43, No. 2, 2825262, 16.09.2015, p. 66-68.

Research output: Contribution to journalConference article

@article{2fb2e5f40dbf4edd8796b65dba59c1b8,
title = "On the impossibility of localizing multiple rumor sources in a line graph",
abstract = "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.",
author = "Sam Spencer and Rayadurgam Srikant",
year = "2015",
month = "9",
day = "16",
doi = "10.1145/2825236.2825262",
language = "English (US)",
volume = "43",
pages = "66--68",
journal = "Performance Evaluation Review",
issn = "0163-5999",
publisher = "Association for Computing Machinery (ACM)",
number = "2",

}

TY - JOUR

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

AU - Spencer, Sam

AU - Srikant, Rayadurgam

PY - 2015/9/16

Y1 - 2015/9/16

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84973377267&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84973377267&partnerID=8YFLogxK

U2 - 10.1145/2825236.2825262

DO - 10.1145/2825236.2825262

M3 - Conference article

AN - SCOPUS:84973377267

VL - 43

SP - 66

EP - 68

JO - Performance Evaluation Review

JF - Performance Evaluation Review

SN - 0163-5999

IS - 2

M1 - 2825262

ER -