Scalable community detection in massive networks via predictive assignment

Subhankar Bhadra · 2025

Read Scalable community detection in massive networks via predictive assignment by Subhankar Bhadra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-16730.txt.

Introduction

Subhankar Bhadra, Marianna Pensky, and Srijan Sengupta make community detection, in a 2025 preprint, cheap enough for truly massive networks. Finding groups in a network usually means holding the whole graph on one machine and factoring big matrices. Both steps choke on huge data. Their predictive assignment strategy splits the job. Communities are first found inside a small subgraph, where the model parameters are estimated. Every remaining node is then slotted into a community by a cheap vector computation. Those assignments run in parallel across machines.

The authors prove the method recovers the true split under the standard blockmodel and its degree-corrected cousin. Tests cover simulated networks and two large real ones: a computer science bibliography and a gamers' social network. Accuracy held up while cost fell away. The paper targets scientists whose networks no longer fit the old workflow at all.

Catalog record

CREATORSubhankar Bhadra
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE132 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-16730

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scalable community detection in massive networks via predictive assignment Subhankar Bhadra Abstract 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. Keywords: Spectral Clustering, Bias-adjusted Spectral Clustering, Stochastic Block Model, Degree Corrected Stochastic Block Model, Computational Efficiency, Scalable Inference 1 Introduction Community structure is a common feature of networks, where the nodes in a network belong to clusters or communities that exhibit similar behavior [ 7 , 38 ] . Numerous community detection methods have been developed and studied in the statistics literature, e.g., spectral methods [ 14 , 26 , 29 ] , modularity based methods [ 4 , 40 ] , and likelihood based methods [ 2 , 30 ] . These community detection methods are statistically sound, with rigorous theoretical guarantees, making them valuable tools for network analysis. However, applying these existing methods becomes computationally challenging in many scientific fields where massive networks are becoming increasingly common, e.g., epidemic modeling [ 33 ] , brain networks [ 24 , 27 ] , online social networks [ 10 , 20 ] , and biomedical text networks [ 11 , 16 ] . How serious is this problem? To illustrate this, we report a brief computational experiment. Consider an undirected network of n nodes with no self-loops, represented by an adjacency matrix A\in\{0,1\}^{n\times n} , where A_{i,j}\sim\text{Bernoulli}(P_{i,j}) for 1\leq i<j\leq n . Suppose the network has K communities, where K is known, with membership vector c=\{c_{i}\}_{i=1}^{n} and membership matrix M\in\{0,1\}^{n\times K} , where M_{i,j}=\mathbb{I}(c_{i}=j) . Under the stochastic block model (SBM) [ 12 ] , we set P=M\Omega M^{T} , where \Omega\in\mathbb{R}^{K\times K} defines block interactions: \Omega_{rs}=\frac{\alpha Kh}{h+(K-1)}\,I(r=s)+\frac{\alpha K}{h+(K-1)}\,I(r\neq s),\quad r,s\in\{1,\dots,K\}, with density parameter \alpha=0.01 and homophily factor h=3 . We generated balanced SBMs (each community has n/K nodes) under five scenarios: (i) n=20000,K=10 , (ii) n=50000,K=15 , (iii) n=100000,K=20 , (iv) n=150000,K=20 , (v) n=200000,K=20 . For each scenario, we generated 30 networks and performed community detection using spectral clustering and bias-adjusted spectral clustering [ 26 , 32 , 17 ] . Spectral Clustering Bias-adjusted Spectral Clustering n K Error (%) Memory (Mb.) Runtime (min) Error (%) Memory (Mb.) Runtime (min) 20000 10 0.0\pm 0.0 98.5 0.87 0.0\pm 0.0 8079.6 2.71 50000 15 0.0\pm 0.0 555 3.89 Memory Overload 100000 20 0.0\pm 0.0 1907 12.90 Memory Overload 150000 20 0.2\pm 1.4 4284 19.92 Memory Overload 200000 20 0.2\pm 1.4 7632 28.31 Memory Overload Table 1: Computational cost of community detection, with units in parentheses, on a server with Intel Xeon(R) E5-4627 v3 processors. Community detection errors are reported as mean \pm standarad deviation in percentage. The R functions irlba and peakRAM were used to implement spectral decomposition of the adjacency matrix and to compute the memory requirement, respectively. In Table 1 , we report the runtime (in minutes) and memory usage (MB), in addition to the Hamming loss community detection error. We observe that while spectral clustering and its bias-adjusted version are statistically very accurate, with errors close to zero, the computational costs are rather high. Spectral clustering takes 20 minutes for n=150000 and over 28 minutes for n=200000 . For bias-adjusted spectral clustering, memory exceeds 8000 MB for n=20000 (exceeding the 8000 MB RAM of a typical laptop) and 16 GB for n\geq 50000 , causing a “memory overload” error on the server since it exceeds the 16 GB memory allocation. We would like to point out that the statistical literature on scalable inference tends to focus on runtime as the only measure of computational cost [ 15 , 23 , 31 ] . But in practice, the memory requirement of a statistical method is also a critical component of computational cost. Also note that spectral clustering is one of the fastest community detection algorithms [ 23 , 34 ] , especially with our fast implementation using irlba . Other community detection algorithms, e.g., likelihood-based methods, are likely to fare worse. In this paper, we introduce predictive assignment , a new technique designed to scale up community detection. The key idea is that if we can have reasonably accurate estimates of the model parameters, we can assign the nodes to communities individually, eliminating the need for clustering. These estimates can be efficiently obtained via community detection on a small subgraph of the network, significantly reducing computational costs compared to community detection on the full network, in the spirit of randomized sketching [ 35 ] . Predictive assignment consists of three steps. In Step 1, we select a subsample of nodes from the network. In Step 2, we implement a standard community detection algorithm Figure 1: A schema of the predictive assignment algorithm. Step 1: subsample selection; Step 2: community detection from the subgraph and estimation of the structural link parameter; Step 3: assignment of the remaining nodes to communities. (such as spectral clustering) on the subgraph formed by the subsampled nodes. When the subsample size is small compared to the full network size, this step drastically reduces runtime and memory usage. For example, if the subsample comprises 20\% of the nodes, an O(n^{3}) algorithm would run approximately 125 times faster than on the full network. In Step 3, we assign the remaining nodes to communities by exploiting the mathematical structure of the model. A model assumption (e.g., SBM) provides a structural link between the community memberships of the subgraph nodes (which have already been estimated) and the community memberships of the rest of the nodes (which still need to be estimated). We leverage this structural link to formulate a decision rule that assigns each remaining node to its community using only vector computations. See Figure 1 for a visual illustration. Predictive assignment is highly versatile as it can accommodate any reasonably accurate community detection method in Step 2 while offering theoretical guarantees of asymptotic accuracy. In this paper, we theoretically analyze predictive assignment under the stochastic blockmodel (defined earlier) as well as the degree corrected blockmodel (DCBM). In Section 3 , we prove that under certain mild assumptions, predictive assignment achieves strong consistency in Step 3 (i.e., perfect community assignment with probability tending to 1), even when subgraph community detection in

Read the complete text