### 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 language | English (US) |
---|---|

Article number | 2825262 |

Pages (from-to) | 66-68 |

Number of pages | 3 |

Journal | Performance Evaluation Review |

Volume | 43 |

Issue number | 2 |

DOIs | |

State | Published - Sep 16 2015 |

Event | 33rd International Symposium on Computer Performance, Modeling, Measurement, and Evaluation, IFIP WG 7.3 Performance 2015 - Sydney, Australia Duration: Oct 19 2015 → Oct 21 2015 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Hardware and Architecture
- Computer Networks and Communications

### Cite this

*Performance Evaluation Review*,

*43*(2), 66-68. [2825262]. https://doi.org/10.1145/2825236.2825262

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

Research output: Contribution to journal › Conference article

*Performance Evaluation Review*, vol. 43, no. 2, 2825262, pp. 66-68. https://doi.org/10.1145/2825236.2825262

}

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 -