Cluster Detection Using Percolation

• Activity Number: 281
• Type: Invited
• Date/Time: Tuesday, August 2, 2011 : 8:30 AM to 10:20 AM
• Sponsor: IMS
• Author(s): Ery Arias-Castro*+ and Geoffrey R. Grimmett
• Companies: University of California at San Diego and University of Cambridge
• Keywords: cluster detection ; surveillance ; scan statistic ; percolation theory ; multiple hypothesis testing

Abstract

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), which consists in scanning the connected components after thresholding.  We establish their performance in an asymptotic decision theoretic framework where the network size increases to infinity, both in the context of parametric and nonparametric classes of clusters.  Percolation theory is at the base of our theoretical results, which are complemented by some numerical experiments.