Two-Sample Test for Stochastic Block Models via Maximum Entry-wise Deviation

Stochastic block model is a popular tool for detecting community structures in network data. How to detect the difference of the community structures is an important issue for stochastic block models. However, two--sample test has been a largely under explored domain, and too little work has been devoted to it. In this article, based on maximum entry--wise deviation of the two centered and rescaled adjacency matrices, we propose a novel test statistic to test two samples of stochastic block models. We prove that the null distribution of the proposed test statistic converges in distribution to a Gumbel distribution, and we show the change of the two samples for stochastic block models can be tested via the proposed method. Further, we show that the proposed test has asymptotic power guarantee against alternative models. One noticeable advantage of the proposed test statistic is that the number of communities can be allowed to grow linearly up to a logarithmic factor. Both simulation studies and real-world data examples indicate that the proposed method works well.