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.

Density based clustering techniques discover the intrinsic clusters by separating the regions present in the dataset as high- and low-density regions based on their neighborhood information. They are popular and effective because they identify the clusters of arbitrary shapes and automatically detect the number of clusters. However, the distribution patterns of clusters are natural and complex in the datasets generated by different applications. Most of the existing density based clustering algorithms are not suitable to identify the clusters of complex pattern with large variation in density because they use fixed global parameters to compute the density of data points. Minimum spanning tree (MST) of a complete graph easily captures the intrinsic neighborhood information of different characteristic datasets without any user defined parameters. We propose a new Relative Density measure based on MST Neighborhood graph (RDMN) to compute the density of data points. Based on this new density measure, we propose a clustering technique to identify the clusters of complex patterns with varying density. The MST neighborhood graph is partitioned into dense regions based on the density level of data points to retain the shape of clusters. Finally, these regions are merged into actual clusters using MST based clustering technique. To the best of our knowledge, the proposed RDMN is the first MST based density measure for capturing the intrinsic neighborhood without any user defined parameter. Experimental results on synthetic and real datasets demonstrate that the proposed algorithm outperforms other popular clustering techniques in terms of cluster quality, accuracy, and robustness against noise and detecting the outliers.

Nowadays cloud servers have become the primary choice to store and share data with multiple users across the globe. The major challenge in sharing data using cloud servers is to protect data against untrusted cloud service provider and illegitimate users. Attribute-Based Encryption (ABE) has emerged as a useful cryptographic technique to securely share data with legitimate recipients in fine-grained manner. Several solutions employing ABE have been proposed to securely share data using cloud servers. However, most of the solutions are data owner-centric and focus on providing data owner complete control on his outsourced data. The existing solutions in cloud computing fail to provide shared access privileges among users and to enable cloud users to delegate their access privileges in a flexible manner. In order to simultaneously achieve the notion of fine-grained access control, scalability and to provide cloud users shared access privileges and flexibility on delegation of their access privileges, we propose a scalable attribute-based access control scheme for cloud storage. The scheme extends the ciphertext policy attribute-based encryption to achieve flexible delegation of access privileges and shared access privileges along with scalability and fine-grained access control. The scheme achieves scalability by employing hierarchical structure of users. Furthermore, we formally prove the security of our proposed scheme based on security of the ciphertext-policy attribute-based encryption. We also implement the algorithm to show its scalability and efficiency.

The wireless sensor network WSN is more vulnerable than the wired network because it is relatively easy for an adversary to eavesdrop, insert, alter, and intercept the message communicated in the network. Sensor nodes have very limited power and memory. While designing the secure communication architectures, the main goal is to design and memory efficient protocols. Most of the well-known communication architectures like TinySec, LLSP, and MiniSec compromise with the security issues because of and memory constraints of sensor nodes. In WSN, communication consumes more than computation. By minimizing communication overhead, the consumption can be reduced. We propose a new energy efficient secure communication called EESCA for WSN, to make the communication secure. Along with authentication, confidentiality and integrity, the proposed architecture provides strong replay protection, and data freshness as permutation and substitution are used to generate massage authentication code. EESCA is robust against heavy packet loss because reset or resynchronization of counter is not required. The proposed scheme is efficient as the security packet overhead is reduced by 1i¾źbyte over the best-known secure communication architectures. The efficacy of EESCA is shown through theoretical and experimental analysis. Copyright © 2016 John Wiley & Sons, Ltd.

The QR algorithm solves the standard eigenvalue problem. Analogously, the QZ-algorithm solves the generalised eigenvalue problem. Both are iterative algorithms. We study these algorithms on the External Memory model introduced by Aggarwal and Vitter and analyse them for their I/O and seek complexities. We analyse the multi shift QR algorithm [1]; this algorithm chases m × m bulges, where m is the number of shifts, using both matrix-vector and matrix-matrix operations. We also investigate the small-bulge multishift QR algorithm [2] which was proposed to avoid the phenomenon called shift blurring. We propose a tile based small-bulge multi shift QR algorithm which is scalable and more amenable for multicore architecture than the traditional panel based algorithms and that under certain conditions of the number of shifts has better seek and I/O complexities. We prove analogous results for the QZ algorithm [3] too.