提出新型马尔可夫链蒙特卡洛算法，实现更灵活的图划分采样。
The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
- 基于带标记边的生成树空间设计新采样路径
- 可在非生成树分布下实现收敛，突破传统算法限制
- 适合需要灵活生成红区划分方案的研究者
新颖的马尔可夫链蒙特卡洛（MCMC）方法已通过图划分实现了大规模红区规划方案的生成。然而，现有算法如可逆重组（RevReCom）和元胞森林重组（MFR）受限于与生成树相关的分布。本文提出标记边游走（MEW），一种在可调分布下对图划分空间进行采样的新MCMC算法。该算法在带标记边的生成树空间上运作，可计算转移概率以用于梅特罗波利斯-哈斯金斯算法。真实世界双图上的实证结果显示，其能在与生成树无关的目标分布下实现收敛。因此，MEW代表了集合生成灵活性的重要进展。
原文摘要 · Abstract (English)
Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans through graph partitioning. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) are constrained to sampling from distributions related to spanning trees. We introduce the marked edge walk (MEW), a novel MCMC algorithm for sampling from the space of graph partitions under a tunable distribution. The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities for use in the Metropolis-Hastings algorithm. Empirical results on real-world dual graphs show convergence under target distributions unrelated to spanning trees. For this reason, MEW represents an advancement in flexible ensemble generation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。