A path algorithm for localizing anomalous activity in graphs

The localization of anomalous activity in graphs is a statistical problem that arises in many applications, such as network surveillance, disease outbreak detection, and activity monitoring in social networks. We will address the localization of a cluster of activity in Gaussian noise in directed, weighted graphs. We develop a penalized likelihood estimator (we call the relaxed graph scan) as a relaxation of the NP-hard graph scan statistic. We review how the relaxed graph scan (RGS) can be solved using graph cuts, and outline the max-flow min-cut duality. We use this combinatorial duality to derive a path algorithm for the RGS by solving successive max flows. We demonstrate the effectiveness of the RGS on two simulations, over an undirected and directed graph.