Graph Coarsening and Clustering on the GPU
Mathematics Institute, Utrecht University, Budapestlaan 6, 3584 CD, Utrecht, the Netherlands
10th DIMACS Implementation Challenge – Graph Partitioning and Graph Clustering, 2012
@article{auer2012graph,
title={Graph Coarsening and Clustering on the GPU},
author={Auer, B.O.F. and Bisseling, RH},
year={2012}
}
Agglomerative clustering is an effective greedy way to quickly generate graph clusterings of high modularity in a small amount of time. In an effort to use the power offered by multi-core CPU and GPU hardware to solve the clustering problem, we introduce a fine-grained sharedmemory parallel graph coarsening algorithm and use this to implement a parallel agglomerative clustering heuristic on both the CPU and the GPU. This heuristic is able to generate clusterings in very little time: a modularity 0.996 clustering is obtained from a street network graph with 14 million vertices and 17 million edges in 4.6 seconds on the GPU.
February 15, 2012 by hgpu
