Detecting small clusters in the stochastic block model

Fei Ye (), Jingsong Xiao (), Weidong Ma (), Shiwen Jin () and Ying Yang ()
Additional contact information
Fei Ye: Capital University of Economics and Business
Jingsong Xiao: Tsinghua University
Weidong Ma: Tsinghua University
Shiwen Jin: Tsinghua University
Ying Yang: Tsinghua University

Statistical Papers, 2025, vol. 66, issue 2, No 7, 34 pages

Abstract: Abstract 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.

Keywords: Stochastic block model; Community detection; Small clusters; Outlier detection; 62H30 (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00362-025-01660-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:stpapr:v:66:y:2025:i:2:d:10.1007_s00362-025-01660-7

Ordering information: This journal article can be ordered from
http://www.springer. ... business/journal/362

DOI: 10.1007/s00362-025-01660-7

Access Statistics for this article

Statistical Papers is currently edited by C. Müller, W. Krämer and W.G. Müller

More articles in Statistical Papers from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().