Subsampling spectral clustering for stochastic block models in large-scale networks

Deng，Jiayi1; Huang，Danyang1; Ding，Yi1; Zhu，Yingqiu2; Jing，Bingyi3; Zhang，Bo1

2024

10.1016/j.csda.2023.107835

Computational Statistics and Data Analysis   Impact Factor & Quartile

0167-9473

The rapid development of science and technology has generated large amounts of network data, leading to significant computational challenges for network community detection. A novel subsampling spectral clustering algorithm is proposed to address this issue, which aims to identify community structures in large-scale networks with limited computing resources. The algorithm constructs a subnetwork by simple random subsampling from the entire network, and then extends the existing spectral clustering to the subnetwork to estimate the community labels for entire network nodes. As a result, for large-scale datasets, the method can be realized even using a personal computer. Moreover, the proposed method can be generalized in a parallel way. Theoretically, under the stochastic block model and its extension, the degree-corrected stochastic block model, the theoretical properties of the subsampling spectral clustering method are correspondingly established. Finally, to illustrate and evaluate the proposed method, a number of simulation studies and two real data analyses are conducted.

Community detection Large-scale networks Network subsampling Spectral clustering Stochastic block model

English

Others

National Natural Science Foundation of China[11701560];National Natural Science Foundation of China[12071477];National Natural Science Foundation of China[71873137];National Natural Science Foundation of China[72271232];

MATHEMATICS

2-s2.0-85170288208

Scopus

1.Center for Applied Statistics,School of Statistics,Renmin University of China,Beijing,China
2.School of Statistics,University of International Business and Economics,China
3.Department of Statistics and Data Science,Southern University of Science and Technology,China

Deng，Jiayi,Huang，Danyang,Ding，Yi,et al. Subsampling spectral clustering for stochastic block models in large-scale networks[J]. Computational Statistics and Data Analysis,2024,189.

Deng，Jiayi,Huang，Danyang,Ding，Yi,Zhu，Yingqiu,Jing，Bingyi,&Zhang，Bo.(2024).Subsampling spectral clustering for stochastic block models in large-scale networks.Computational Statistics and Data Analysis,189.

Deng，Jiayi,et al."Subsampling spectral clustering for stochastic block models in large-scale networks".Computational Statistics and Data Analysis 189(2024).