The power of choice in network growth

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.

9 pages, 4 figures

References in corpus (10)

• Emergence of scaling in random networks
• Front propagation into unstable states
• Organization of Growing Random Networks
• Log-Networks
• Largest Lyapunov Exponent for Many Particle Systems at Low Densities
• Extreme Value Statistics and Traveling Fronts: Various Applications
• Traveling Waves, Front Selection, and Exact Nontrivial Exponents in a Random Fragmentation Problem
• Statistics of Lead Changes in Popularity-Driven Systems
• Extremal properties of random trees
• Congruence properties of depths in some random trees

Cited by in corpus (15)

• Scale-free networks with exponent one
• Preferential attachment with choice
• Depth properties of scaled attachment random recursive trees
• Long and short paths in uniform random recursive dags
• Choice-Driven Phase Transition in Complex Networks
• Preferential attachment with partial information
• Inverting the Achlioptas rule for explosive percolation
• Longest path distance in random circuits
• Random Recursive Hypergraphs
• Scale-free tree network with an ultra-large diameter
• Choices and intervals
• Network Growth with Feedback
• Some remarks on biased recursive trees
• High degree vertices in the Power of Choice model combined with Preferential Attachment
• Kinetics of Aggregation with Choice