The graph partitioning problem is widely used and studied in many practical
and theoretical applications. The multilevel strategies represent today one of
the most effective and efficient generic frameworks for solving this problem on
large-scale graphs. Most of the attention in designing the multilevel
partitioning frameworks has been on the refinement phase. In this work we focus
on the coarsening phase, which is responsible for creating structurally similar
to the original but smaller graphs.