On Detecting Epidemics from Weak Signatures

Tuesday, October 20, 2015 - 11:30am - 12:20pm
Keller 3-180
Shie Mannor (Technion-Israel Institute of Technology)
We consider the problem of detecting epidemics in graphs when the indication if a node is infected
is extremely noisy. We show that with even overwhelming noise the structure of the network can still
be used to detect epidemics. Our approach uses local algorithms for detection and only a fairly
loose information about the network structure is needed. Our analysis relies on percolation theory and
tools from analysis of extreme events of diffusion processes over graphs.

The motivation to this work comes, for instance, when the only signature of a worm infecting a
neighboring network node is a (rarely occurring) temporally-localized increased processor and
network load (when the worm is actively spreading from one node to its neighbor). However,
many other benign activities have a similar signature; further these benign activities occur
frequently (as opposed to the rare occurrence of a worm infection). While it is impossible to
distinguish between an infection incidence and a benign activity merely from observing a single
node, we show that the spread itself can be used as a global signature of epidemic spread, and
thus we can reliably distinguish between these two hypotheses (epidemic / benign activity).
MSC Code: