Detection Thresholds for the $\beta$-Model on Sparse Graphs

Understand

In this paper we study sharp thresholds for detecting sparse signals in $\beta$-models for potentially sparse random graphs.

• The results demonstrate interesting interplay between graph sparsity, signal sparsity, and signal strength.
• In regimes of moderately dense signals, irrespective of graph sparsity, the detection thresholds mirror corresponding results in independent Gaussian sequence problems.
• For sparser signals, extreme graph sparsity implies that all tests are asymptotically powerless, irrespective of the signal strength.