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

}