SC13 Denver, CO

The International Conference for High Performance Computing, Networking, Storage and Analysis

Nerstrand: Fast Multi-Threaded Graph Clustering.


Authors: Dominique W. LaSalle (University of Minnesota), George Karypis (University of Minnesota)

Abstract: In this work we apply the multilevel paradigm to optimizing the modularity of a graph clustering on parallel shared memory architectures. We improve upon the state of the art by introducing new methods for effectively and efficiently coarsening graphs with power-law degree distributions, detecting an unknown number of communities, and for performing greedy modularity refinement in parallel. Finally, we present the culmination of this research, the clustering tool Nerstrand. In serial mode, Nerstrand runs in a fraction of the time of current methods and produces results of similar quality. When run with multiple threads, Nerstrand exhibits significant speedup without any degradation of clustering quality. Nerstrand works well on large graphs, clustering a graph with over 18 million vertices and 261 million edges in 18.3 seconds.

Poster: pdf
Two-page extended abstract: pdf


Poster Index