Parallel community detection for massive graphs

E. Jason Riedy, Henning Meyerhenke, David Ediger, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

43 Scopus citations


Tackling the current volume of graph-structured data requires parallel tools. We extend our work on analyzing such massive graph data with the first massively parallel algorithm for community detection that scales to current data sizes, scaling to graphs of over 122 million vertices and nearly 2 billion edges in under 7300 seconds on a massively multithreaded Cray XMT. Our algorithm achieves moderate parallel scalability without sacrificing sequential operational complexity. Community detection partitions a graph into subgraphs more densely connected within the subgraph than to the rest of the graph. We take an agglomerative approach similar to Clauset, Newman, and Moore's sequential algorithm, merging pairs of connected intermediate subgraphs to optimize different graph properties. Working in parallel opens new approaches to high performance. On smaller data sets, we find the output's modularity compares well with the standard sequential algorithms.

Original languageEnglish (US)
Title of host publicationParallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers
Number of pages11
EditionPART 1
StatePublished - 2012
Externally publishedYes
Event9th International Conference on Parallel Processing and Applied Mathematics, PPAM 2011 - Torun, Poland
Duration: Sep 11 2011Sep 14 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume7203 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference9th International Conference on Parallel Processing and Applied Mathematics, PPAM 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Community detection
  • graph analysis
  • parallel algorithm


Dive into the research topics of 'Parallel community detection for massive graphs'. Together they form a unique fingerprint.

Cite this