An experimental study of partitioning methods for large graphs

Author

S. Kanagaraj

Date of Award

12-1995

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Mark T. Jones

Committee Members

Donald Bouldin, Michael Langston

Abstract

The solution models of a number of problems requiring parallel processing systems can be represented in the forms of graphs. Partitioning a given problem to be processed on a parallel system can therefore be reduced to partitioning its representative graph. Graph coarsening is a technique in which a large graph hav-ing many thousands to millions of vertices is reduced to a few thousand vertices where the partitioning can be performed in less time. Graph coarsening in con-junction with various partitioning methods available has been found to improve the partitioning quality by as much as 50% and also in many cases reduce the overall partitioning time by about 16% at the same time. There are two primary methods available for coarsening: edge contraction and vertex reduction. In this thesis, we present six coarsening heuristics based on the vertex reduction tech-nique. There are several partitioning heuristics available to partition the graph. We explain five of these heuristics used in this thesis. Combinations of these coarsening and partitioning heuristics can be used in at least two general methods to partition a graph: single-level and multilevel,/em>. The main objective of this thesis is to present and examine experimentally the coarsening/partitioning “space”. There are several variables to consider to generate the experimental re-sults and some variables could take many values. Through experimental results, we show that the experimental “space' can be simplified by eliminating three variables from the list of variables. Using the simplified list, we then perform experiments on seventeen test graphs. The methods are evaluated by measuring the partitioning quality of the results from these experiments. Graph coarsening used in conjunction with the multilevel algorithm usu-ally improves the partitioning quality and frequently reduces the overall time for partitioning. For most of the graphs tested, results indicate that, among the coarsening heuristics presented, Min Degree results in better quality partition-ing. Results from the tests show that with the multilevel partitioning algorithm, the vertex reduction scheme takes less time than the edge contraction scheme and results in an almost equivalent or better partitioning quality. Results also show that with the vertex reduction scheme, the multilevel partitioning algorithm always results in a better partitioning quality than the single-level partitioning algorithm. Use of the KL local refinement method generally improves the qual-ity of the partitioning at the expense of increased time. The multilevel method in conjunction with the vertex reduction coarsening technique and the KL local refinement heuristic is a good choice where a high quality partitioning is required.