Metropolized Forest Recombination for Monte Carlo Sampling of Graph Partitions
From MaRDI portal
(Redirected from Publication:58516)
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.
Recommendations
Cites work
- Assessing significance in a Markov chain without mixing
- Automated Redistricting Simulation Using Markov Chain Monte Carlo
- Crime in Philadelphia: Bayesian Clustering with Particle Optimization
- Graph Partitioning and Graph Clustering
- Graph partitioning models for parallel computing
- Metropolized multiscale forest recombination for redistricting
- Partitioning graphs to speedup Dijkstra's algorithm
- Spatial clustering of average risks and risk trends in Bayesian disease mapping
- The average number of spanning trees in sparse graphs with given degrees
Cited in
(5)
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)
