Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions

DOI10.48550/ARXIV.1911.01503zbMATH Open1522.65008arXiv1911.01503OpenAlexW3162705107WikidataQ122909260 ScholiaQ122909260MaRDI QIDQ58516FDOQ58516

Authors: Eric Autrey, Daniel Carter, Gregory Herschlag, Zach Hunter, Jonathan C. Mattingly, Eric A. Autry, Daniel Carter, Gregory Herschlag, Zach Hunter, Jonathan C. Mattingly 

Publication date: 28 October 2019

Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)

Abstract: We develop a new Markov chain on graph partitions that makes relatively global moves yet is computationally feasible to be used as the proposal in the Metropolis-Hastings method. Our resulting algorithm can be made reversible and able to sample from a specified measure on partitions. Both of these properties are critical to some important applications and computational Bayesian statistics in general. Our proposal chain modifies the recently developed method called Recombination (ReCom), which draws spanning trees on joined partitions and then randomly cuts them to repartition. We improve the computational efficiency by augmenting the state space from partitions to spanning forests. The extra information accelerates the computation of the forward and backward proposal probabilities. We demonstrate this method by sampling redistricting plans and find promising convergence results on several key observables of interest.

Full work available at URL: https://arxiv.org/abs/1911.01503

Recommendations

• Metropolized multiscale forest recombination for redistricting
• A graph partitioning model of congressional redistricting
• Algorithms for gerrymandering over graphs
• Random walks and the universe of districting plans
• Local search algorithms for political districting

zbMATH Keywords

balanced graph partitioningMarkov chain Monte CarloMetropolis-Hastingsspanning trees

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Models of societies, social and urban evolution (91D10) Mathematical geography and demography (91D20) History, political science (91F10)

Cites Work

• Graph partitioning models for parallel computing
• The average number of spanning trees in sparse graphs with given degrees
• Spatial clustering of average risks and risk trends in Bayesian disease mapping
• Partitioning graphs to speedup Dijkstra's algorithm
• Assessing significance in a Markov chain without mixing
• Graph Partitioning and Graph Clustering
• Metropolized multiscale forest recombination for redistricting
• Automated Redistricting Simulation Using Markov Chain Monte Carlo
• Crime in Philadelphia: Bayesian Clustering with Particle Optimization

Cited In (5)

• Metropolized multiscale forest recombination for redistricting
• Spanning tree bounds for grid graphs
• Irreducibility of recombination Markov chains in the triangular lattice
• redist
• Random walks and the universe of districting plans

This page was built for publication: Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q58516)