B0564
Title: Testing degree corrections in stochastic block models
Authors: Subhabrata Sen - Microsoft Research (United States)
Rajarshi Mukherjee - Harvard T.H. Chan School of Public Health (United States) [presenting]
Abstract: Thresholds for degree corrections in Stochastic Block Models are studied in the context of a goodness of fit problem. When degree corrections are relatively dense, a simple test based on the total number of edges is asymptotically optimal. For sparse degree corrections in non-dense graphs, simple degree based Higher Criticism Test is optimal with sharp constants. In contrast, for dense graphs, the optimal procedure runs in two stages. It involves running a suitable community recovery algorithm in stage 1, followed by a Higher Criticism Test based on a linear combination of within and across (estimated) community degrees in stage 2. The necessity of the two-step procedure is demonstrated by the failure of the ordinary Maximum Degree Test in achieving sharp constants. As necessary tools, we also derive asymptotic distribution of the Maximum Degree in Stochastic Block Models along with moderate deviation and local central limit type asymptotics of positive linear combinations of independent Binomial random variables.
Journal