Thumbnail
Access Restriction
Open

Author Riedy, E. Jason ♦ Meyerhenke, Henning ♦ Ediger, David ♦ Bader, David A.
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Current Volume ♦ Current Data Size ♦ Parallel Scalability ♦ Parallel Open New Approach ♦ Different Graph Property ♦ Sequential Operational Complexity ♦ Massive Graph Data ♦ Parallel Community Detection Algorithm ♦ Parallel Tool ♦ Real-world Graph ♦ Massive Graph ♦ Parallel Algorithm ♦ Graph-structured Data ♦ Cray Xmt2 ♦ Parallel Community Detection ♦ Community Detection Partition ♦ Sequential Algorithm ♦ Openmp Platform ♦ High Performance ♦ Agglomerative Approach ♦ Community Detection ♦ Four-processor Intel E7-8870-based Server ♦ Algorithm Achieves ♦ Dimacs Implementation ♦ Connected Intermediate Subgraphs
Description Tackling the current volume of graph-structured data requires parallel tools. We extend our work on analyzing such massive graph data with a massively parallel algorithm for community detection that scales to current data sizes, clustering a real-world graph of over 100 million vertices and over 3 billion edges in under 500 seconds on a four-processor Intel E7-8870-based server. 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. We improve performance of our parallel community detection algorithm on both the Cray XMT2 and OpenMP platforms and adapt our algorithm to the DIMACS Implementation
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2011-01-01
Publisher Institution IN: PROCEEDINGS OF THE 9TH INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING AND APPLIED MATHEMATICS. TORUN