2025, Vol. 6, Issue 2, Part E
Spectral graph methods for identifying communities in massive-scale social network data
Author(s): Kunal Kumar Singh
Abstract: The exponential growth of social platforms such as Facebook, Twitter (X), and LinkedIn has produced massive-scale social networks with billions of nodes and trillions of edges. Detecting communities densely connected groups of nodes remains a central task for understanding influence, information diffusion, and user behavior. This study proposes a scalable spectral graph framework that combines representative selection, sparse affinity construction, and bipartite partitioning to address the computational burden of eigen-decomposition in large graphs. The method reduces complexity to near-linear time, expressed as O(np+p3+nk), while significantly lowering memory usage.Traditional spectral clustering struggles with noisy, dynamic, and overlapping communities, making direct application infeasible for networks with millions of nodes. Our approach resolves these challenges through landmark-based approximation and sparsified Laplacians, enabling efficient computation without compromising accuracy. Experimental results demonstrate strong performance: for Facebook Circles (4,039 nodes), the method achieved NMI = 0.92, ARI = 0.89, Modularity = 0.83 in just 2.1s using 150MB; for DBLP (45,000 nodes), it achieved NMI = 0.88 and ARI = 0.85 with 980MB. In conclusion, the proposed framework balances scalability and accuracy, establishing spectral methods as practical tools for community detection in massive-scale social networks.
DOI: https://doi.org/10.22271/math.2025.v6.i2e.273
Pages: 751-760 | Views: 107 | Downloads: 38
Download Full Article: Click Here
How to cite this article:
Kunal Kumar Singh. Spectral graph methods for identifying communities in massive-scale social network data. Journal of Mathematical Problems, Equations and Statistics. 2025; 6(2): 751-760. DOI: 10.22271/math.2025.v6.i2e.273
