You are not logged in to this journal. Log in

We present a new algorithm for graph partitioning based on optimization of the combinatorial isoperimetric constant. It is shown empirically that this algorithm is competitive with other global partitioning algorithms in terms of partition quality. The isoperimetric algorithm is easy to parallelize, does not require coordinate information, and handles nonplanar graphs, weighted graphs, and families of graphs which are known to cause problems for other methods. Compared to spectral partitioning, the isoperimetric algorithm is faster and more stable. An exact circuit analogy to the algorithm is also developed with a natural random walks interpretation. The isoperimetric algorithm for graph partitioning is implemented in our publicly available Graph Analysis Toolbox [L. Grady, Ph.D. thesis, Boston University, Boston, MA, 2004], [L. Grady and E. L. Schwartz, Technical report TR-03-021, Boston University, Boston, MA, 2003] for MATLAB obtainable at http://eslab.bu.edu/software/graphanalysis/. This toolbox was used to generate all of the results compiled in the tables of this paper.