Graph change-point detection problems have wide applications in graphical data types, such as social networks and sensor networks. Given a sequence of random graphs with fixed vertices and changing edges, we are interested in detecting a change that causes a shift in the distribution of a subgraph. We present two graph scanning statistics that can detect local changes in the distribution of edges in a subset of the graph. The first statistic assumes a parametric model, i.e., the observations on the edges are Gaussian random variables, and the change shifts the mean of a subgraph. We derive the scan statistic and present a theoretical approximation to the false alarm rate, which is verified to be accuracy numerically. The second statistic adopts a nonparametric approach based on k-Nearest Neighbors (k-NN). We demonstrate the efficiency of our detection statistics for ambient noise imaging, using a real dataset records real-time seismic signals around the Old Faithful Geyser in the Yellowstone National Park.
展开▼
