  This work describes probabilistic methods for utilizing random spanning trees
generated via a random walk process. Goyal et al. showed that the union of
random spanning trees approximates the expansion of every cut of a graph.
First, we generalize the method by Goyal et al. for weighted graphs and show
that it is possible to approximate the expansion of every cut in a weighted
graph with the union of random spanning trees generated by a random walk on a
weighted graph. Second, we show that our union of random spanning trees is a
spectral sparsifier of the graph. Moreover, we show that $O(\log n
/\epsilon^2)$ random spanning trees are required in order to spectrally
approximate a bounded degree graph. This result closes a previously open
question on the number of random spanning trees required for saprsification.
Third, we show that our random spanning trees based construction provides
security features for virtual networks, in the context of Software-Defined
Networking. Network virtualization coupled with Software-Defined Networking
allows new on-demand management capabilities. We demonstrate such a service,
namely, on-demand efficient monitoring or anonymity. The proposed service is
based on network virtualization of expanders or sparsifiers over the physical
network. The defined virtual (or overlay) communication graphs coupled with a
multi-hop extension of Valiant randomization based routing lets us monitor the
entire traffic in the network, with a very few monitoring nodes. We propose
methods that theoretically improve services provided by existing monitoring or
anonymity networks, and optimize the degree of monitoring or anonymity.
