Spectral partitioning of graphs into compact, connected regions

Abstract

Partitioning a graph into regions that are both compact and connected is an important problem with applications in many areas, for example, circuit design, social network analysis, and electoral redistricting. Our work builds on existing ideas of spectral bipartitioning and Markov chain Monte Carlo (MCMC) recombination methods to provide a new method for partitioning graphs: spectral recombination. Previous methods utilized these ideas independently, for example, partitioning a graph directly using its spectrum or using MCMC recombination methods that do not rely on its spectrum. Our work represents a novel approach that combines the two ideas. We provide empirical evidence that spectral recombination methods generate partitions with low cut edge counts, that is, more compact regions with shorter boundaries. Moreover, we demonstrate that our base spectral recombination algorithm can be modified to prioritize different metrics, such as balanced vertex weights among regions. We note that there appears to be a trade-off between achieving low cut edge counts and maintaining approximate weight balance, illuminating an avenue for future research. Our code and data can be found at https://github.com/MaxFlorescence/spectral_redistricting.