Influence of the link weight structure on the shortest path.
The shortest path tree rooted at a source to all other nodes is investigated in a graph with polynomial link weights tunable by the power exponent alpha. By varying alpha, different types of shortest path trees, in short alpha trees, appear. Especially, the alpha --> 0 regime that corresponds to heavily fluctuating link weights possesses a peculiar type of tree. The most important properties of this alpha --> 0 tree are derived in the asymptotic limit for large N. The application of the theoretical insights to real networks (such as the Internet) are discussed: steering flow by adjusting link weights (traffic engineering), sensitivity of link weights and modeling of the network by alpha trees.
Van Mieghem
Piet
P
Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands.
van Langen
Stijn
S