Statistics and Its Interface

Volume 17 (2024)

Number 2

Special issue on statistical learning of tensor data

A random projection method for large-scale community detection

Pages: 159 – 172

DOI: https://dx.doi.org/10.4310/22-SII752

Authors

Haobo Qi (Guanghua School of Management, Peking University, Beijing, China)

Hansheng Wang (Guanghua School of Management, Peking University, Beijing, China)

Xuening Zhu (School of Data Science, Fudan University, Shanghai, China)

Abstract

In this work, we consider a random projection method for a large-scale community detection task. We introduce a random Gaussian matrix that generates several projections on the column space of the network adjacency matrix. The $k$-means algorithm is then applied with the low-dimensional projected matrix. The computational complexity is much lower than that of the classic spectral clustering methods. Furthermore, the algorithm is easy to implement and accessible for privacy preservation. We can theoretically establish a strong consistency result of the algorithm under the stochastic block model. Extensive numerical studies are conducted to verify the theoretical findings and illustrate the usefulness of the proposed method.

Keywords

community detection, large scale network, random projection, stochastic block model

Full Text (PDF format)

Haobo Qi and Hansheng Wang are supported by National Natural Science Foundation of China (NSFC, 11831008). Xuening Zhu’s research is supported by the National Natural Science Foundation of China (nos. 72222009, 11901105, 71991472, U1811461).

Received 5 December 2021

Accepted 5 August 2022

Published 1 February 2024