Title: Using Maximum Entry-Wise Deviation to Test the Goodness-of-Fit for Stochastic Block Models,
Abstract: The stochastic block model is widely used for detecting community structures
in network data. How to test the goodness-of-fit of the model is one of the
fundamental problems and has gained growing interests in recent years. In this
paper, we propose a novel goodness-of-fit test based on the maximum entry of
the centered and re-scaled adjacency matrix for the stochastic block model. One
noticeable advantage of the proposed test is that the number of communities can
be allowed to grow linearly with the number of nodes ignoring a logarithmic
factor. We prove that the null distribution of the test statistic converges in
distribution to a Gumbel distribution, and we show that both the number of
communities and the membership vector can be tested via the proposed method.
Further, we show that the proposed test has asymptotic power guarantee against
a class of alternatives. We also demonstrate that the proposed method can be
extended to the degree-corrected stochastic block model. Both simulation
studies and real-world data examples indicate that the proposed method works
well.