An efficient parallel graph clustering technique using Pregel
- 1 January 2016
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 370-373
Abstract
To represent complex structure, graph data is widely used in diverse applications. Among various techniques to extract meaningful information in graph data, graph clustering is an important task for the discovery of an underlying graph structure. However, the volume of graph data becomes large and increases fast recently as well as traditional clustering algorithms become computationally expensive as the size of data to be clustered increases. In this paper, we propose an efficient graph clustering algorithm running on Pregel which is one of prominent parallel processing models for large-scale graph data. Graph clustering technique merges the nodes into clusters such that the nodes in a cluster are strongly connected each other. To seek strongly connected nodes efficiently, we utilize Min-Hash which calculates similarity between vertices and/or clusters. In our experimental study, we demonstrate the efficiency and scalability of our parallel algorithm compared to existing algorithms.Keywords
This publication has 7 references indexed in Scilit:
- Mining of Massive Datasets2011
- Pregel2010
- RRW: repeated random walks on genome-scale protein networks for local cluster discoveryBMC Bioinformatics, 2009
- Clustering Social Networks2007
- On clusteringsJournal of the ACM, 2004
- Syntactic clustering of the WebComputer Networks and ISDN Systems, 1997
- A bridging model for parallel computationCommunications of the ACM, 1990