Advanced Coarsening Schemes for Graph Partitioning

摘要

The graph partitioning problem is widely used and studied in many practical and theoretical applications.rnToday, multilevel strategies represent one of the most effective and efficient generic frameworks for solvingrnthis problem on large-scale graphs. Most of the attention in designing multilevel partitioning frameworksrnhas been on the refinement phase. In this work, we focus on the coarsening phase, which is responsiblernfor creating structures similar to the original but smaller graphs. We compare different matching- andrnAMG-based coarsening schemes, experiment with the algebraic distance between nodes, and demonstraterncomputational results on several classes of graphs that emphasize the running time and quality advantagesrnof different coarsening schemes.