The power of choice in growing trees

DOI10.1140/EPJB/E2007-00310-5zbMATH Open1189.05157arXiv0704.1882OpenAlexW2093257776MaRDI QIDQ978747FDOQ978747

J. Martínez

Publication date: 25 June 2010

Published in: The European Physical Journal B. Condensed Matter and Complex Systems (Search for Journal in Brave)

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 tree and network 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 network 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 network 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.

Full work available at URL: https://arxiv.org/abs/0704.1882

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial probability (60C05) Stochastic network models in operations research (90B15)

Cites Work

• Emergence of Scaling in Random Networks
• Front propagation into unstable states
• Balanced Allocations
• Probability and Computing
• Parallel randomized load balancing
• On the profile of random trees
• Extreme value statistics and traveling fronts: Various applications

Cited In (12)

• Preferential attachment with choice
• Long and short paths in uniform random recursive dags
• Depth properties of scaled attachment random recursive trees
• Choices and intervals
• Random recursive hypergraphs
• Community modulated recursive trees and population dependent branching processes
• The degree profile in some classes of random graphs that generalize recursive trees
• The power of choice in the construction of recursive trees
• Longest Path Distance in Random Circuits
• Choice-driven phase transition in complex networks
• Profile of random exponential recursive trees
• Title not available (Why is that?)

This page was built for publication: The power of choice in growing trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q978747)