Adaptive Subsampling Spectral Clustering Based on Second‐Order Neighbour Relationships for Sparse Networks

ABSTRACT Community detection is pivotal in social network analysis, with spectral clustering being a widely adopted method due to its theoretical robustness. However, traditional spectral clustering faces significant challenges in large‐scale sparse networks: high computational costs and reduced accuracy. Subsampling strategies, while mitigating computational demands, often suffer from structural information loss due to limited sample sizes. To address these issues, we propose a method called adaptive subsampling spectral clustering (ASSC). ASSC dynamically enriches the subsampled network by integrating second‐order neighbour relationships, thereby enhancing subgraph density without introducing hyperparameters. This approach leverages node influence weights to optimize the subsampling process, effectively preserving global structural patterns while reinforcing local connectivity. Experiments on simulation and real‐world datasets demonstrate that the clustering performance of ASSC significantly outperforms existing subsampling methods, with computational cost comparable to that of existing approaches. The proposed method provides a cost‐effective and robust solution for community detection in large‐scale sparse networks, balancing efficiency and accuracy.