The power of 2 choices over preferential attachment

Yury Malyshkin, Elliot PaquettearXiv 2013 · DOI · arXiv

Abstract

We introduce a new type of preferential attachment tree that includes choices in its evolution, like with Achlioptas processes. At each step in the growth of the graph, a new vertex is introduced. Two possible neighbor vertices are selected independently and with probability proportional to degree. Between the two, the vertex with smaller degree is chosen, and a new edge is created. We determine with high probability the largest degree of this graph up to some additive error term.

Introduction

In the study of evolving networks, the Preferential Attachment (PA) model—popularized by Barabási and Albert—serves as a foundational framework for understanding how "hubs" form. The core principle is simple: "the rich get richer." New nodes entering the network are more likely to connect to existing nodes that already possess a high degree. While this accurately models the power-law degree distributions seen in the internet or citation networks, it results in a maximum degree that scales as $t^{1/2}$ for a network of size $t$.

In many practical systems, such as load balancing in distributed computing, these massive hubs represent single points of failure or congestion. This research investigates whether a minimal amount of choice can fundamentally alter this scaling behavior. By applying the "power of two choices" principle—a well-known concept in computer science where choosing the lesser-loaded of two random bins leads to exponential improvements in balance—the authors propose a "min-choice" variant of preferential attachment.

The Min-Choice Preferential Attachment Model

The authors define a growth rule for a min-choice preferential attachment tree that introduces a competitive element to the connection process. At each time step $m+1$:

  1. A new vertex $v_{m+1}$ is added to the graph.
  2. Two candidate vertices, $X^1$ and $X^2$, are selected from the existing graph. The selection is biased: each vertex is picked with a probability proportional to its current degree, following the standard PA rule.
  3. The new vertex $v_{m+1}$ connects to the candidate with the smaller degree. If the degrees are equal, a choice is made uniformly at random.

This mechanism creates a tension between the degree-biased selection (which favors hubs) and the min-choice connection rule (which favors smaller nodes).

Methodology and Mathematical Proof

The paper provides a rigorous probabilistic analysis of this model. The authors track the evolution of the network by defining $F_m(k)$ as the sum of degrees of all vertices with a degree of at least $k$. By treating the growth of the network as a Markov chain, they employ a four-step inductive proof to bound the maximum degree.

A critical component of the proof involves establishing precise initial estimates for the weights of low-degree vertices. These estimates rely on rational approximations to provide a solid base for the induction.

Calculated bounds for the initial degree estimates used in the inductive proof.

Following these initial estimates, the authors prove that the weight of high-degree vertices decays doubly exponentially. They then use concentration inequalities, such as Hoeffding’s and Chernoff bounds, to demonstrate that the probability of any vertex reaching an extremely high degree is vanishingly small. Finally, a coupling argument relates the model back to the classic "two-choice balls-and-bins" problem to establish a lower bound.

Key Insights: Breaking the Power Law

The most striking result of this work is the qualitative shift in the network's structure. In a standard PA model, the maximum degree grows polynomially ($t^{1/2}$). In the min-choice model, the maximum degree is suppressed to a nearly constant $\log \log t$.

Comparison between standard preferential attachment (left) and the min-choice model (right).

As shown in the visual comparison above, the standard model (left) is dominated by a few massive hubs. In contrast, the min-choice model (right) produces a much more distributed, "stringy" architecture. For a network of one billion nodes, the difference is staggering: a maximum degree of roughly 31,600 versus a maximum degree of approximately 5. This demonstrates that the "power of two choices" is robust enough to overcome the inherent "rich-get-richer" bias of preferential attachment.

Conclusion and Future Directions

This research proves that a tiny intervention in the connection logic of a growing network can lead to a massive change in its global properties. While the study focuses on the degree sequence, it opens several avenues for future work:

  • Graph Topology: Investigating the diameter of min-choice trees. The authors suspect these trees may have larger diameters than their standard PA counterparts.
  • Max-Choice Dynamics: Exploring the opposite rule—choosing the larger degree—which is conjectured to create even more extreme hubs ($m / \log m$).
  • Non-linear Attachment: Testing the limits of this effect under sublinear or superlinear attachment rules ($\text{degree}^\alpha$), where phase transitions in behavior are expected.

By showing that the $\log \log$ scaling is a fundamental property of min-choice dynamics even under degree-biased selection, this paper provides a powerful tool for designing more balanced and resilient evolving systems.

Summary updated

Abstract

We introduce a new type of preferential attachment tree that includes choices in its evolution, like with Achlioptas processes. At each step in the growth of the graph, a new vertex is introduced. Two possible neighbor vertices are selected independently and with probability proportional to degree. Between the two, the vertex with smaller degree is chosen, and a new edge is created. We determine with high probability the largest degree of this graph up to some additive error term.
BibTeX
@misc{malyshkin2013power,
  author = {Yury Malyshkin and Elliot Paquette},
  title = {{The power of 2 choices over preferential attachment}},
  year = {2013},
  eprint = {1311.1091},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1311.1091},
}
Figure