Paper Info
Title
Observer Placement for Source Localization: The Effect of Budgets and Transmission Variance.
Abstract
When an epidemic spreads in a network, a key question is where was its source, i.e., the node that started the epidemic. If we know the time at which various nodes were infected, we can attempt to use this information in order to identify the source. However, maintaining observer nodes that can provide their infection time may be costly, and we may have a budget k on the number of observer nodes we can maintain. Moreover, some nodes are more informative than others due to their location in the network. Hence, a pertinent question arises: Which nodes should we select as observers in order to maximize the probability that we can accurately identify the source? Inspired by the simple setting in which the node-to-node delays in the transmission of the epidemic are deterministic, we develop a principled approach for addressing the problem even when transmission delays are random. We show that the optimal observer-placement differs depending on the variance of the transmission delays and propose approaches in both low-and high-variance settings. We validate our methods by comparing them against state-of-the-art observer-placements and show that, in both settings, our approach identifies the source with higher accuracy.
Year
DOI
Venue
2016
10.1109/ALLERTON.2016.7852307
2016 54TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON)
DocType
Volume
ISSN
Conference
abs/1608.04567
2474-0195
Citations 
PageRank 
References 
1
0.35
20
Authors
3
Name
Order
Citations
PageRank
Brunella Spinelli171.18
L. Elisa Celis26514.72
Patrick Thiran32712217.24