The power of choice in growing trees

DOI10.1140/EPJB/E2007-00310-5MaRDI QIDQ978747zbMATH OpenOpenAlexFDO

Authors 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)

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)

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.

Recommendations

• The power of choice over preferential attachment
• The power of choice combined with preferential attachement
• The power of choice in the construction of recursive trees
• Preferential attachment with choice
• Random trees and general branching processes

Cites work

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

Cited in

(15)

• Preferential attachment with choice
• Long and short paths in uniform random recursive dags
• Depth properties of scaled attachment random recursive trees
• Choices and intervals
• A complementary view on the growth of directory trees
• Random recursive hypergraphs
• Longest path distance in random circuits
• The power of choice combined with preferential attachement
• 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
• Choice-driven phase transition in complex networks
• Profile of random exponential recursive trees
• scientific article; zbMATH DE number 1305528 (Why is no real title available?)
• The power of choice over preferential attachment

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)