Budgeted sensor placement for source localization on trees

https://doi.org/10.1016/j.endm.2015.07.012Get rights and content

Abstract

We address the problem of choosing a fixed number of sensor vertices in a graph in order to detect the source of a partially-observed diffusion process on the graph itself. Building on the definition of double resolvability we introduce a notion of vertex resolvability. For the case of tree graphs we give polynomial time algorithms for both finding the sensors that maximize the probability of correct detection of the source and for identifying the sensor set that minimizes the expected distance between the real source and the estimated one.

References (5)

  • D. Shah et al.

    Rumors in a network: who's the culprit?

    IEEE Transactions on information theory

    (2011)
  • P. Pinto et al.

    Locating the Source of Diffusion in Large-Scale Networks

    Physical Review Letters

    (2012)
There are more references available in the full text version of this article.

Cited by (0)

1

The work has been done during the author's enrollment in the Faculty of Electrical Engineering and Computing, University of Zagreb, Croatia and prior to the current employment by Google Switzerland GmbH.

2

The author was supported in part by the Bill and Melinda Gates Foundation, under Grant No. OPP1070273.

View full text