Performance analysis for dynamic tree embedding in k-partite networks by random walk

We study the problem of dynamic tree embedding in k-partite networks G ^k and analyze the performance on inter-partition load distribution of the embedding. We show that, for ring-connected G ^k , if the embedding proceeds by taking uni-directional random walk at length randomly chosen from [0, Δ-1], where a is a multiple of k, the best-case performance is achievable at probability √(2πke ^-k ), which is much higher than the asymptotically-zero probability at which the worst-case performance may appear. We also show that the same probabilities hold also for fully-connected G ^k if the embedding proceeds by taking random walk at length randomly chosen from [2, ∞). When k=2 (bipartite networks), our results show that if we do the embedding under the above random-walk schemes in their corresponding networks, we will have 50 percent chance to achieve the best-case performance. We also analyze the performances for embedding in these two networks in the expected case, and observe an interesting fact that if a ring- or fully-connected G ^k contains equal-sized partitions, the expected-case performance matches that in the best case.