Optimality of Graph Scanning Statistic for Online Community Detection

Sequential change detection for graphs is a fundamental problem for streaming network data and has wide applications in social networks and power systems. Given fixed vertices and a sequence of random graphs, the objective is to detect the change-point where the underlying distribution of the random graph changes. In particular, we focus on the local change that only affects a small subgraph. We adopt the classical Erdős-Rényi model and revisit the generalized likelihood ratio (GLR) procedure. The scan statistic is computed by sequentially estimating the most-likely subgraph where the change happens. We provide theoretical analysis for the asymptotic optimality of the proposed procedure and we comment on generalizations to other random graph models. We demonstrate the efficiency of our detection algorithm using simulations.