Detecting small clusters in the stochastic block model

In the study of community detection, the stochastic block model (SBM) is frequently used as an ideal model. Many community detection strategies have been proposed and proved to be consistent under the SBM. However, almost all of these consistencies were established on the common assumption that all communities are balanced. When the communities are not balanced and some communities have small size, those strategies might be less efficient. In this paper, we consider the SBM with small clusters, under which the communities consist of several large clusters that have balanced sizes and some small clusters that have sizes of order smaller than the sizes of large clusters, and propose a two-step method to efficiently detect small clusters as well as the community structure of large clusters. In the first step, to get an initial estimator of the community structure, we treat the nodes in small clusters as outliers and utilize a robust community detecting method to classify the majority of nodes in large clusters correctly. In the second step, we pick out the nodes in small clusters using the entry-wise deviation, and update the community structure. We demonstrate that, under mild conditions, our method can consistently recover the large communities and identify each node in small clusters. Simulation results show that the proposed approach performs well whether the initial estimator is obtained by the semidefinite programming or the regularized spectral clustering. We also illustrate our method on real world networks.