Detecting abrupt changes in the community structure of a network from noisy observations is a fundamental problem in statistics and machine learning. This paper presents an online change detection algorithm called Spectral-CUSUM to detect unknown network structure changes through a generalized likelihood ratio statistic. We characterize the average run length (ARL) and the expected detection delay (EDD) of the Spectral-CUSUM procedure and prove its asymptotic optimality. Finally, we demonstrate the good performance of the Spectral-CUSUM procedure and compare it with several baseline methods using simulations and real data examples on seismic event detection using sensor network data.
翻译:从噪音观测中检测到网络社区结构突然变化是统计和机器学习的根本问题。本文展示了名为Spectral-CUSUM的在线变化探测算法,以通过普遍可能性比率统计探测未知的网络结构变化。我们用传感器网络数据模拟和地震事件探测实际数据实例来描述光谱-CUSUUM程序的平均运行长度和预期的检测延迟(EDD),并证明其无症状的最佳性。最后,我们展示了光谱-CUSUUM程序的良好性能,并将其与若干基线方法进行比较。