Subsampling Based Community Detection in Large Networks

• Activity Number: 347 - Contributed Poster Presentations: Section on Statistical Computing
• Type: Contributed
• Date/Time: Tuesday, August 9, 2022 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Computing
• Author(s): Sayan Chakrabarty* and Srijan Sengupta and Yuguo Chen
• Companies: University of Illinois at Urbana Champaign and NCSU and University of Illinois at Urbana-Champaign
• Keywords: Community detection; Computational efficiency; Large network; Spectral clustering; Subsampling; Stochastic blockmodel

Abstract

Large networks are increasingly prevalent in scientific applications. Statistical analysis of such large networks become prohibitive due to exorbitant computation cost and high memory requirements. In this project, we develop a subsampling based divide-and-conquer algorithm, SONNET, for community detection in large networks. The algorithm splits the original network into multiple subnetworks with a common overlap and applies a suitable community detection algorithm on each subnetwork. The results from individual subnetworks are aggregated using a label matching method to get the final community labels. This method saves both memory and computation costs significantly as one needs to store and process only the smaller subnetworks. This method is also parallelizable. We derive a theoretical upper bound for the error rate of SONNET applied with any community detection algorithm. We also specialize the bound when SONNET is applied with spectral clustering on a stochastic blockmodel (SBM) and with spherical K-median spectral clustering on a degree corrected blockmodel (DCBM). We demonstrate the effectiveness of SONNET on a real-world network and on networks simulated from SBM and DCBM.