News & Announcements

July 2, 2012

"New coarsening schemes improve quality in graph partitioning problems"

Media Contacts: Gail Pieper at pieper@mcs.anl.gov

Ilya Safro, an Argonne Scholar in the Mathematics and Computer Science Division, and two colleagues from the Karlsruhe Institute of Technology have formulated new coarsening schemes for multilevel graph partitioning.

The graph partitioning problem is widely used in many practical and theoretical applications, for example in biological networks, the Web, and social communities. Numerous multilevel strategies have been developed for solving this problem, but most of the research has been on the refinement phase.

Safro and his colleagues have instead focused on the coarsening phase and, in particular, on algebraic multigrid-based schemes with highly irregular structures. They have incorporated algebraic distance as a measure of connectivity strength for graph partitioning algorithms to help separate the subgraphs and postpone the aggregation into one mixture.

The computational results show clear improvements in quality—both on graphs arising in real-world applications and on graphs specifically designed to be hard for multilevel algorithms. Arguably, the tradeoff for improvement in quality is additional running time; however, experiments show that this additional time becomes far less significant with the growth of the graph size compared with the complexity of the refinement phase.