We study the problem of locating the source of an epidemic diffusion process from a sparse set of sensors, under noise. In a graph $G=(V,E)$, an unknown source node $v^* in V$ is drawn uniformly at random, and unknown edge weights $w(e)$ for $ein E$, representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean $1$ and variance $sigma^2$. An algorithm then attempts to locate $v^*$ by picking sensor (also called query) nodes $s in V$ and being told the length of the shortest path between $s$ and $v^*$ in graph $G$ weighted by $w$. We consider two settings: static, in which all query nodes must be decided in advance, and sequential, in which each query can depend on the results of the previous ones. We characterize the query complexity when $G$ is an $n$-node path. In the static setting, $Theta(nsigma^2)$ queries are needed for $sigma^2 leq 1$, and $Theta(n)$ for $sigma^2 geq 1$. In the sequential setting, somewhat surprisingly, only $Theta(loglog_{1/sigma}n)$ are needed when $sigma^2 leq 1/2$, and $Theta(log log n)+O_sigma(1)$ when $sigma^2 geq 1/2$. This is the first mathematical study of source location under non-trivial amounts of noise.
تحميل البحث