The power of choice in growing trees |
| |
Authors: | R M D'Souza P L Krapivsky C Moore |
| |
Institution: | (1) Department of Mechanical and Aeronautical Engineering, University of California, Davis, CA 95616, USA;(2) The Santa Fe Institute, Santa Fe, NM 87501, USA;(3) Department of Physics, Boston University, Boston, MA 02215, USA;(4) Computer Science Department, University of New Mexico, Albuquerque, NM 87131, USA |
| |
Abstract: | The “power of choice” has been shown to radically alter the behavior of a number of
randomized algorithms. Here we explore the effects of choice on models of random tree growth.
In our models each new node has k randomly chosen contacts, where k > 1 is a constant.
It then attaches to whichever one of these contacts is most desirable in some sense, such as its
distance from the root or its degree. Even when the new node has just two choices,
i.e., when k = 2, the resulting tree can be very different from a random graph or tree. For instance,
if the new node attaches to the contact which is closest to the root of the tree, the
distribution of depths changes from Poisson to a traveling wave solution.
If the new node attaches to the contact with the smallest degree, the degree distribution
is closer to uniform than in a random graph, so that with high probability there are no nodes in the
tree with degree greater than O(log log N). Finally, if the new node attaches to the contact
with the largest degree, we find that the degree distribution is a power law with exponent -1
up to degrees roughly equal to k, with an exponential cutoff beyond that; thus, in this case,
we need k ≫ 1 to see a power law over a wide range of degrees. |
| |
Keywords: | 89 75 Hc Networks and genealogical trees 02 50 Ey Stochastic processes 05 40 -a Fluctuation phenomena random processes noise and Brownian motion |
本文献已被 SpringerLink 等数据库收录! |
|