GC-SPM: A Fast $O(N\lg N)$ Graph Clustering Technique Using Structural Proximity for Social Systems Analysis
Mohammad Maksood Akhter, Rashmi Maheshwari, Abdul Atif Khan, Sraban Kumar Mohanty · IEEE Transactions on Computational Social Systems · 2025
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$O(N\lg N)$, GC-SPM is well-suited for real-time applications in computational social systems, including human activity recognition, e-commerce analytics, and environmental monitoring.