DIMACS/AMS Volumes in
Contemporary Mathematics Series

TITLE: "Graph Partitioning and Graph Clustering"
EDITORS: David A. Bader, Henning Meyerhenke, Peter Sanders and Dorothea Wagner

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.


This collection is related to the Workshop of the 10th DIMACS Implementation Challenge, which took place in Atlanta, Georgia (USA) on February 13-14, 2012. The purpose of DIMACS Implementation Challenges is to assess the practical performance of algorithms in a respective problem domain. These challenges are scientific competitions in area of interest where worst case and probabilistic analysis yield unrealistic results. Where analysis fails, experimentation can provide insights into realistic algorithm performance and thereby help to bridge the gap between theory and practice. For this purpose common benchmark instances, mostly from real applications, are established. By evaluating different implementations on these instances, the challenges create a reproducible picture of the state of the art in the area under consideration. This helps to foster an effective technology transfer within the research areas of algorithms, data structures, and implementation techniques as well as a transfer back to the original applications.

The 10th challenge considered the two related problems of partitioning and clustering graphs. Both are ubiquitous subtasks in many application areas. Generally speaking, techniques for graph partitioning and graph clustering aim at the identification of vertex subsets with many internal and few external edges. To name only a few, problems addressed by graph partitioning and graph clustering algorithms are:

  • What are the communities within an (online) social network?
  • How do I speed up a numerical simulation by mapping it efficiently onto a parallel computer?
  • How must components be organized on a computer chip such that they can communicate efficiently with each other?
  • What are the segments of a digital image?
  • Which functions are certain genes (most likely) responsible for?

    Within the algorithms community, techniques for solving the problems above have been developed at least since the early 1970s - while some of the applications are newer. Improving known and developing new solution techniques are aspects of ongoing research.

    The primary goal of this challenge was to create a reproducible picture of the state of the art in the area of graph partitioning and graph clustering algorithms. To this end, a standard set of benchmark instances was identified. Then participants were invited to submit solutions to different challenge problems. This way different algorithms and implementations were tested against the benchmark instances. Thereby future researchers are enabled to identify techniques that are most effective for a respective partitioning or clustering problemby using our benchmark set and by comparing their results to the challenge results.

    PDF for Full front and end matter.


         David A. Bader, Henning Meyerhenke, Peter Sanders,
           and Dorothea Wagner                               vii
    High Quality Graph Partitioning
         Peter Sanders and Christian Schulz                    1
    Abusing a Hypergraph Partitioner for Unweighted Graph
         B.O. Fagginger Auer and R.H. Bisseling               19
    Parallel Partitioning with Zoltan: Is Hypergraph
       Partitioning Worth It?
         Sivasankaran Rajamanickam and Erik G. Boman          37
    UMPa: A Multi-objective, multi-level partitioner for
       communication minimization
         Umit V. Catalyurek, Mehmet Deveci, Kamer Kaya,
           and Bora Ucar                                      53
    Shape Optimizing Load Balancing for MPI-Parallel
       Adaptive Numerical Simulations
         Henning Meyerhenke                                   67
    Graph Partitioning for Scalable Distributed Graph
         Aydin Buluc and Kamesh Madduri                       83
    Using Graph Partitioning for Efficient Network
       Modularity Optimization
         Hristo Djidjev and Melih Onus                       103
    Modularity Maximization in Networks by Variable
       Neighborhood Search
         Daniel Aloise, Gilles Caporossi, Pierre Hansen,
           Leo Liberti, Sylvain Perron, and Manuel Ruiz      113
    Network Clustering via Clique Relaxations: A Community
       Based Approach
         Anurag Verma and Sergiy Butenko                     129
    Identifying Base Clusters and Their Application to
       Maximizing Modularity
         Sriram Srinivasan, Tanmoy Chakraborty, and
           Sanjukta Bhowmick                                 141
    Complete Hierarchical Cut-Clustering: A Case Study on
       Expansion and Modularity
         Michael Hamann, Tanja Hartmann, and Dorothea Wagner 157
    A Partitioning-Based Divisive Clustering Technique for
       Maximizing the Modularity
         Umit V. Catalyurek, Kamer Kaya, Johannes Langguth,
           and Bora Ucar                                     171
    An Ensemble Learning Strategy for Graph Clustering
         Michael Ovelgonne and Andreas Geyer-Schulz          187
    Parallel Community Detection for Massive Graphs
         E. Jason Riedy, Henning Meyerhenke, David Ediger,
           and David A. Bader                                207
    Graph Coarsening and Clustering on the GPU
         B.O. Fagginger Auer and R.H. Bisseling              223

    Index Index of Volumes
    DIMACS Homepage
    Contacting the Center
    Document last modified on October 22, 2013.