Seminar Details
2018-04-24 (14:00) : Locating the source of diffusion in large-scale and random networks
At Maxwell building, Shannon room
Organized by Mathematical Engineering
Speaker :
Thiran, Patrick
Abstract :
We will survey some results on the localization of the source of diffusion in a network. There have been significant efforts in studying the dynamics of epidemic propagations on networks, and more particularly on the forward problem of epidemics: understanding the diffusion process and its dependence on the infecting and curing rates. We address here the inverse problem of inferring the original source of diffusion, given the infection data gathered at some of the nodes in the network. Indeed, because of the large size of many real networks, the state of all nodes in a network cannot in general be observed. We show that it is fundamentally possible to estimate the location of the source from measurements collected by sparsely placed observers. We present a strategy that is optimal for arbitrary trees, achieving maximum probability of correct localization, and describe efficient implementations for arbitrary graphs. When propagation times are (close to) deterministic values, the smallest number of sensors needed to exactly localize the source is the double metric dimension of the network. We compute tight bounds for this quantity in a number of topologies that include Erdös-Renyi random graphs, and we comment on its implications for the detectability of a source in actual networks.
This is a joint work with Elisa Celis, Pedro Pinto, Brunella Spinelli and Martin Vetterli.