Parallel community detection for massive graphs

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

doi:10.1007/978-3-642-31464-3_29

Parallel community detection for massive graphs

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

45 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 language	English (US)
Title of host publication	Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers
Pages	286-296
Number of pages	11
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-31464-3_29
State	Published - 2012
Externally published	Yes
Event	9th International Conference on Parallel Processing and Applied Mathematics, PPAM 2011 - Torun, Poland Duration: Sep 11 2011 → Sep 14 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	7203 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Parallel Processing and Applied Mathematics, PPAM 2011
Country/Territory	Poland
City	Torun
Period	9/11/11 → 9/14/11

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Keywords

Community detection
graph analysis
parallel algorithm

Access to Document

10.1007/978-3-642-31464-3_29

Cite this

Riedy, E. J., Meyerhenke, H., Ediger, D., & Bader, D. A. (2012). Parallel community detection for massive graphs. In Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers (PART 1 ed., pp. 286-296). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7203 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-31464-3_29

Riedy, E. Jason ; Meyerhenke, Henning ; Ediger, David et al. / Parallel community detection for massive graphs. Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers. PART 1. ed. 2012. pp. 286-296 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{97877c68383845c6982a0b09ec4e3293,

title = "Parallel community detection for massive graphs",

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.",

keywords = "Community detection, graph analysis, parallel algorithm",

author = "Riedy, {E. Jason} and Henning Meyerhenke and David Ediger and Bader, {David A.}",

year = "2012",

doi = "10.1007/978-3-642-31464-3_29",

language = "English (US)",

isbn = "9783642314636",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "286--296",

booktitle = "Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers",

edition = "PART 1",

note = "9th International Conference on Parallel Processing and Applied Mathematics, PPAM 2011 ; Conference date: 11-09-2011 Through 14-09-2011",

}

Riedy, EJ, Meyerhenke, H, Ediger, D & Bader, DA 2012, Parallel community detection for massive graphs. in Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 7203 LNCS, pp. 286-296, 9th International Conference on Parallel Processing and Applied Mathematics, PPAM 2011, Torun, Poland, 9/11/11. https://doi.org/10.1007/978-3-642-31464-3_29

Parallel community detection for massive graphs. / Riedy, E. Jason; Meyerhenke, Henning; Ediger, David et al.
Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers. PART 1. ed. 2012. p. 286-296 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7203 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Parallel community detection for massive graphs

AU - Riedy, E. Jason

AU - Meyerhenke, Henning

AU - Ediger, David

AU - Bader, David A.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

KW - Community detection

KW - graph analysis

KW - parallel algorithm

UR - http://www.scopus.com/inward/record.url?scp=84865214626&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84865214626&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-31464-3_29

DO - 10.1007/978-3-642-31464-3_29

M3 - Conference contribution

AN - SCOPUS:84865214626

SN - 9783642314636

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 286

EP - 296

BT - Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers

T2 - 9th International Conference on Parallel Processing and Applied Mathematics, PPAM 2011

Y2 - 11 September 2011 through 14 September 2011

ER -

Riedy EJ, Meyerhenke H, Ediger D, Bader DA. Parallel community detection for massive graphs. In Parallel Processing and Applied Mathematics - 9th International Conference, PPAM 2011, Revised Selected Papers. PART 1 ed. 2012. p. 286-296. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-31464-3_29

Parallel community detection for massive graphs

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this