Parallel Edge Contraction for Large Nonplanar Graph Clustering

With the flowering of graph mining and computation technology, the field of graph clustering has become popular. Particularly, to cluster increasingly massive data represented as graph become common today. There have been many research efforts on graph clustering algorithms as well as reported applications. However, graph clustering technology is highly application specific and computationally expensive especially when applied to huge data. In this paper, we propose an efficient graph contraction algorithm for speeding up graph clustering. We target at parallelizing edge contraction for reducing computing time for graph mining. We adopt massive multithreading for edge contraction on huge non planar graph. In experiment, our algorithm achieves good parallel efficiency for computation time of both contracting edges and clustering graph as the number of threads increases. Our edge contraction algorithm achieves the speedup ranging from 3 to 6 in contracting 10000 to 30000 edges. Finally, we observe that with edge contraction, parallel clustering achieves speed up is 8 to 80 times faster compared with the result of no edge contraction.