Detection of an anomalous cluster in a network

Abstract

We consider the problem of detecting whether or not, in a given sensor network, there is a cluster of sensors which exhibit an "unusual behavior." Formally, suppose we are given a set of nodes and attach a random variable to each node. We observe a realization of this process and want to decide between the following two hypotheses: under the null, the variables are i.i.d. standard normal; under the alternative, there is a cluster of variables that are i.i.d. normal with positive mean and unit variance, while the rest are i.i.d. standard normal. We also address surveillance settings where each sensor in the network collects information over time. The resulting model is similar, now with a time series attached to each node. We again observe the process over time and want to decide between the null, where all the variables are i.i.d. standard normal, and the alternative, where there is an emerging cluster of i.i.d. normal variables with positive mean and unit variance. The growth models used to represent the emerging cluster are quite general and, in particular, include cellular automata used in modeling epidemics. In both settings, we consider classes of clusters that are quite general, for which we obtain a lower bound on their respective minimax detection rate and show that some form of scan statistic, by far the most popular method in practice, achieves that same rate to within a logarithmic factor. Our results are not limited to the normal location model, but generalize to any one-parameter exponential family when the anomalous clusters are large enough.

Published in at http://dx.doi.org/10.1214/10-AOS839 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (8)

• Detection of an anomalous cluster in a network
• Innovated higher criticism for detecting sparse signals in correlated noise
• Searching for a trail of evidence in a maze
• Optimal and fast detection of spatial clusters with scan statistics
• On combinatorial testing problems
• Properties of higher criticism under strong dependence
• Adaptive multiscale detection of filamentary structures in a background of uniform random points
• Random growth models with polygonal shapes

Cited by in corpus (58)

• Optimal detection of sparse principal components in high dimension
• Detection of an anomalous cluster in a network
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Higher Criticism for Large-Scale Inference, Especially for Rare and Weak Effects
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Computational Lower Bounds for Sparse PCA
• Computational Barriers to Estimation from Low-Degree Polynomials
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Testing for Global Network Structure Using Small Subgraph Statistics
• Detection of correlations
• Finding Hidden Cliques of Size \sqrt{N/e} in Nearly Linear Time
• Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix
• Cluster detection in networks using percolation
• Nonparametric Detection of Geometric Structures over Networks
• Robust Sparse Estimation Tasks in High Dimensions
• Efficient Minimax Signal Detection on Graphs
• Data segmentation algorithms: Univariate mean change and beyond
• Approximate $l_0$-penalized estimation of piecewise-constant signals on graphs
• Energy Landscape for large average submatrix detection problems in Gaussian random matrices
• Dual Averaging Method for Online Graph-structured Sparsity
• Detecting Localized Categorical Attributes on Graphs
• Stochastic Iterative Hard Thresholding for Graph-structured Sparsity Optimization
• Spatial statistics, image analysis and percolation theory
• Identifying the Support of Rectangular Signals in Gaussian Noise
• Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
• Adaptive Inferential Method for Monotone Graph Invariants
• Calibrating the scan statistic: finite sample performance vs. asymptotics
• Quickest Detection of Dynamic Events in Networks
• Fast Path Localization on Graphs via Multiscale Viterbi Decoding
• Anomaly Detection for a Large Number of Streams: A Permutation-Based Higher Criticism Approach
• Quarantines as a Targeted Immunization Strategy
• Removing Malicious Nodes from Networks
• Moving sum data segmentation for stochastics processes based on invariance
• Lattice partition recovery with dyadic CART
• Distribution-Free Detection of Structured Anomalies: Permutation and Rank-Based Scans
• Local Two-Sample Testing over Graphs and Point-Clouds by Random-Walk Distributions
• Template Matching and Change Point Detection by M-estimation
• Stochastic Hard Thresholding Algorithms for AUC Maximization
• Technical Report: A Generalized Matching Pursuit Approach for Graph-Structured Sparsity
• Detecting Anomalous Activity on Networks with the Graph Fourier Scan Statistic
• Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies
• Learning Mixtures of Graphs from Epidemic Cascades
• A Kernel-Based Nonparametric Test for Anomaly Detection over Line Networks
• Optimal partition recovery in general graphs
• Sparse Anomaly Detection Across Referentials: A Rank-Based Higher Criticism Approach
• Compressed Hypothesis Testing: To Mix or Not to Mix?
• Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs
• Minimax rates for sparse signal detection under correlation
• Sharp Signal Detection Under Ferromagnetic Ising Models
• Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets
• Asymptotic convergence rate of the longest run in an inflating Bernoulli net
• Distributionally Robust Removal of Malicious Nodes from Networks
• Global testing under the sparse alternatives for single index models
• Fast and Asymptotically Powerful Detection for Filamentary Objects in Digital Images
• Finding Differentially Covarying Needles in a Temporally Evolving Haystack: A Scan Statistics Perspective
• Adaptive nonparametric detection in cryo-electron microscopy