Diffusion source detection in a network using partial observations

Roxana Alexandru; Pier Luigi Dragotti

doi:10.1117/12.2529418

9 September 2019 Diffusion source detection in a network using partial observations

Proceedings Volume 11138, Wavelets and Sparsity XVIII; 111380L (2019) https://doi.org/10.1117/12.2529418
Event: SPIE Optical Engineering + Applications, 2019, San Diego, California, United States

Abstract

Diffusive phenomena are ubiquitous in nature and society, and have been extensively studied in various fields, such as natural sciences and engineering. Recently, however, the more challenging inverse problem of diffusion source detection in a network has started to receive a significant amount of attention. A lot of research has concentrated on finding origins in tree-like networks, however these approaches cannot be easily extended to generic networks. Furthermore, only some methods consider realistic temporal diffusion dynamics. We introduce a novel method to localise the source of multiple rumours in an arbitrary network of known topology, using partial observations of the network nodes. We first present two mathematical models of the discrete-time, susceptible infected propagation dynamics, which accurately capture the diffusion process and have low computational complexity. The first one is a simplified likelihood of infection at a node, at a certain time after the rumour is initiated. The second is a formulation of the infection likelihood of a node, as a function of its shortest distance to the source. We then design an efficient single source detection algorithm, which leverages these mathematical models of diffusion, and the assumption that the start time of the propagation is known. Finally, we show how these methods can be extended to the case when the start time of the rumour is unknown, by taking advantage of the dissimilarity in dynamics of infection, of different nodes in the network. Simulation results show that a high source estimation probability is achieved using a small number of observations.

Citation Download Citation

Roxana Alexandru and Pier Luigi Dragotti "Diffusion source detection in a network using partial observations", Proc. SPIE 11138, Wavelets and Sparsity XVIII, 111380L (9 September 2019); https://doi.org/10.1117/12.2529418

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