|
Abstract:
|
We will discuss the detection of patterns in networks hidden within white noise. We focus on the detection of patterns that have a small cut size within the graph. The natural generalized likelihood ratio test (GLRT) is a combinatorial optimization that lies within an NP-hard class. To this end, we propose and analyze approximation algorithms that are computationally efficient variants of the GLRT. Four methods will be reviewed and compared: Graph Fourier scan statistic, spanning tree Haar wavelet basis, the Lovasz extended scan statistic, and a multiscale scan statistic. The theoretical statistical performance of these methods will be related to various notions of connectivity within the graph, such as the spectrum of the Laplacian, the effective resistances of the edges, and the number of connected components. Also, the computational complexity of these scan statistics will be discussed and empirically compared.
|
