SPECTRAL GRAPH THEORY FOR COMMUNITY DETECTION IN LARGE-SCALE SOCIAL NETWORKS: A MATHEMATICAL FRAMEWORK

Abstract

Community detection in large-scale social networks remains a central challenge because methods must be both theoretically grounded and computationally efficient. This paper introduces a spectral framework that links the eigenvalue structure of the normalized Laplacian to the existence and separability of communities, and couples this theory with a scalable algorithm. The method estimates the number of groups by inspecting the spectral gap, embeds vertices using the leading eigenvectors, and clusters the embeddings. We validate on the MUSAE GitHub social network dataset, which contains edges, node features, and ground-truth communities. The framework delivers strong accuracy and efficiency: normalized mutual information 0.77, adjusted rand index 0.72, modularity 0.51, and median end-to-end runtime 120 seconds on graphs exceeding one hundred thousand nodes. Spectral analysis of the dataset exhibits a clear gap consistent with the recovered partitions, demonstrating alignment between theoretical detectability and empirical performance. The study offers a transparent, portable pipeline built on sparse linear algebra and randomized eigensolvers, and lays the foundations for extensions to temporal graphs, higher-order relations, and integration with neural models.