10/01/1996 09:00 AM
Computer Science
This paper presents a new spectral partitioning formulation which directly incorporates vertex size information. The formulation results in a generalized eigenvalue problem, and this problem is reduced to the standard eigenvalue problem. Experimental results show that incorporating vertex sizes into the eigenvalue calculation produces results that are 50% better than the standard formulation in terms of scaled ratio-cut cost, even when a Kernighan-Lin style iterative improvement algorithm taking into vertex sizes is applied as a post-processing step. The standard spectral partitioning formulation is impractical for use in multi-level partitioning schemes since it requires a contraction method that produces nearly-equal-size clusters. To evaluate the new method for use in multi-level partitioning, we combine the partitioner with a multi-level bottom- up clustering algorithm and iterative refinement. Experimental results show that our new spectral algorithm is more effective than the standard spectral formulation and other partitioners in the multi-level partitioning of hypergraphs.
