Scan Statistics on Graphs and Networks

This article summarizes modern research of scan statistics on graphs and networks. These statistics arise naturally in the scanning of time and space looking for clusters of anomalous entities or events. We review theories and methodologies of constructing scan statistics for both static and dynamic graphs, in both purely spatial and spatio temporal frameworks. Computation of graph-structured scan statistics is challenging, and usually leads to NP-hard problems. We also review several popular convex approximation algorithms for computing scan statistics in this article.