Detection of an anomalous cluster in a network

This work considers the problem of detecting whether or not in a given sensor network, there is a cluster of sensors which exhibit an "unusual behavior", and considers classes of clusters that are quite general, for which a lower bound is obtained on their respective minimax detection rate.

Abstract

We consider the problem of detecting whether or not, in a given sensor\nnetwork, there is a cluster of sensors which exhibit an "unusual behavior."\nFormally, suppose we are given a set of nodes and attach a random variable to\neach node. We observe a realization of this process and want to decide between\nthe following two hypotheses: under the null, the variables are i.i.d. standard\nnormal; under the alternative, there is a cluster of variables that are i.i.d.\nnormal with positive mean and unit variance, while the rest are i.i.d. standard\nnormal. We also address surveillance settings where each sensor in the network\ncollects information over time. The resulting model is similar, now with a time\nseries attached to each node. We again observe the process over time and want\nto decide between the null, where all the variables are i.i.d. standard normal,\nand the alternative, where there is an emerging cluster of i.i.d. normal\nvariables with positive mean and unit variance. The growth models used to\nrepresent the emerging cluster are quite general and, in particular, include\ncellular automata used in modeling epidemics. In both settings, we consider\nclasses of clusters that are quite general, for which we obtain a lower bound\non their respective minimax detection rate and show that some form of scan\nstatistic, by far the most popular method in practice, achieves that same rate\nto within a logarithmic factor. Our results are not limited to the normal\nlocation model, but generalize to any one-parameter exponential family when the\nanomalous clusters are large enough.\n