If it spreads it can't hide: detecting epidemics from weak signatures

Professor Constantine Caramanis
Associate Professor, University of Texas at Austin
Given on: Feb. 19th, 2015
Venue: Packard 101
Time: 4:15pm to 5:15pm


Last week, Sanjay Shakkottai (UT Austin) talked about how external agents affect spreading properties of an epidemic – a prediction or “forward” problem. This talk is about “inverse” problems – what explains what we are seeing? In particular, is it an epidemic?

Specifically, we ask: can we (early) detect the spread of a new disease, or of a new kind of malware, one whose properties have not been studied, and characteristics not yet identified? We consider the problem of detecting an infection process in a network when the indication that any particular node is infected is extremely noisy – statistically indistinguishable from everyday behavior.

Such a scenario occurs, 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). In addition, we explore how graph topology impacts our ability to do early detection.

Based on joint with work Chris Milling, Eli Meirom, Sanjay Shakkottai, Shie Mannor and Ariel Orda.


Constantine Caramanis received the A.B. degree in Mathematics from Harvard University, and the MS and Ph.D. degrees from MIT. He is currently an Associate Professor in the Department of Electrical and Computer Engineering at UT Austin. He received the NSF CAREER award in 2011. His current research interests include optimization and large-scale inference, computation and decision-making in large-scale systems.