Graph Partitioning and Graph Clustering
Will be published approx. on 30. July 2013
Book
Paperback/Softback
240 pages
978-0-8218-9038-7 (ISBN)
Description
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:
li>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 organised 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 analyse 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.
li>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 organised 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 analyse 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.
More details
Series
Language
English
Place of publication
Providence
United States
Target group
Professional and scholarly
Weight
384 gr
ISBN-13
978-0-8218-9038-7 (9780821890387)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Persons
David A. Bader, Georgia Institute of Technology, Atlanta, GA, USA.
Henning Meyerhenke, Karlsruhe Institute of Technology, Germany.
Peter Sanders, Karlsruhe Institute of Technology, Germany.
Dorothea Wagner, Karlsruhe Institute of Technology, Germany.
Henning Meyerhenke, Karlsruhe Institute of Technology, Germany.
Peter Sanders, Karlsruhe Institute of Technology, Germany.
Dorothea Wagner, Karlsruhe Institute of Technology, Germany.
Content
Table of Contents
Preface - by David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner
High quality graph partitioning - by P. Sanders and C. Schulz
Abusing a Hypergraph Partitioner for Unweighted Graph Partitioning - by B. O. Fagginger Auer and R. H. Bisseling
Parallel partitioning with Zoltan: Is hypergraph partitioning worth it? - by S. Rajamanickam and E. G. Boman
UMPa: A multi-objective, multi-level partitioner for communication minimization - by U. V. Catalyurek, M. Deveci, K. Kaya, and K. Ucar
Shape optimizing load balancing for MPI-parallel adaptive numerical simulations - by H. Meyerhenke
Graph partitioning for scalable distributed graph computations - by A. Buluc and K. Madduri
Using graph partitioning for efficient network modularity optimization - by H. Djidjev and M. Onus
Modularity maximization in networks by variable neighborhood search - by D. Aloise, G. Caporossi, P. Hansen, L. Liberti, S. Perron, and M. Ruiz
Network clustering via clique relaxations: A community based approach - by A. Verma and S. Butenko
Identifying base clusters and their application to maximizing modularity - by S. Srinivasan, T. Chakraborty, and S. Bhowmick
Complete hierarchical cut-clustering: A case study on expansion and modularity - by M. Hamann, T. Hartmann, and D. Wagner
A partitioning-based divisive clustering technique for maximizing the modularity - by U. V. Catalyurek, K. Kaya, J. Langguth, and B. Ucar
An ensemble learning strategy for graph clustering - by M. Ovelgonne and A. Geyer-Schulz
Parallel community detection for massive graphs - by E. J. Riedy, H. Meyerhenke, D. Ediger, and D. A. Bader
Graph coarsening and clustering on the GPU - by B. O. Fagginger Auer and R. H. Bisseling
Preface - by David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner
High quality graph partitioning - by P. Sanders and C. Schulz
Abusing a Hypergraph Partitioner for Unweighted Graph Partitioning - by B. O. Fagginger Auer and R. H. Bisseling
Parallel partitioning with Zoltan: Is hypergraph partitioning worth it? - by S. Rajamanickam and E. G. Boman
UMPa: A multi-objective, multi-level partitioner for communication minimization - by U. V. Catalyurek, M. Deveci, K. Kaya, and K. Ucar
Shape optimizing load balancing for MPI-parallel adaptive numerical simulations - by H. Meyerhenke
Graph partitioning for scalable distributed graph computations - by A. Buluc and K. Madduri
Using graph partitioning for efficient network modularity optimization - by H. Djidjev and M. Onus
Modularity maximization in networks by variable neighborhood search - by D. Aloise, G. Caporossi, P. Hansen, L. Liberti, S. Perron, and M. Ruiz
Network clustering via clique relaxations: A community based approach - by A. Verma and S. Butenko
Identifying base clusters and their application to maximizing modularity - by S. Srinivasan, T. Chakraborty, and S. Bhowmick
Complete hierarchical cut-clustering: A case study on expansion and modularity - by M. Hamann, T. Hartmann, and D. Wagner
A partitioning-based divisive clustering technique for maximizing the modularity - by U. V. Catalyurek, K. Kaya, J. Langguth, and B. Ucar
An ensemble learning strategy for graph clustering - by M. Ovelgonne and A. Geyer-Schulz
Parallel community detection for massive graphs - by E. J. Riedy, H. Meyerhenke, D. Ediger, and D. A. Bader
Graph coarsening and clustering on the GPU - by B. O. Fagginger Auer and R. H. Bisseling