The power of choice in growing trees

R. M. D'Souza (), P. L. Krapivsky and C. Moore

The European Physical Journal B: Condensed Matter and Complex Systems, 2007, vol. 59, issue 4, 535-543

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. Copyright EDP Sciences/Società Italiana di Fisica/Springer-Verlag 2007

Keywords: 89.75.Hc Networks and genealogical trees; 02.50.Ey Stochastic processes; 05.40.-a Fluctuation phenomena; random processes; noise; and Brownian motion (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1140/epjb/e2007-00310-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurphb:v:59:y:2007:i:4:p:535-543

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/10051

DOI: 10.1140/epjb/e2007-00310-5

Access Statistics for this article

The European Physical Journal B: Condensed Matter and Complex Systems is currently edited by P. Hänggi and Angel Rubio

More articles in The European Physical Journal B: Condensed Matter and Complex Systems from Springer, EDP Sciences
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().