DIMACS/AMS Volumes in
Contemporary Mathematics Series

CONTEMPORARY MATHEMATICS 588
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.

EXCERPT FROM PREFACE

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.

    TABLE OF CONTENTS

    
Preface
     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
   Partitioning
     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
   Computations
     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.