22 Abril 2016, 16:08 - Maria João Silva Carvalho
Candidato: Sabina Zejnilovic (CMU-PT ECE)
Título: Localizing a diffusion source on graphs: analysis and design of node selection strategies
Terça-feira, 26 de Abril, 17:00, Torre norte, sala 4.12 (videoconferência com a CMU)
Abstract: Many different phenomena, such as spreading of infectious diseases in networks and dissemination of information through social networks are modeled as a diffusion over a network of nodes. Localizing the source of diffusion becomes crucial for quarantine efforts, as well as for identifying influential individuals who start certain trends. In many real world networks, due to their size, it is unfeasible to observe the infection times of all nodes. In this case, identification of the source node is carried out based only on a subset of nodes, called observer nodes. The choice of observer nodes heavily impacts the accuracy of source localization.
In this thesis we specifically focus on the analysis and design of observer selection strategies with the goal of understanding which are the best nodes to observe that contribute the most to the disambiguation of the source on graphs for different diffusion scenarios. We introduce and study the concept of network observability which characterizes the ability to identify the source node based only on partial network knowledge, provided by the observer nodes. There are four main contributions of our work:
- We study the effect of the choice of observers on source localization when there is no uncertainty present - in a purely deterministic scenario. We model the dynamics of network diffusion as a linear time-varying system, and present a necessary and sufficient condition for network observability in the context of the proposed model, as well as in the context of graph theory. Relating the observer selection problem to a known problem of finding a resolving set of a graph, we design observer selection strategies with performance guarantees.
- We extend the concept of observability for the scenario when the network topology is not fully known and the edges between different communities are hidden. We present necessary and sufficient conditions for network observability when the components are all trees, cycles, grids and complete graphs. We also give sufficient conditions when the components are of arbitrary structure.
- We formulate a metric, based on error exponents, that can be used to compare different observer subsets from the perspective of source localization error. We evaluate the error exponent for vanishing noise for three different diffusion scenarios; in each, the infection times are modeled as random variables with different distributions: Gaussian, Laplace and exponential.
- We develop different sequential selection strategies, optimal and sub-optimal, for dynamic observer selection in both deterministic and stochastic setting, and demonstrate the applicability of one of the proposed strategies on a real-world dataset of a cholera outbreak.