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

Abstract

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
Pages286-296
Number of pages11
EditionPART 1
DOIs
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

Conference

Conference9th International Conference on Parallel Processing and Applied Mathematics, PPAM 2011
Country/TerritoryPoland
CityTorun
Period9/11/119/14/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Community detection
  • graph analysis
  • parallel algorithm

Fingerprint

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

Cite this