Abstract:
|
In this talk, we discuss optimal hypothesis testing for distinguishing a stochastic block model from an Erdos-Renyi random graph. We derive central limit theorems for a collection of linear spectral statistics under both the null and local alternatives. In addition, we show that linear spectral statistics based on Chebyshev polynomials can be used to approximate signed cycles of growing lengths which in turn determine the likelihood ratio test asymptotically when the graph size and the average degree grow to infinity together. Therefore, one achieves sharp asymptotic optimal power of the testing problem within polynomial time complexity.
|