Sampling random spanning arborescences in graphs with low conductance

Vittorio Zampinetti, Harald Melin and Jens Lagergren

Statistics & Probability Letters, 2025, vol. 226, issue C

Abstract: Sampling random spanning arborescences in directed graphs is critical for applications in network analysis, optimization, and machine learning. While many state-of-the-art methods perform well on graphs with high conductance, they often fail or generalize poorly on low-conductance graphs. Inspired by Wilson’s algorithm, we propose a novel sampling approach that overcomes this limitation by using dynamic programming to compute random walk probabilities. This avoids both inefficient walk simulations and numerically unstable Laplacian determinant calculations. Our method demonstrates superior efficiency and sampling quality in simulations, and is the only one to handle low-conductance graphs effectively.

Keywords: Random tree sampling; Bayesian inference; Random walk; Wilson’s algorithm (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167715225001269
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:stapro:v:226:y:2025:i:c:s0167715225001269

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spl.2025.110481

Access Statistics for this article

Statistics & Probability Letters is currently edited by Somnath Datta and Hira L. Koul

More articles in Statistics & Probability Letters from Elsevier
Bibliographic data for series maintained by Catherine Liu ().