Optimal hypothesis testing for stochastic block models with growing degrees

Understand

The present paper considers testing an Erdos--Renyi random graph model against a stochastic block model in the asymptotic regime where the average degree of the graph grows with the graph size n.

• Our primary interest lies in those cases in which the signal-to-noise ratio is at a constant level.
• Focusing on symmetric two block alternatives, we first derive joint central limit theorems for linear spectral statistics of power functions for properly rescaled graph adjacency matrices under both the null and local alternative hypotheses.
• The powers in the linear spectral statistics are allowed to grow to infinity together with the graph size.