GC-SPM: A Fast $O(N\lg N)$ Graph Clustering Technique Using Structural Proximity for Social Systems Analysis

The rapid growth of information technology in social systems has made extracting insights from large-scale, real-time data increasingly challenging. This has led to a demand for faster and more efficient clustering algorithms. Traditional methods like K-means struggle to capture complex structures, while graph-based clustering techniques, though effective, often come with high computational costs. This work introduces GC-SPM, a fast and efficient graph-based clustering method that leverages intra- and interproximity between subclusters to improve clustering accuracy while reducing computational overhead. The method follows a three-step process: 1) two-stage data partitioning, which splits the dataset into compact subclusters based on data dispersion, preserving geometric distribution; 2) sparse graph construction, which efficiently connects subcluster centers to identify adjacency relationships; and 3) iterative merging, which forms final clusters based on structural similarity. Experimental results on diverse datasets show that GC-SPM outperforms traditional and state-of-the-art methods in clustering quality while achieving the fastest execution time. With an overall computational complexity of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(N\lg N)$</tex-math></inline-formula>, GC-SPM is well-suited for real-time applications in computational social systems, including human activity recognition, e-commerce analytics, and environmental monitoring.