Percolation-based methods for the detection of clusters in networks

We consider the task of detecting a salient cluster in a (sensor) network, which we model as an undirected graph with a random variable attached to each node. Motivated by recent research in environmental statistics and the drive to compete with the reigning scan statistic, we explore alternative methods based on the percolative properties of the network. The first method is based on the size of the largest connected component after removing the nodes in the network whose value is lower than a given threshold. The second one is the upper level set scan test introduced by Patil and Taillie (2003). We establish their performance in an asymptotic decision theoretic framework where the network size increases to infinity. We make abundant use of percolation theory to derive our theoretical results and our theory is complemented with some numerical experiments.
(Joint work with G. Grimmett.)