Intersection of Random Spanning Trees in Small-World Networks

Alon et al. [1] investigated the following 2-player zero-sum game on a connected graph G: tree player chooses a spanning tree T of G, while edge player chooses an edge e of G. The payoff to the edge player is defined by a function \(\textrm{cost}(T,e)\). It is a natural continuation of their work is to consider the case when both players are a tree player. This also leads us to the problem of intersection of random spanning trees, that is the number of common edges of two spanning trees of G chosen uniformly at random. In this paper we derive a lower bound for the minimum expected intersection and using bootstrap simulations we determine the empirical mean value for synthetic and real networks. Experiments show that for random model networks there is no significant difference between the two value. On the other hand, interestingly, for some real networks the observed empirical mean intersection highly differs from the minimum expected. Our finding may provide a new perspective of investigating real small-world networks and gives some new insights on the structure of them.