Academic Journals Database
Disseminating quality controlled scientific knowledge

GClustering Algorithm

Author(s): Mr. Promod Kumar Sahu , G.Ravi teja

Journal: International Journal of Advanced Research in Computer Engineering & Technology (IJARCET)
ISSN 2278-1323

Volume: 1;
Issue: 7;
Start page: 188;
Date: 2012;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: Graph clusters | Hashing | Pruning | Hash Table.

Graph clustering poses significant challenges because of the complex structures which may be present in the underlying data. The massive size of the underlying graph makes explicit structural enumeration very difficult. Consequently, most techniques for clustering multi-dimensional data are difficult to generalize to the case of massive graphs. Recently, methods have been proposed for clustering graph data, though these methods are designed for static data, and are not applicable to the case of graph streams. Furthermore, these techniques are especially not effective for the case of massive graphs, since a huge number of distinct edges may need to be tracked simultaneously. This result in storage and computational challenges during the clustering process.The finding of clusters, well-connected components in a graph, is useful in many applications from natural function prediction to social community detection. An important insight is that many clustering applications need only the subset of best clusters, and not all clusters in the entire graph. In this paper we propose a new technique, GClustering, which probabilistically searches large, edge weighted, directed graphs for their best clusters in linear time. The algorithm is inherently parallelizable, and is able to find variable size, overlapping clusters. To increase scalability, a parameter is introduced that controls memory use. When compared with three other state-of-the art clustering techniques, GClustering algorithm achieves running time speedups of up to 70% on large scale real world datasets. In addition, the clusters returned by GClustering are consistently found to be better both in calculated score and when compared on real world benchmarks.
Why do you need a reservation system?      Save time & money - Smart Internet Solutions