# Subsampling Spectral Clustering for Large-Scale Social Networks

arXiv: https://arxiv.org/abs/2110.13613 · HTML: https://mlsanity.com/paper/2110.13613/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2021.

## Built on by (most cited first, 4 of 4)

- [Community detection by spectral methods in multi-layer networks](https://mlsanity.com/paper/2403.12540/) (2024)
- [Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton](https://mlsanity.com/paper/2502.13583/) (2025)
- [Model-free algorithms for fast node clustering in SBM type graphs and application to social role inference in animals](https://mlsanity.com/paper/2509.15989/) (2025)
- [A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation](https://mlsanity.com/paper/2609.09211/) (2026)

## Abstract (arXiv)

Online social network platforms such as Twitter and Sina Weibo have been extremely popular over the past 20 years. Identifying the network community of a social platform is essential to exploring and understanding the users' interests. However, the rapid development of science and technology has generated large amounts of social network data, creating great computational challenges for community detection in large-scale social networks. Here, we propose a novel subsampling spectral clustering algorithm to identify community structures in large-scale social networks with limited computing resources. More precisely, spectral clustering is conducted using only the information of a small subsample of the network nodes, resulting in a huge reduction in computational time. As a result, for large-scale datasets, the method can be realized even using a personal computer. Specifically, we introduce two different sampling techniques, namely simple random subsampling and degree corrected subsampling. The methodology is applied to the dataset collected from Sina Weibo, which is one of the largest Twitter-type social network platforms in China. Our method can very effectively identify the community structure of registered users. This community structure information can be applied to help Sina Weibo promote advertisements to target users and increase user activity.