With the exponential growth of Big Data in domains such as healthcare, genomics, and sensor networks, computationally efficient and effective clustering techniques have become essential for uncovering meaningful patterns. Traditional clustering methods face fundamental limitations in Big Data analysis. K-means is among the fastest known approaches, but it fails to capture non-spherical clusters. Hierarchical clustering can detect arbitrary shapes but suffers from sub-cubic complexity, while many state-of-the-art methods still incur quadratic complexity. Moreover, most existing approaches fail to capture the intrinsic structure of data. In this context, graph-based clustering has emerged as a powerful alternative due to its ability to model geometric relationships and reveal underlying structures. However, existing graph-based techniques typically incur quadratic complexity, limiting their scalability. The objective of this work is to develop a scalable graph-based clustering framework that reduces complexity while preserving clustering quality in large, noisy, and high-dimensional datasets. To achieve this, we propose a fast graph clustering framework with overall complexity$\mathcal {O}(N \lg N)$, where$N$denotes the number of data points. The method employs a two-stage dispersion-based partitioning to generate cohesive sub-clusters, followed by the construction of a sparse graph on sub-cluster centers to efficiently capture adjacency. Sub-clusters are then merged iteratively using a gravitational-force-inspired attraction model, enabling the discovery of coherent structures with reduced computation. Extensive experiments on 41 multi-scale datasets demonstrate that our method consistently outperforms traditional and state-of-the-art approaches, achieving average 27.33% higher clustering accuracy while reducing runtime by more than 86.64% on average. These results highlight both the innovation and the effectiveness of the proposed approach, making it highly suitable for Big Data analytics.

Spectral clustering (SC) is well-known for discovering natural groups present in the data by projecting them into Eigen-space based on the proximity graph but incurs cubic time in terms of size (N) of the data as all pair proximity is used. To enhance the efficiency of the SC techniques, the proximity between the data instances and their representatives ( R ) is captured through a bipartite similarity graph. However, extrinsic parameters such as the number of representatives and nearby representatives of data instances, influence the clustering performance, time, and memory usage. Therefore, in this work, we construct a parameter-free bipartite graph to further improve the clustering quality and computational cost of SC by introducing a locality-based sparsification technique. First, the proposed method (SBSC) determines O(√N) numbers of well-distributed representatives in O(N lg N) time by applying Bi-means and K -means partitioning techniques. Next, SBSC utilizes the local neighbors of R to search the nearby representatives, which fastens the search time to O(N). To the best of our knowledge, the proposed bipartite graph is the least (O(N)) sized and therefore, by exploiting the high sparsity of the graph accelerates the Eigen-decomposition step of SBSC. The proposed algorithm takes overall O(N(K 2 +lg N)) time only to detect K clusters, and experimental results on eighteen large-sized diversified datasets suggest that SBSC discovers complex clusters much faster than the competing methods with enhanced clustering quality.

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.

Density-based techniques are gaining popularity due to their inherent capability to detect nonconvex shaped clusters in the presence of noises and outliers. However, existing approaches suffer from higher computational costs and require optimization of global parameter values to determine similar density regions present within the data. The sparse similarity graphs can aid in detecting the neighborhood information which is essential to calculate the density distribution. We propose a technique, “graphical and gravitational force-based density clustering (GGDC)” by combining the concepts of graph neighborhood, density distribution, and gravitational force of attraction to obtain satisfying results with higher efficacy. First, the neighbors are identified using the similarity graph, and then a new density computation technique is proposed which considers the number of neighbors as well as their proximity information. Next, the density values are utilized to identify the similar density distributed regions using the force of gravity between the data points and their neighbors. Lastly, the neighboring denser regions are merged together to form the actual clusters using the gravitational force of attraction based on their density distribution and proximity. A thorough experimental study is performed to evaluate the performance of GGDC by comparing it to nine other well-known clustering algorithms on 26 diversified synthetic, gene expression, and real datasets including three application areas from computational social systems. The results show that GGDC is effective in identifying complex clusters and is also superior in terms of time complexity, and robustness against noise.

Approximate spectral clustering (ASC) algorithms work on the representative points of the data for discovering intrinsic groups. The existing ASC methods identify fewer representatives as compared to the number of data points to reduce the cubic computational overhead of the spectral clustering technique. However, identifying such representative points without any domain knowledge to capture the shapes and topology of the clusters remains a challenge. This work proposes an ASC method that suitably computes enough well-scattered representatives to efficiently capture the topology of the data, making the ASC faster without the requirement of tuning any external parameters. The proposed ASC algorithm first applies two-level partitioning using both boundary points and centroids-based partitioning to identify quality representatives in less time. In the next step, we calculate the proximity between the neighboring representatives using$k$-rounds of minimum spanning tree (MST) by considering the distribution of edge weights in each round to find$k$. The proposed method effectively utilizes the number of representatives in a way that the overall computational time is bounded by$O(N\lg N)$. The experimental results suggest that the proposed ASC method outperforms the competing ASC methods in terms of both running time and clustering quality.