A local graph rewiring algorithm for sampling spanning trees

Preprint number: CP3-Origins-2017-32 DNRF90
Authors: John Bulava (CP3-Origins) and Neal McBride (Trinity College Dublin)
External link: arXiv.org

We introduce a Markov Chain Monte Carlo algorithm which samples from the space of spanning
trees of complete graphs using local rewiring operations only. The probability distribution of graphs
of this kind is shown to depend on the symmetries of these graphs and these symmetries are reflected
in the equilibrium distribution of the Markov chain. We prove that the algorithm is ergodic and
proceed to estimate the probability distribution for small graph ensembles with exactly known
probabilities. The autocorrelation time of the graph diameter demonstrates that the algorithm
generates independent configurations efficiently as the system size increases. Finally, the mean
graph diameter is estimated for spanning trees of sizes ranging over three orders of magnitude. The
mean graph diameter results agree very closely with asymptotic values.