Title: Testing Degree Corrections in Stochastic Block Models,
Abstract: We study sharp detection thresholds for degree corrections in Stochastic
Block Models 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 (Mukherjee, Mukherjee, Sen
2016) 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.