Performance Analysis for Dynamic Tree Embedding ink-Partite Networks by a Random Walk

We study the problem of dynamic tree embedding ink-partite networksG^kand analyze the performance on interpartition load distribution of the embedding. We show that, for ring-connectedG^k, if the embedding proceeds by taking a unidirectional random walk at a length randomly chosen from [0, Δ - 1], where Δ is a multiple ofk, the best-case performance is achievable at probability2π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 for fully connectedG^kif the embedding proceeds by taking a random walk at a length randomly chosen from [2, ∞). Whenk= 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 a 50% chance to achieve the best-case performance. We also analyze the performances for embedding in these networks in the expected case and observe the interesting fact that they match the performances in the best case when the network isk-partitionable into partitions of equal size.