文章基本信息

标题：GClustering Algorithm
本地全文：下载
作者：Promod Kumar Sahu ; G.Ravi teja
期刊名称：International Journal of Advanced Research in Computer Engineering & Technology (IJARCET)
印刷版ISSN：2278-1323
出版年度：2012
卷号：1
期号：7
页码：188-192
出版社：Shri Pannalal Research Institute of Technolgy
摘要：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.
关键词：Graph clusters; Hashing; Pruning; Hash Table