Graph Coarsening and Clustering on the GPU

B. O. Fagginger Auer, R. H. Bisseling
Mathematics Institute, Utrecht University, Budapestlaan 6, 3584 CD, Utrecht, the Netherlands
10th DIMACS Implementation Challenge – Graph Partitioning and Graph Clustering, 2012


   title={Graph Coarsening and Clustering on the GPU},

   author={Auer, B.O.F. and Bisseling, RH},



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: