Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 196/296 - Student Colloquium

Ery Arias-Castro

UCSD

Detection of an Abnormal Cluster in a Network

Abstract:

We consider the model problem of detecting whether or not in a given sensor network, there is a cluster of sensors which exhibit an unusual behavior. Formally, suppose we are given a set of nodes and attach a random variable to each node which represent the measurement that a particular sensor transmits. Under the normal circumstances, the variables have a standard normal distribution. Under abnormal circumstances, there is a cluster (subset of nodes) where the variables now have a positive mean. The cluster is unknown but restricted to belong to a class of interest, for example discrete squares.\\ We also address surveillance settings where each sensor in the network transmits information over time. The resulting model is similar, now with a time series is attached to each node. We consider some well-known examples of growth models, including cellular automata used to model epidemics.\\ In both settings, we study best possible detection rates under which no test works. We do so for a variety of cluster classes. In all the situations we consider, we show that the scan statistic, by far the most popular method in practice, is near-optimal.\\ Joint work with Emmanuel Candes (Stanford) and Arnaud Durand (Universit$\mathrm{\acute{e}}$ Paris XI)

November 17, 2009

11:00 AM

AP&M B412

****************************