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.

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.


Download paper here