SC13 Home > SC13 Schedule > SC13 Presentation - Nerstrand: Fast Multi-Threaded Graph Clustering

SCHEDULE: NOV 16-22, 2013

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

Nerstrand: Fast Multi-Threaded Graph Clustering

SESSION: Research Poster Reception

EVENT TYPE: Posters, Electronic Posters, and Education Posters

TIME: 5:15PM - 7:00PM

AUTHOR(S):Dominique W. LaSalle, George Karypis

ROOM:Mile High Pre-Function

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.

Chair/Author Details:

Dominique W. LaSalle - University of Minnesota

George Karypis - University of Minnesota

Add to iCal  Click here to download .ics calendar file

Add to Outlook  Click here to download .vcs calendar file

Add to Google Calendarss  Click here to add event to your Google Calendar