Scan statistics on graphs and networks
Published in Handbook of Scan Statistics, 2017
Recommended citation: Zhang, P. and Glaz, J. (2018). "Scan statistics on graphs and networks." In Glaz, J. and Koutras, M. V. (Eds.) Handbook of Scan Statistics. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-8414-1_43-1
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.