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

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. (c) 2023 Elsevier B.V. All rights reserved.

Automated summary

This study proposes a subsampling spectral clustering algorithm to address the computational challenges of large-scale network data. By constructing a subnetwork through simple random subsampling and extending the spectral clustering method, the algorithm can identify community structures in the entire network with limited computing resources. The method also has the potential for parallelization and theoretical properties are established under the stochastic block model.