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
Your response
You must be logged in to post a comment.
