# Linking and Cutting Spanning Trees
## 4 The Details
### Experimental Results
#### 4.3.2 Coupling Simulation  
As mentioned before, we obtained no general bounds on the coupling we presented. In fact, experimental simulation for the coupling does not converge for all classes of graphs. We obtained experimental convergence for cycle graph, as expected from Theorem 2, and for ladder graphs. For the remaining graphs we used an optimistic version of the coupling which always assumes that \(s_{y}\in U_{y}\) and that \(B^{*}\) fails. With these assumptions, all the cases which increase the distance between states are eliminated and the coupling always converges. Note that this approach does not yield sound coupling, but in practice we verified that this procedure obtained good experimental variation distance. Moreover, the variation distance estimation for these tests is not the simpler distance but the actual experimental variation distance, obtained by generating several experimental trees, such that in average each possible tree is obtained 100 times. The simulation of the path coupling proceeds by generating a path with \(e\ln V\) steps, essentially selecting two trees at distance \(e\ln V\) from each other. This path is obtained by computing \(e\ln V\) steps of the fast chain. Recall that our implementation and all simulations use the fast version of the chain. The simulation ends once this path contracts to size \(\ln V\). Let \(t^{\prime}\) be the number of steps in this process. Once this point is obtained, our estimate for mixing time is \(\hat{\tau}=t^{\prime}\ln V\). In general, we wish to obtain \(\hat{\tau}\) such that the probability that the two general chains \(X_{t}\) and \(X_{t}\) coalesce is at least 75%. Hence, we repeat this process four times and choose the second largest value of \(\hat{\tau}\) as our estimate. Table 1 summarizes results for the experimental variation distance. The number of possible spanning trees for each graph was computed with [PERSON]'s theorem. Then, we generated 100 times the number of possible trees, and we computed the variation distance. As stated above, we obtained good results for the variation distance, getting a median well below 25% for all tested graph topologies. We now present experimental results for larger graphs where we use the optimistic coupling. All experiments were conducted on a computer with an Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40 GHz with 4 cores and 32 GB of RAM. We present running times for different graph topologies and sizes in Figures 26-32. Note beforehand that the coupling estimate needs only to be computed once for each graph. Once the estimate is known, we can generate as many spanning trees as we want. Although the edge-swapping method is not always the faster compared with the random walk and [PERSON]'s algorithms, it is competitive in practice for **dmP** and **torus** graphs, and it is faster for **biK**, **cycle** and **sparse** (ladder) graphs. As expected, it is less competitive for **dense** graphs. Hence, experimental results seem to point out that the edge-swapping method is more competitive in practice for those instances that are harder for random walk-based methods, namely **biK** and **cycle** graphs. The results for **biK** and **dmP** are of particular interest as most real networks seem to include these kind of topologies, i.e., they include communities and they are scale-free [13]. \begin{table}
\begin{tabular}{l c c c} \hline \hline
**Graph** & \(|V|\) & **Median VD** & **Max VD** \\ \hline
**dense** & \(\{5,7\}\) & 0.060 & 0.194 \\
**biK** & \(\{8,10\}\) & 0.065 & 0.190 \\
**cycle** & \(\{16,20,24\}\) & 0.001 & 0.004 \\
**sparse** & \(\{10,14,20\}\) & 0.053 & 0.110 \\
**torus** & \(\{9,12\}\) & 0.094 & 0.383 \\
**dmP** & \(\{8,10,12\}\) & 0.069 & 0.270 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Variation distance (VD) for different graph topologies. Median and maximum VD computed over five runs for each network. Since **dmP** graphs are random, results for **dmP** were further computed over five different graphs for each size \(|V|\).