A fast Monte Carlo algorithm for source localization on graphs

Ameya Agaskar; Yue M. Lu

doi:10.1117/12.2023039

26 September 2013 A fast Monte Carlo algorithm for source localization on graphs

Ameya Agaskar, Yue M. Lu

Proceedings Volume 8858, Wavelets and Sparsity XV; 88581N (2013) https://doi.org/10.1117/12.2023039
Event: SPIE Optical Engineering + Applications, 2013, San Diego, California, United States

Abstract

Epidemic models on networks have long been studied by biologists and social sciences to determine the steady state levels of an infection on a network. Recently, however, several authors have begun considering the more difficult problem of estimating the source of an infection given information about its behavior some time after the initial infection. In this paper, we describe a technique to estimate the source of an infection on a general graph based on observations from a small set of observers during a fixed time window at some unknown time after the initial infection. We describe an alternate representation for the susceptible-infected (SI) infection model based on geodesic distances on a randomly-weighted version of the graph; this representation allows us to exploit fast algorithms to compute geodesic distances to estimate the marginal distributions for each observer and compute a pseudo-likelihood function that is maximized to find the source.

Citation Download Citation

Ameya Agaskar and Yue M. Lu "A fast Monte Carlo algorithm for source localization on graphs", Proc. SPIE 8858, Wavelets and Sparsity XV, 88581N (26 September 2013); https://doi.org/10.1117/12.2023039

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available