All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD1-S6-T3.1
Paper Title Optimality of Graph Scanning Statistic for Online Community Detection
Authors Liyan Xie, Yao Xie, Georgia Institute of Technology, United States
Session D1-S6-T3: Inference in Graphical Models
Chaired Session: Monday, 12 July, 23:40 - 00:00
Engagement Session: Tuesday, 13 July, 00:00 - 00:20
Abstract 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\H{o}s-R\'enyi 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.