Scalable Community Detection in Massive Networks via Predictive Assignment

• 成果类型: Article; Early Access
• 署名作者: Bhadra, Subhankar; Pensky, Marianna; Sengupta, Srijan
• 署名单位: Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; State University System of Florida; University of Central Florida; North Carolina State University
• 刊物名称: JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION
• ISSN/ISSBN: 0162-1459; 1537-274X
• DOI: 10.1080/01621459.2026.2628341
• 发表日期: 2026-06-20
• 关键词: Bias-adjusted spectral clustering; computational efficiency; Degree corrected stochastic block model; Scalable inference; Spectral Clustering; stochastic block model; OF-SAMPLE EXTENSIONS; adjacency; Consistency

摘要

Massive network datasets are becoming increasingly common in scientific applications. Existing community detection methods encounter significant computational challenges for such massive networks due to two reasons. First, the full network needs to be stored and analyzed on a single server, leading to high memory costs. Second, existing methods typically use matrix factorization or iterative optimization using the full network, resulting in high runtimes. We propose a strategy called predictive assignment to enable computationally efficient community detection while ensuring statistical accuracy. The core idea is to avoid large-scale matrix computations by breaking up the task into a smaller matrix computation plus a large number of vector computations that can be carried out in parallel. Under the proposed method, community detection is carried out on a small subgraph to estimate the relevant model parameters. Next, each remaining node is assigned to a community based on these estimates. We prove that predictive assignment achieves strong consistency under the stochastic blockmodel and its degree-corrected version. We also demonstrate the empirical performance of predictive assignment on simulated networks and two large real-world datasets: DBLP (Digital Bibliography & Library Project), a computer science bibliographical database, and the Twitch Gamers Social Network. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.