**Contemporary Mathematics**

Volume: 588;
2013;
240 pp;
Softcover

MSC: Primary 05; 68;

**Print ISBN: 978-0-8218-9038-7
Product Code: CONM/588**

List Price: $95.00

AMS Member Price: $76.00

MAA Member Price: $85.50

**Electronic ISBN: 978-0-8218-9869-7
Product Code: CONM/588.E**

List Price: $89.00

AMS Member Price: $71.20

MAA Member Price: $80.10

# Graph Partitioning and Graph Clustering

Share this page *Edited by *
*David A. Bader; Henning Meyerhenke; Peter Sanders; Dorothea Wagner*

Graph partitioning and graph clustering are ubiquitous subtasks in many applications where graphs play an important role. Generally speaking, both techniques 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?

The 10th DIMACS Implementation Challenge Workshop was devoted to determining realistic performance of algorithms where worst case analysis is overly pessimistic and probabilistic models are too unrealistic. Articles in the volume describe and analyze various experimental data with the goal of getting insight into realistic algorithm performance in situations where analysis fails.

This book is published in cooperation with the Center for Discrete Mathematics and Theoretical Computer Science

#### Readership

Graduate students and research mathematicians interested in graph theory and combinatorial algorithms.

# Table of Contents

## Graph Partitioning and Graph Clustering

- Preface vii8 free
- High quality graph partitioning 116 free
- Abusing a hypergraph partitioner for unweighted graph partitioning 1934
- Parallel partitioning with Zoltan: Is hypergraph partitioning worth it? 3752
- UMPa: A multi-objective, multi-level partitioner for communication minimization 5368
- Shape optimizing load balancing for MPI-parallel adaptive numerical simulations 6782
- Graph partitioning for scalable distributed graph computations 8398
- 1. Introduction 8398
- 2. Parallel Breadth-first Search 8499
- 3. Analysis of Communication Costs 85100
- 4. Graph and Hypergraph Partitioning Metrics 88103
- 5. Experimental Setup 89104
- 6. Microbenchmarking Collectives Performance 90105
- 7. Performance Analysis and Results 92107
- 8. Conclusions and Future Work 99114
- Acknowledgments 100115
- References 100115
- Appendix on edge count per processor 100115

- Using graph partitioning for efficient network modularity optimization 103118
- Modularity maximization in networks by variable neighborhood search 113128
- Network clustering via clique relaxations: A community based approach 129144
- Identifying base clusters and their application to maximizing modularity 141156
- Complete hierarchical cut-clustering: A case study on expansion and modularity 157172
- A partitioning-based divisive clustering technique for maximizing the modularity 171186
- An ensemble learning strategy for graph clustering 187202
- Parallel community detection for massive graphs 207222
- Graph coarsening and clustering on the GPU 223238