An Investigation of Locality Region for Scan Statistics in a Time Series of Graphs

• Activity Number: 417
• Type: Contributed
• Date/Time: Tuesday, August 3, 2010 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistics in Defense and National Security
• Author(s): Kristin Ash*+ and David J. Marchette and Carey E. Priebe
• Companies: Naval Surface Warfare Center and Naval Surface Warfare Center and The Johns Hopkins University
• Keywords: scan statistic ; graph time series ; random graph ; locality statistic ; stochastic model

Abstract

Scan statistics provide a means of discovering changes and anomalies in a time series of graphs. Given a locality statistic (in our case the size of the induced subgraph of N[v], the neighborhood at a vertex), the scan statistic is the maximum locality statistic for a given graph. Taking a window of time W up to current time, we consider four of the possible definitions of neighborhood over a time series of graphs: N[v] in the current graph; N[v] in the current graph applied to each graph in W; the union and intersection of all N[v] in W. Each method has power under different assumptions. We compare these in a simple change point detection problem: the detection of a small anomalous region. We discuss a stochastic model for the generation of a time series of random graphs and explore the performance of the different neighborhood approaches as a function of the parameters of the model.