The power of choice in network growth
Raissa M. D’Souza,1, 2 Paul L. Krapivsky,3 and Cristopher Moore4, 2
1Department of Mechanical and Aeronautical Engineering, University of California, Davis, CA 95616
2and the Santa Fe Institute, Santa Fe, NM 87501
3Department of Physics, Boston University, Boston, MA 02215
4Computer Science Department, University of New Mexico, Albuquerque, NM 87131
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.
PACS numbers: 89.75.Hc,02.50.Ey,05.40.-a
I. FORMULATION OF THE MODEL
Over the past decade, the “power of choice” has
emerged as a theme in research on optimization and ran-
domized algorithms [1, 2, 3, 4]. Consider a random de-
cision process. Typically at each step of the process a
decision is reached by choosing one outcome at random
and accepting this choice. Now, rather then one random
alternative being presented at each decision point, let
a small set of randomly generated alternatives be pre-
sented, and let the best one be selected. It has been
shown that with as few as two alternatives at each deci-
sion point, the resulting properties of the process can be
radically altered. This was first explored in the context
of load-balancing the allocation of jobs arriving at ran-
dom times to a batch of processors. With as few as two
choices, the maximum load on any one processor drops
dramatically from O(logN) to O(log logN). Increasing
the number of choices beyond two only improves this by
a constant factor, illustrating the “power of two choices.”
Here we explore the effect of choice on random network
growth. Perhaps the simplest way to build a growing ran-
dom network is to attach each new node to an existing
node which is chosen uniformly at random. This pro-
cess generates random recursive trees which have been
studied in great detail (see e.g. [5, 6, 7, 8] and references
therein). Here we discuss a simple generalization: for
each new node we choose k > 1 existing ‘contact’ nodes
uniformly at random, select the ‘best’ one according to
some definition, and connect the new node to it. This
creates a random tree [9] whose statistics may be very
different from those of a random recursive tree.
We have to define, of course, the ‘quality’ of the node
so that we can choose the best one. One natural defi-
nition of quality in a tree is distance to the root — the
closer to the root, the better, so that the new node at-
taches to whichever one of its contacts is closest to the
root (and, if more than one contact has this smallest dis-
tance, we choose one of them randomly). This could cor-
respond, for instance, to someone joining a hierarchical
organization, and choosing to become a daughter node
of whichever one of their k contacts is highest up in the
hierarchy.
Another natural definition is to measure quality by
degree of the contact node: for instance, to attach the
new node to the contact node with highest degree, again
breaking ties randomly. Note that this is very different
from the preferential attachment process [10], where the
contact is selected from the entire graph with probabil-
ity proportional to its degree. This latter process requires
complete knowledge of the degree of all existing nodes.
In contrast, our model assumes that the new node pos-
sesses only a small amount of local information, namely,
the degrees of a small number of potential contacts. This
brings us to another motivation for this work: the desire
to understand the effects of limited, local information on
network growth.
For the smallest-depth model, we find a marked differ-
ence in behavior for k ≥ 2 versus k = 1. The measure of
interest in this case is the depth distribution (the frac-
tion of nodes at each depth j). For k = 1, i.e., a random
recursive tree, this distribution is Poisson. For k ≥ 2,
the same Poisson distribution is observed for distances
close to the root, however for larger distances the depth
distribution obeys a traveling wave solution. We also con-
sider using maximal depth, rather than minimal depth,
as the contact node selection criterion and find a similar
traveling-wave solution.
For the highest-degree model, we find that the degree
distribution decays exponentially for degree i > k. For
i < k the degree distribution exhibits power-law like be-
havior, thus in order to observe a power law for any sub-
stantial regime requires k � 1. In other words, a large
amount of (overhead/state/knowledge of the system) is
required to achieve a power law distribution.
Finally, in analogy to the above-referenced works on
load balancing, the lowest-degree model achieves a de-
gree distribution which is very close to uniform, in which
the maximum degree in the entire graph is O(log logN)
as opposed to the maximum degree in a Poisson distri-
bution, which is roughly O(logN).
II. SMALLEST DEPTH
Let N be the total number of nodes and Dj(N) be the
number of nodes at distance j from the root. By defini-
tion, D0(N) ≡ 1, since the root is distance 0 from itself.
Thus D0(N) is a deterministic quantity, while Dj(N)
with 1 ≤ j < N are random variables. We shall focus
on their averages Qj(N) ≡ 〈Dj(N)〉. An average value
provides a good description of a random variable when
it is large and hence fluctuations are relatively small; we
will see that this is indeed correct for D1(N).
To set the stage we begin in Sect. II A with the sim-
pler case of random recursive trees, for which everything
is already known (see e.g. [11]). We then consider the
influence of 2 or more choices in Sect. II B.
A. Random recursive trees and depth
The quantity Dj grows each time a node at distance
j − 1 is selected as the contact node. The average depth
distribution thus satisfies the master equation [12]
Qj(N + 1) = Qj(N) +
Qj−1(N) . (1)
This equation is exact and it applies even for j=0 if we
set Q−1(N) ≡ 0. Using the recursive nature of (1), we
first solve for Q1(N), then Q2(N), etc. This gives
Qj(N + 1) =
1≤m1<···<mj≤N
m1 × · · · ×mj
. (2)
Equivalently, we can recast the j-fold sums into simple
sums, although the results look less neat. For example,
Q1(N) = HN−1 (3a)
Q2(N) =
(HN−1)
2 −H(2)N−1
where H(p)N =
1≤n≤N n
−p are harmonic numbers. The
asymptotic behaviors of HN ≡ H
N , H
N , and other
harmonic numbers are well-known [13], and the resulting
asymptotics of the depth distribution are
Q1(N + 1) = lnN + γ +
+ · · ·
Q2(N + 1) =
(lnN)2 + γ lnN +
+ · · · ,
where γ ≈ 0.577 is the Euler-Mascheroni constant. Anal-
ogous results hold for Qj(N) for larger j.
If we merely want to establish the leading asymptotic
behavior, we can replace the summation in (2) by inte-
gration. This leads to the simple result
Qj(N)→
(lnN)j
showing that in the limit N → ∞, the depth distribu-
tion is Poisson with mean lnN . Alternatively, we can
derive (4) within a continuum approach by replacing fi-
nite differences by derivatives in the N →∞ limit of (1).
This procedure recasts discrete master equations into dif-
ferential equations
Qj−1 (5)
Solving (5) one recovers (4).
The normalization requirement
j≥0Dj(N) = N im-
plies the sum rule for the averages∑
Qj(N) = N (6)
The continuum approximation (4) agrees with the sum
rule (2) implying that it well approximates the depth
distribution in the entire range. We therefore use it to
find the depth of the recursive random tree. The depth
is defined as the maximal jmax. The criterion Qjmax = 1
leads to an estimate [11]
jmax = e lnN (7)
It is possible to derive this result within the exact (dis-
crete) approach and to determine the fluctuations of
jmax. However, for our purposes (7) is sufficient.
B. The model with k = 2 choices
Now suppose the new node has k = 2 choices. In this
case, we have Dj(N + 1) = Dj(N) + 1 if the two contact
nodes have minimum depth j−1, or equivalently, if both
of them have depth at least j−1, but if they do not both
have depth greater than j − 1. The probability of this is
i≥j−1
= N−2
D2j−1 + 2Dj−1∑
 . (8)
This leads to the exact recurrence
Qj(N + 1) = Qj(N) +N
D2j−1 + 2Dj−1
Unfortunately, this is not very helpful since the average of
the product of random quantities differs from the product
of their averages, viz. 〈DiDj〉 6= 〈Di〉〈Dj〉. One can, of
course, write down an exact recurrence for 〈DiDj〉, but
this involves third order moments 〈DiDjDk〉, and so on.
Thus the hierarchical nature of the governing equations
does not allow us to obtain complete and rigorous results
as is possible for the case k = 1.
The cases of j = 1, 2 are exceptional and one can de-
termine Q1 and Q2 analytically. For j = 1 the analysis is
especially simple since D0 = 1,
i≥1Di = N−1, and the
growth rate (8) simplifies to [1+2(N−1)]/N2. Therefore
the average number of the neighbors of the root grows ac-
cording to an exact and closed recurrence
Q1(N + 1) = Q1(N) +
2N − 1
Solving (9) subject to Q1(1) = 0 yields
Q1(N) =
2n− 1
= 2HN−1 −H
N−1 (10)
Similarly for j = 2 we use relation
i≥2Di = N−1−D1
and obtain
Q2(N + 1) = Q2(N) + 2
N − 1
Q1(N)−
〈D21(N)〉
To obtain a closed recurrence for Q2 we need to deter-
mine 〈D21(N)〉, the average of the square of the number
of neighbors of the root. Then (8) leads to
D1(N + 1) =
D1(N) + 1 prob N−2(2N − 1)
D1(N) prob 1−N−2(2N − 1)
Squaring this equation and averaging we obtain
〈D21(N + 1)〉 =
2N − 1
〈D21(N)〉
2N − 1
[〈D21(N)〉+ 2Q1(N) + 1]
= 〈D21(N)〉+ 2
2N − 1
Q1(N) +
2N − 1
Rather than directly solving this recurrence, we can use
it together with (9) to establish a simpler recurrence for
the variance V1(N) = 〈D21(N)〉 − 〈D1(N)〉2. We find
V1(N + 1) = V1(N) +
2N − 1
2N − 1
which is readily solved to give
V1(N + 1) = 2HN − 5H
N + 4H
Thus 〈D21〉 6= 〈D1〉2, yet the variance is asymptotically
2 lnN and therefore fluctuations of the random variable
D1 are indeed small compared to its average which grows
as 2 lnN , see (10).
We determined 〈D21(N)〉 = V1(N) +Q21(N) and there-
fore Q2 satisfies a closed solvable recurrence (11). The
solution reads
Q2(N) =
[Q1(N)]
2n− 1
V1(n) + [Q1(n)]2 +Q1(n)
For j ≥ 3, the problem becomes genuinely hierarchi-
cal and intractable. If we are seeking only the leading
behavior, however, we can proceed. When N � 1 and
j is sufficiently small, namely such that
i≤j Qi � N ,
we can replace the sum
i≥j Di by N and the growth
rate (8) by 2Dj−1/N . Thus we arrive at a set of differ-
ential equations
. (13)
Solving these equations we obtain
Qj(N) =
(2 lnN)j
. (14)
We check the validity of this approximation by substitut-
ing it back into our assumption
i≤j Qi � N which we
used in the derivation of (13). This suggests that (14)
holds when j < v lnN (i.e., for small distances from the
root) where v is the smallest positive root of
= 1 . (15)
We can write v in terms of Lambert’s function W (x),
defined as the root of WeW = x:
v = −1/W−1(−1/2e) (16)
where W−1 denotes the −1st branch of the Lambert func-
tion. Numerically, v = 0.373365...
When j ≥ v lnN we cannot use (14). However, as
long as Qj is much larger than 1, let us assume that the
fluctuations in Dj are small. In that case we can replace
averages 〈DjDk〉 by QjQk, and in this regime we obtain
= N−2
Q2j−1 + 2Qj−1∑
 . (17)
It is convenient to introduce the cumulative variable
Qi (18)
that is, the average fraction of nodes whose depth is at
least j. Summing (17) over all i ≥ j we arrive at a neat
recurrence
Nqj = q
j−1 . (19)
The form of this equation suggests the introduction of a
new ‘time’ variable
t = lnN . (20)
This transformation recasts (19) into
= −qj + q2j−1 (21)
which should be solved subject to the step function initial
condition: qj(0) = 1 for j ≤ 0 and qj(0) = 0 for j > 0.
Equation (21) has appeared in various contexts (see
e.g. [14]) and while it is unsolvable, an asymptotic be-
havior of its solution is understood. In the long time
limit, the solution approaches a ‘traveling wave’ form,
qj(t)→ q(j − vt) . (22)
Plugging (22) into (21) one finds that q(x) satisfies
= q(x)− q(x− 1)2 . (23)
The boundary conditions are
q(−∞) = 1, q(+∞) = 0 . (24)
The boundary-value problem (23)–(24) is still intractable
analytically. However, the velocity v can be determined
even without a complete solution for q(x). The method
relies on the analysis of the tail region x → −∞. One
notices that (23) admits an exponential solution in this
region,
1− q(x) ∝ eλx as x→ −∞ . (25)
Plugging this into (23) shows that the velocity v is related
to λ via the dispersion relation [14]
1− 2e−λ
The maximum of v = v(λ) is given by (15) and it oc-
curs at the largest positive root λ of the transcendental
equation 2(1 + λ) = eλ. This is
λ = −1−W−1(−1/2e) (27)
or numerically, λ = 1.67835... Comparing with (16), we
see that λ and v are related as follows,
λ = −1 + 1/v . (28)
Strictly speaking, one can only assert that velocity
does not exceed the maximum of (26). However, the
so-called selection principle tells us that this extremal
value is realized for any initial conditions which vanish
sufficiently rapidly at infinity. The selection principle has
been rigorously proven for a few nonlinear parabolic par-
tial differential equations. Yet heuristic arguments and
numerical evidence indicate that the its range of appli-
cability is much broader. This is reviewed in [15] in the
context of partial differential equations and in [16] in the
context of difference equations.
Thus there is a sharp front at depth jfront ≈ vt = v lnN
to leading order, where the depth of most nodes in the
tree is concentrated. Furthermore, the width of this front
remains finite even in the limitN →∞. It is also possible
to compute the sub-leading correction to the position of
the front [14], giving an improved estimate of its location:
jfront ≈ v lnN +
ln lnN . (29)
To estimate the maximum depth jmax, it is necessary to
bound the tail of q(x) in the positive direction x→ +∞.
To do this, note that by definition q(x) is monotonically
decreasing, and by (23) this implies that
q(x) ≤ q(x− 1)2
and therefore that this tail is doubly exponential,
q(x) ∝ e−A·2
for some constant A > 0. Setting q(x) = 1/N then gives
the estimate
jmax ≈ jfront +
ln lnN
minus a constant C = lnA/ ln 2. As shown in Fig. 1, (29)
and (31) are indeed excellent estimates of the average and
maximum depth respectively.
FIG. 1: The average depth (circles) and maximum depth
(crosses) of a tree with k = 2, averaged over 103 indepdent
trials for each value of N , and (dashed) the expressions (29)
and (31) for jfront and jmax respectively.
C. The effect of choice
At first sight, it seems that having two choices instead
of one does not qualitatively affect the outcome, since the
depth distributions (4) and (14) both seem Poissonian,
and both have typical depth O(log n). This is, however,
an illusion. First of all, the distribution (4) for random
recursive trees is indeed Poissonian while (14) is valid
only for j < v lnN . Secondly, while both types of trees
have depth O(log n), choice causes the depth to be much
more concentrated. This is easiest to see if we consider
the cumulative depth distribution (18). For random re-
cursive trees, qj(t) is asymptotically
qj(t) =
j − t
where erfc(z) is the error function
erfc(z) =
dη e−η
qj(t) =
1 j − t� −
0 j − t� +
The boundary layer where q changes from one to zero is
not a true front as its width grows with ‘time’ as
lnN .
On the other hand, for the model with choice the cu-
mulative depth distribution has a traveling wave shape
with a front of constant width. Thus
qj(t) =
1 j − jfront � −1
0 j − jfront � +1
D. Multiple choices
What if the new node has more than two choices? The
cases with k ≥ 3 (with k constant) are morally similar to
the k = 2 case: the cumulative depth distribution obeys
the differential equation
= −qj + qkj−1 . (34)
Transforming this to qj(t) = q(j−vt) as before, we obtain
= q(x)− q(x− 1)k . (35)
The solution is again a traveling wave, whose velocity v
depends on k. Assuming the selection principle, v is the
smallest positive root of
= 1 (36)
which can be written in terms of Lambert’s function as
v = −1/W−1(−1/ke) . (37)
Asymptotically, as k grows we have
ln ke+ ln ln ke
ln ln k
. (38)
A more precise estimate for jfront is again given by (29),
with λ given by (28). For j � jfront, (4) and (14) gener-
alize to
Qj(N) =
(k lnN)j
. (39)
Finally, the tail of q(x) is doubly exponential,
q(x) ≈ e−Ak
and the maximum depth is given by
jmax ≈ jfront +
ln lnN
. (41)
III. LARGEST DEPTH
We pause here to consider a model in which we reverse
our definition of the ‘better’ node, and attach each new
node to the contact node which is furthest from the root.
If k = 2, then we have Dj(N + 1) = Dj(N) + 1 whenever
the maximum depth of the two nodes is j − 1, and this
occurs with probability
(j−1∑
= N−2
D2j−1 + 2Dj−1
. (42)
For instance, the average number of the neighbors of the
root grows according to
Q1(N + 1) = Q1(N) +
and therefore
Q1(N) = H
N−1 . (44)
Thus the average number of neighbors of the root does
not diverge as in the smallest depth model, but instead
approaches the constant ζ(2) = π2/6. Generally, the
behavior of Qj(N) for small j is very different from (14),
viz. for j = O(1) the average number of nodes of depth j
remains finite in the N →∞ limit. Therefore in contrast
with the smallest depth model, the quantities Dj(∞) are
not self-averaging when j = O(1) and their averages do
not characterize them. Yet, the probability distribution
P (s) = Prob[D1(∞) = s] (45)
can be determined. For instance, D1(2) = 1 and the
probability that the root still has one neighbor when the
network size reaches N is
Prob[D1(N) = 1] =
and therefore
P (1) =
. (46)
Proceeding with this line of reasoning one obtains
P (s+ 1) =
2≤n1<···<ns
(n21 − 1)× · · · × (n2s − 1)
which can be expressed as a sum involving the zeta func-
tion at positive integers.
However, even though the Dj are not self-averaging,
there are many similarities between the smallest depth
model and this one. In particular, the cumulative depth
distribution has a traveling wave shape (22). Indeed, af-
ter several mappings [16] the model becomes identical to
one which has appeared in studies of collision processes in
gases [17], fragmentation processes [18], and other prob-
lems [14]. If we define the cumulative variable as
Qi , (47)
then writing qj(t) = q(j − vt) gives (19), (21) and (23)
again, but now with the boundary conditions
q(−∞) = 0, q(+∞) = 1 . (48)
With these boundary conditions, (23) admits a solution
whose tail in the positive direction is exponential,
1− q(x) ∝ e−µx as x→ +∞ (49)
and the dispersion relation is now
2eµ − 1
. (50)
The selection principle now suggests that v is the mini-
mum of (50). This is the larger of the two real roots of
the transcendental equation (15), which is v = 4.31107...
A more precise estimate of jfront is
jfront = v lnN −
ln lnN (51)
where µ = 0.768039... is the larger root of 2(1−µ) = e−µ.
More generally, for k > 2 the velocity v is the larger
real root of (36), or
v = −1/W1(−1/ke) (52)
which, as k grows, approaches
v ≈ ke− 1 . (53)
The position of the front is given by (51) with
µ = 1− 1/v . (54)
Finally, since the tail of q(x) in the positive direction is
given by (49), setting qj = 1 − 1/N gives the following
estimate of the maximum depth,
jmax = jfront +
lnN . (55)
Note that, unlike the minimum depth model, jmax−jfront
is O(logN) instead of O(log logN), since the tail (49) is
exponential rather than doubly exponential.
IV. HIGHEST DEGREE
We now consider a model in which quality is measured
not by depth, but by the degree of the contact node —
the higher the degree, the better. As we will show below,
in this case the degree distribution exhibits a power law
up to degree j ∼ k, beyond which it decays exponen-
tially. Therefore, in this model we need a large number
of choices, k � 1, in order to observe a power law over a
wide range of degrees.
A. Recurrence for the degree distribution
We start by writing a master equation for the degree
distribution of the network. We add one node at each
step, so at time t there are t nodes in the network.
Let Ni(t) be the number of nodes which have degree
i at time t, and let Ci(t) =
j=1Nj(t) be the corre-
sponding total number of nodes of degree i or less at
time t. Normalizing these numbers, let ai(t) = Ni(t)/t
be the fraction of nodes which have degree i, and let
ci(t) =
j=1 aj(t) = Ci(t)/t be the corresponding cu-
mulative distribution.
At each iteration, we choose k contact nodes at random
from the t existing nodes, and connect the new node to
the contact node of highest degree, with ties broken ran-
domly. The evolution of the expected cumulative degree
distribution can can be written as, for all i ≥ 1,
Ci(t+ 1) = Ci(t) + 1−
ci(t)
k − ci−1(t)k
, (56)
since Ci increases by 1 for each new node added, and
decreases precisely when the new node connects to a node
of degree i. This latter event occurs when all k nodes
have degree i or less, but not all have degree i−1 or less.
Writing ci(t) = Ci(t)/t and making the assumption that
a steady-state limit exists, we obtain the recurrence
ci = 1− (cki − c
i−1) . (57)
We note that in the case k = 1, where there is no choice,
the solution to (57) is simply
ci = 1− 2−i and ai = 2−i (58)
which is the degree distribution of a random recursive
tree.
B. The model with k ≥ 2 choices
We are particularly interested in the behavior for small
k. Recall that the “power of choice” comes from situa-
tions where results vary dramatically if k = 2 rather than
k = 1. For k ≥ 2 we can solve (57) analytically only in
the regime i � 1 as discussed in detail below. Yet, for
k = 2, equation (57) is very easy to solve numerically as
it reduces to the quadratic equation:
c2i + ci − (1 + c
i−1) = 0. (59)
Figure 2 is a plot of the degree distribution, ai, for k = 1
and k = 2. Recall ai = ci − ci−1. The data points are
from a numerical simulation with k = 2, grown to size
1×106 nodes. Note the excellent agreement. Though the
distribution for k = 2 decays less slowly than k = 1 both
exhibit exponential decay, thus the nature of the solution
is not altered with such minor amounts of choice.
From numerical simulation with k ≥ 2 we find different
behaviors for i > k than for i < k (see Fig. 3). For degree
i > k we observe ai ∼ exp(−i/k). For i < k we observe
what appears to be a power law in that regime, ai ∼ k−γ ,
with γ ≈ 1.5. The largest k we simulated was k = 32,
hence the “power law” regime is quite small. Rather
than computer simulation, we can look at the asymptotic
limits of (57) and arrive at these similar results in the
limit i � 1 and k � 1. Note, the asymptotic limit
will give γ = 1, and we can attribute the difference with
numerical results to finite size effects in simulation.
C. Asymptotic limits
In the asymptotic regime i � 1 we write ci = 1 − �i
and assume that �i � 1. To first order, cki = 1 − k�i.
Simplifying (57), we find (k+ 1)�i = k�i−1 and therefore
1− ci = Ak
k + 1
when i� 1, (60)
where Ak is a constant depending on k. We argue below
Ak ∼ k−1 as k →∞ (61)
In the rest of this section we always assume that k � 1.
Let us start with nodes of degree one (which are often
called ‘leaves’). In this case we have c1 = a1 and equa-
tion (57) reduces to
a1 = 1− ak1 . (62)
5 10 15 20
deg, i
FIG. 2: The degree distribution, ai, for the highest degree
model, for both k = 1 and k = 2. The points at data from
numerical simulation of the model with k = 2.
● ● ●●●●
●●●●●●●●●
●●●●●●●●●
●●●●●●●●●●●
●●●●●●●●●
1 2 5 10 20 50 100
deg, i
o k=16
a(i) ~ i^(−1.5)
a(i) ~ exp(−i/16)   
FIG. 3: Numerical simulation results for k = 16. Note that
for i < k we observe ai ∼ i−1.5, while for i > k we observe
i ∼ e−i/k.
Writing
a1 = 1−
and assuming that W � k yields ak1 = e−W . This allows
us to recast (62) into
WeW = k (64)
so W is Lambert’s function W (k). For large k, we have
W (k) ≈ ln k, justifying our assumption that W � k.
Thus almost all nodes are leaves: the fraction of nodes
whose degree exceeds one is 1−a1 = W (k)/k ≈ (ln k)/k.
Analyzing (57) for i = 2, 3, . . . one finds that the fol-
lowing ansatz is useful:
ci = 1−
W − wi
Plugging (65) into (57) we obtain
1 + ewi−1 − ewi = W−1wi (66)
Since W →∞ as k →∞, Eq. (66) simplifies to
1 + ewi−1 − ewi = 0 (67)
whose solution (satisfying w1 = 0) is wi = ln i. Plugging
this to (65) we find that ai = ci − ci−1 is given by
ai = k
−1 ln
when 2 ≤ i� k (68)
The upper bound i� k is necessary since we can use (67)
instead of (66) only when wi �W which is equivalent to
ln i� ln k. Note that we can further simplify (68) when
i� 1, viz.
when 1� i� k (69)
Thus up to a crossover at i = k, the degree distribution
exhibits an algebraic behavior ai ∼ i−1 with unusually
small exponent.
The derivation of (60) actually holds when i� k. Us-
ing (60) we compute ai = ci − ci−1 to give
ai = k
k + 1
when i� k (70)
The regions of the validity of (69) and (70) do not for-
mally overlap. It is reasonable to assume, however, that
they remain qualitatively correct. Then from Eq. (69)
we obtain ak ∼ k−2 while Eq. (70) leads to ak ∼ k−1Ak.
Matching this values we confirm the announced asymp-
totic of the amplitude, Eq. (61). Furthermore, we find
k + 1
≈ e−i/k when 1� k � i. (71)
V. LOWEST DEGREE
There are situations where one wants to ensure that all
nodes have low degree, for instance consider the case of
load-balancing discussed in Sec. I. Thus the final variant
we consider is when an incoming node connects to the
target node of lowest degree.
A. Recurrence for the degree distribution
As in Sec. IV, we begin by writing the master equa-
tion for the degree distribution of the network. Again
let Ni(t) be the number of nodes which have degree i
at time t, and now let Ci(t) =
j≥iNj(t) be the cor-
responding total number of nodes of degree i or greater
at time t. Normalizing, let ai(t) = Ni/t and let ci(t) =∑
j≥i aj(t) = Ci(t)/t be the complementary cumulative
distribution.
At each iteration, we choose k contact nodes at ran-
dom from the t existing nodes, and connect the new node
to the contact node of lowest degree, with ties broken
randomly. The evolution of the expected complementary
cumulative degree distribution can can be written, for all
i > 1, as
Ci(t+ 1) = Ci(t) +
ci−1(t)
k − ci(t)k
, (72)
since Ci increases precisely when the new node connects
to a node of degree i − 1. This event occurs when all
k nodes have degree i − 1 or greater, but not all have
degree i or greater. Writing ci(t) = Ci(t)/t and making
the assumption that a steady-state limit exists, we obtain
the recurrence
ci = c
i−1 − c
i . (73)
We note that in the case k = 1, where there is no choice,
the solution to (73) is simply
ci = 2
−(i−1) and ai = 2
−i (74)
which, as (58), is the degree distribution of a random
recursive tree.
B. The model with k ≥ 2 choices
For k = 2, (73) is very easy to solve numerically as it
reduces to the quadratic equation:
c2i + ci − c
i−1 = 0 . (75)
Figure 4 is a plot of the degree distribution, ai, for k = 1
and k = 2. Recall here, ai = ci − ci+1. The data points
are from a numerical simulation with k = 2, grown to
size 1 × 106 nodes. Note the excellent agreement. With
minor choice, the degree distribution is radically altered.
For all k ≥ 2 we can show the upper bound on the
maximum degree is O(log logN) using a method similar
to that in [19]. From (73), for i ≥ 3 we obtain the upper
bound, ci ≤ cki−1, and by recursion:
ci ≤ cki−1 ≤ c
2 , (76)
where K = k(i−2). Since c2 < 1, ci decreases doubly-
exponentially. To find imax, the typical largest degree
present after addition of N nodes, we set ci = 1/N . Solv-
ing this relation we find:
imax ≤ logk log1/c2 N = O(log logN). (77)
5 10 15 20
deg, i
FIG. 4: The degree distribution, ai, for the lowest degree
model, for both k = 1 and k = 2. The points at data from
numerical simulation of the model with k = 2.
VI. DISCUSSION
We explore the “power of choice” in network growth
by introducing a minimalist generalization of random re-
cursive trees. At each decision point k > 1 choices are
presented and the most desirable one selected. If the cri-
teria is to minimize or maximize network depth, a small
amount of choice has a dramatic effect. For k = 1 the
depth distribution decays with a Poisson behavior. For
k ≥ 2 this Poisson decay is seen for distances close to the
root, but for further distances, the depth distribution
obeys a traveling wave behavior. If the criteria instead
involves node degree, we must distinguish the maximum
degree model from the minimum degree one. For mini-
mum degree, choice has a dramatic effect. Going from
k = 1 to k = 2 the degree distribution changes from geo-
metric decay to double-exponential decay (and hence the
maximum degree observed in the network changes from
O(logN) to O(log logN)). In contrast, for maximum de-
gree, a large number of choices, k � 1, must be allowed
before a change from the k = 1 behavior is observed. The
degree distribution decays exponentially for all small val-
ues of k. Once k � 1 a power law distribution results
for nodes of degree i < k, while for nodes of degree i > k
the distribution decays exponentially.
We established many results about the depth distri-
bution. Some of them are exact, others (namely the
assumption that the maximum allowed value of veloc-
ity is realized, employed at the end of Sec. II B) utilize
a selection principle which is not rigorously established
for (21). There is no doubt of the validity of this principle
in a broad range of contexts, and there is firm numerical
support of all analytical results derived herein.
Acknowledgments. P.L.K. is thankful to CNLS (Los
Alamos National Laboratory) for hospitality during the
initial stage of this research, and to Renaud Lambiotte for
interesting correspondence. C.M. is supported by NSF
grant CCF-0524613 and ARO contract W911NF-04-R-
[1] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. In
Proc. 26th ACM Symp. Theory of Computing, 593–602
(1994).
[2] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, SIAM
J. Comp. 29, 180–200 (1999).
[3] M. Adler, S. Chakarabarti, M. Mitzenmacher, and
L. Rasmussen, Rand. Struct. Alg. 13, 159–188 (1998).
[4] M. Mitzenmacher and E. Upfal, Probability and Comput-
ing : Randomized Algorithms and Probabilistic Analysis
(Cambridge University Press, New York, 2005).
[5] R. T. Smythe and H. Mahmoud, Theory Probab. Math.
Statist. 51, 1–27 (1995).
[6] M. Drmota and B. Gittenberger, Random Struct. Alg.
10, 421–451 (1997); M. Drmota and H.-K. Hwang, Adv.
Appl. Probab. 37, 321–341 (2005).
[7] P. L. Krapivsky and S. Redner, Phys. Rev. Lett. 89,
258703 (2002); (cond-mat/0207370).
[8] S. Janson, Alea Lat. Am. J. Probab. Math. Stat. 1 347–
366 (2006); (math/0509471).
[9] We always assume that we start with a tree; we further
assume (if not stated otherwise) that the initial network
is a single node which is the root.
[10] A. L. Barabási and R. Albert, Science 286, 509–512
(1999).
[11] P. L. Krapivsky and S. Redner, Phys. Rev. E 63, 066123
(2001); (cond-mat/0011094).
[12] Equation (1) appears in many contexts, e.g. for networks
with copying: P. L. Krapivsky and S. Redner, Phys. Rev.
E 71, 036118 (2005); (cond-mat/0410379).
[13] R. L. Graham, D. E. Knuth, and O. Patashnik, Con-
crete Mathematics : A Foundation for Computer Science
(Reading, Mass.: Addison-Wesley, 1989).
[14] E. Ben-Naim, P. L. Krapivsky, and S. N. Majumdar,
Phys. Rev. E 64, 035101 (2001); (cond-mat/0105309).
[15] W. van Saarloos, Phys. Rep. 386, 29 (2003).
[16] S. N. Majumdar and P. L. Krapivsky, Physica A 318,
161–170 (2003); (cond-mat/0205581).
[17] R. van Zon, H. van Beijeren, and Ch. Dellago, Phys. Rev.
Lett. 80, 2035–2038 (1998).
[18] P. L. Krapivsky and S. N. Majumdar, Phys. Rev. Lett.
85, 5492–5495 (2000).
[19] M. Mitzenmacher, IEEE Trans. Paral. Dist. Sys. bf 12,
1094–1104 (2001).
http://arxiv.org/abs/cond-mat/0207370
http://arxiv.org/abs/math/0509471
http://arxiv.org/abs/cond-mat/0011094
http://arxiv.org/abs/cond-mat/0410379
http://arxiv.org/abs/cond-mat/0105309
http://arxiv.org/abs/cond-mat/0205581
	Formulation of the model
	Smallest Depth
	Random recursive trees and depth
	The model with k=2 choices
	The effect of choice
	Multiple choices
	Largest Depth
	Highest Degree
	Recurrence for the degree distribution
	The model with k 2 choices
	Asymptotic limits
	Lowest Degree
	Recurrence for the degree distribution
	The model with k2 choices
	Discussion
	References

  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.

The power of choice in network growth
Raissa M. D’Souza,1, 2 Paul L. Krapivsky,3 and Cristopher Moore4, 2
1Department of Mechanical and Aeronautical Engineering, University of California, Davis, CA 95616
2and the Santa Fe Institute, Santa Fe, NM 87501
3Department of Physics, Boston University, Boston, MA 02215
4Computer Science Department, University of New Mexico, Albuquerque, NM 87131
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.
PACS numbers: 89.75.Hc,02.50.Ey,05.40.-a
I. FORMULATION OF THE MODEL
Over the past decade, the “power of choice” has
emerged as a theme in research on optimization and ran-
domized algorithms [1, 2, 3, 4]. Consider a random de-
cision process. Typically at each step of the process a
decision is reached by choosing one outcome at random
and accepting this choice. Now, rather then one random
alternative being presented at each decision point, let
a small set of randomly generated alternatives be pre-
sented, and let the best one be selected. It has been
shown that with as few as two alternatives at each deci-
sion point, the resulting properties of the process can be
radically altered. This was first explored in the context
of load-balancing the allocation of jobs arriving at ran-
dom times to a batch of processors. With as few as two
choices, the maximum load on any one processor drops
dramatically from O(logN) to O(log logN). Increasing
the number of choices beyond two only improves this by
a constant factor, illustrating the “power of two choices.”
Here we explore the effect of choice on random network
growth. Perhaps the simplest way to build a growing ran-
dom network is to attach each new node to an existing
node which is chosen uniformly at random. This pro-
cess generates random recursive trees which have been
studied in great detail (see e.g. [5, 6, 7, 8] and references
therein). Here we discuss a simple generalization: for
each new node we choose k > 1 existing ‘contact’ nodes
uniformly at random, select the ‘best’ one according to
some definition, and connect the new node to it. This
creates a random tree [9] whose statistics may be very
different from those of a random recursive tree.
We have to define, of course, the ‘quality’ of the node
so that we can choose the best one. One natural defi-
nition of quality in a tree is distance to the root — the
closer to the root, the better, so that the new node at-
taches to whichever one of its contacts is closest to the
root (and, if more than one contact has this smallest dis-
tance, we choose one of them randomly). This could cor-
respond, for instance, to someone joining a hierarchical
organization, and choosing to become a daughter node
of whichever one of their k contacts is highest up in the
hierarchy.
Another natural definition is to measure quality by
degree of the contact node: for instance, to attach the
new node to the contact node with highest degree, again
breaking ties randomly. Note that this is very different
from the preferential attachment process [10], where the
contact is selected from the entire graph with probabil-
ity proportional to its degree. This latter process requires
complete knowledge of the degree of all existing nodes.
In contrast, our model assumes that the new node pos-
sesses only a small amount of local information, namely,
the degrees of a small number of potential contacts. This
brings us to another motivation for this work: the desire
to understand the effects of limited, local information on
network growth.
For the smallest-depth model, we find a marked differ-
ence in behavior for k ≥ 2 versus k = 1. The measure of
interest in this case is the depth distribution (the frac-
tion of nodes at each depth j). For k = 1, i.e., a random
recursive tree, this distribution is Poisson. For k ≥ 2,
the same Poisson distribution is observed for distances
close to the root, however for larger distances the depth
distribution obeys a traveling wave solution. We also con-
sider using maximal depth, rather than minimal depth,
as the contact node selection criterion and find a similar
traveling-wave solution.
For the highest-degree model, we find that the degree
distribution decays exponentially for degree i > k. For
i < k the degree distribution exhibits power-law like be-
havior, thus in order to observe a power law for any sub-
stantial regime requires k � 1. In other words, a large
amount of (overhead/state/knowledge of the system) is
required to achieve a power law distribution.
Finally, in analogy to the above-referenced works on
load balancing, the lowest-degree model achieves a de-
gree distribution which is very close to uniform, in which
the maximum degree in the entire graph is O(log logN)
as opposed to the maximum degree in a Poisson distri-
bution, which is roughly O(logN).
II. SMALLEST DEPTH
Let N be the total number of nodes and Dj(N) be the
number of nodes at distance j from the root. By defini-
tion, D0(N) ≡ 1, since the root is distance 0 from itself.
Thus D0(N) is a deterministic quantity, while Dj(N)
with 1 ≤ j < N are random variables. We shall focus
on their averages Qj(N) ≡ 〈Dj(N)〉. An average value
provides a good description of a random variable when
it is large and hence fluctuations are relatively small; we
will see that this is indeed correct for D1(N).
To set the stage we begin in Sect. II A with the sim-
pler case of random recursive trees, for which everything
is already known (see e.g. [11]). We then consider the
influence of 2 or more choices in Sect. II B.
A. Random recursive trees and depth
The quantity Dj grows each time a node at distance
j − 1 is selected as the contact node. The average depth
distribution thus satisfies the master equation [12]
Qj(N + 1) = Qj(N) +
Qj−1(N) . (1)
This equation is exact and it applies even for j=0 if we
set Q−1(N) ≡ 0. Using the recursive nature of (1), we
first solve for Q1(N), then Q2(N), etc. This gives
Qj(N + 1) =
1≤m1<···<mj≤N
m1 × · · · ×mj
. (2)
Equivalently, we can recast the j-fold sums into simple
sums, although the results look less neat. For example,
Q1(N) = HN−1 (3a)
Q2(N) =
(HN−1)
2 −H(2)N−1
where H(p)N =
1≤n≤N n
−p are harmonic numbers. The
asymptotic behaviors of HN ≡ H
N , H
N , and other
harmonic numbers are well-known [13], and the resulting
asymptotics of the depth distribution are
Q1(N + 1) = lnN + γ +
+ · · ·
Q2(N + 1) =
(lnN)2 + γ lnN +
+ · · · ,
where γ ≈ 0.577 is the Euler-Mascheroni constant. Anal-
ogous results hold for Qj(N) for larger j.
If we merely want to establish the leading asymptotic
behavior, we can replace the summation in (2) by inte-
gration. This leads to the simple result
Qj(N)→
(lnN)j
showing that in the limit N → ∞, the depth distribu-
tion is Poisson with mean lnN . Alternatively, we can
derive (4) within a continuum approach by replacing fi-
nite differences by derivatives in the N →∞ limit of (1).
This procedure recasts discrete master equations into dif-
ferential equations
Qj−1 (5)
Solving (5) one recovers (4).
The normalization requirement
j≥0Dj(N) = N im-
plies the sum rule for the averages∑
Qj(N) = N (6)
The continuum approximation (4) agrees with the sum
rule (2) implying that it well approximates the depth
distribution in the entire range. We therefore use it to
find the depth of the recursive random tree. The depth
is defined as the maximal jmax. The criterion Qjmax = 1
leads to an estimate [11]
jmax = e lnN (7)
It is possible to derive this result within the exact (dis-
crete) approach and to determine the fluctuations of
jmax. However, for our purposes (7) is sufficient.
B. The model with k = 2 choices
Now suppose the new node has k = 2 choices. In this
case, we have Dj(N + 1) = Dj(N) + 1 if the two contact
nodes have minimum depth j−1, or equivalently, if both
of them have depth at least j−1, but if they do not both
have depth greater than j − 1. The probability of this is
i≥j−1
= N−2
D2j−1 + 2Dj−1∑
 . (8)
This leads to the exact recurrence
Qj(N + 1) = Qj(N) +N
D2j−1 + 2Dj−1
Unfortunately, this is not very helpful since the average of
the product of random quantities differs from the product
of their averages, viz. 〈DiDj〉 6= 〈Di〉〈Dj〉. One can, of
course, write down an exact recurrence for 〈DiDj〉, but
this involves third order moments 〈DiDjDk〉, and so on.
Thus the hierarchical nature of the governing equations
does not allow us to obtain complete and rigorous results
as is possible for the case k = 1.
The cases of j = 1, 2 are exceptional and one can de-
termine Q1 and Q2 analytically. For j = 1 the analysis is
especially simple since D0 = 1,
i≥1Di = N−1, and the
growth rate (8) simplifies to [1+2(N−1)]/N2. Therefore
the average number of the neighbors of the root grows ac-
cording to an exact and closed recurrence
Q1(N + 1) = Q1(N) +
2N − 1
Solving (9) subject to Q1(1) = 0 yields
Q1(N) =
2n− 1
= 2HN−1 −H
N−1 (10)
Similarly for j = 2 we use relation
i≥2Di = N−1−D1
and obtain
Q2(N + 1) = Q2(N) + 2
N − 1
Q1(N)−
〈D21(N)〉
To obtain a closed recurrence for Q2 we need to deter-
mine 〈D21(N)〉, the average of the square of the number
of neighbors of the root. Then (8) leads to
D1(N + 1) =
D1(N) + 1 prob N−2(2N − 1)
D1(N) prob 1−N−2(2N − 1)
Squaring this equation and averaging we obtain
〈D21(N + 1)〉 =
2N − 1
〈D21(N)〉
2N − 1
[〈D21(N)〉+ 2Q1(N) + 1]
= 〈D21(N)〉+ 2
2N − 1
Q1(N) +
2N − 1
Rather than directly solving this recurrence, we can use
it together with (9) to establish a simpler recurrence for
the variance V1(N) = 〈D21(N)〉 − 〈D1(N)〉2. We find
V1(N + 1) = V1(N) +
2N − 1
2N − 1
which is readily solved to give
V1(N + 1) = 2HN − 5H
N + 4H
Thus 〈D21〉 6= 〈D1〉2, yet the variance is asymptotically
2 lnN and therefore fluctuations of the random variable
D1 are indeed small compared to its average which grows
as 2 lnN , see (10).
We determined 〈D21(N)〉 = V1(N) +Q21(N) and there-
fore Q2 satisfies a closed solvable recurrence (11). The
solution reads
Q2(N) =
[Q1(N)]
2n− 1
V1(n) + [Q1(n)]2 +Q1(n)
For j ≥ 3, the problem becomes genuinely hierarchi-
cal and intractable. If we are seeking only the leading
behavior, however, we can proceed. When N � 1 and
j is sufficiently small, namely such that
i≤j Qi � N ,
we can replace the sum
i≥j Di by N and the growth
rate (8) by 2Dj−1/N . Thus we arrive at a set of differ-
ential equations
. (13)
Solving these equations we obtain
Qj(N) =
(2 lnN)j
. (14)
We check the validity of this approximation by substitut-
ing it back into our assumption
i≤j Qi � N which we
used in the derivation of (13). This suggests that (14)
holds when j < v lnN (i.e., for small distances from the
root) where v is the smallest positive root of
= 1 . (15)
We can write v in terms of Lambert’s function W (x),
defined as the root of WeW = x:
v = −1/W−1(−1/2e) (16)
where W−1 denotes the −1st branch of the Lambert func-
tion. Numerically, v = 0.373365...
When j ≥ v lnN we cannot use (14). However, as
long as Qj is much larger than 1, let us assume that the
fluctuations in Dj are small. In that case we can replace
averages 〈DjDk〉 by QjQk, and in this regime we obtain
= N−2
Q2j−1 + 2Qj−1∑
 . (17)
It is convenient to introduce the cumulative variable
Qi (18)
that is, the average fraction of nodes whose depth is at
least j. Summing (17) over all i ≥ j we arrive at a neat
recurrence
Nqj = q
j−1 . (19)
The form of this equation suggests the introduction of a
new ‘time’ variable
t = lnN . (20)
This transformation recasts (19) into
= −qj + q2j−1 (21)
which should be solved subject to the step function initial
condition: qj(0) = 1 for j ≤ 0 and qj(0) = 0 for j > 0.
Equation (21) has appeared in various contexts (see
e.g. [14]) and while it is unsolvable, an asymptotic be-
havior of its solution is understood. In the long time
limit, the solution approaches a ‘traveling wave’ form,
qj(t)→ q(j − vt) . (22)
Plugging (22) into (21) one finds that q(x) satisfies
= q(x)− q(x− 1)2 . (23)
The boundary conditions are
q(−∞) = 1, q(+∞) = 0 . (24)
The boundary-value problem (23)–(24) is still intractable
analytically. However, the velocity v can be determined
even without a complete solution for q(x). The method
relies on the analysis of the tail region x → −∞. One
notices that (23) admits an exponential solution in this
region,
1− q(x) ∝ eλx as x→ −∞ . (25)
Plugging this into (23) shows that the velocity v is related
to λ via the dispersion relation [14]
1− 2e−λ
The maximum of v = v(λ) is given by (15) and it oc-
curs at the largest positive root λ of the transcendental
equation 2(1 + λ) = eλ. This is
λ = −1−W−1(−1/2e) (27)
or numerically, λ = 1.67835... Comparing with (16), we
see that λ and v are related as follows,
λ = −1 + 1/v . (28)
Strictly speaking, one can only assert that velocity
does not exceed the maximum of (26). However, the
so-called selection principle tells us that this extremal
value is realized for any initial conditions which vanish
sufficiently rapidly at infinity. The selection principle has
been rigorously proven for a few nonlinear parabolic par-
tial differential equations. Yet heuristic arguments and
numerical evidence indicate that the its range of appli-
cability is much broader. This is reviewed in [15] in the
context of partial differential equations and in [16] in the
context of difference equations.
Thus there is a sharp front at depth jfront ≈ vt = v lnN
to leading order, where the depth of most nodes in the
tree is concentrated. Furthermore, the width of this front
remains finite even in the limitN →∞. It is also possible
to compute the sub-leading correction to the position of
the front [14], giving an improved estimate of its location:
jfront ≈ v lnN +
ln lnN . (29)
To estimate the maximum depth jmax, it is necessary to
bound the tail of q(x) in the positive direction x→ +∞.
To do this, note that by definition q(x) is monotonically
decreasing, and by (23) this implies that
q(x) ≤ q(x− 1)2
and therefore that this tail is doubly exponential,
q(x) ∝ e−A·2
for some constant A > 0. Setting q(x) = 1/N then gives
the estimate
jmax ≈ jfront +
ln lnN
minus a constant C = lnA/ ln 2. As shown in Fig. 1, (29)
and (31) are indeed excellent estimates of the average and
maximum depth respectively.
FIG. 1: The average depth (circles) and maximum depth
(crosses) of a tree with k = 2, averaged over 103 indepdent
trials for each value of N , and (dashed) the expressions (29)
and (31) for jfront and jmax respectively.
C. The effect of choice
At first sight, it seems that having two choices instead
of one does not qualitatively affect the outcome, since the
depth distributions (4) and (14) both seem Poissonian,
and both have typical depth O(log n). This is, however,
an illusion. First of all, the distribution (4) for random
recursive trees is indeed Poissonian while (14) is valid
only for j < v lnN . Secondly, while both types of trees
have depth O(log n), choice causes the depth to be much
more concentrated. This is easiest to see if we consider
the cumulative depth distribution (18). For random re-
cursive trees, qj(t) is asymptotically
qj(t) =
j − t
where erfc(z) is the error function
erfc(z) =
dη e−η
qj(t) =
1 j − t� −
0 j − t� +
The boundary layer where q changes from one to zero is
not a true front as its width grows with ‘time’ as
lnN .
On the other hand, for the model with choice the cu-
mulative depth distribution has a traveling wave shape
with a front of constant width. Thus
qj(t) =
1 j − jfront � −1
0 j − jfront � +1
D. Multiple choices
What if the new node has more than two choices? The
cases with k ≥ 3 (with k constant) are morally similar to
the k = 2 case: the cumulative depth distribution obeys
the differential equation
= −qj + qkj−1 . (34)
Transforming this to qj(t) = q(j−vt) as before, we obtain
= q(x)− q(x− 1)k . (35)
The solution is again a traveling wave, whose velocity v
depends on k. Assuming the selection principle, v is the
smallest positive root of
= 1 (36)
which can be written in terms of Lambert’s function as
v = −1/W−1(−1/ke) . (37)
Asymptotically, as k grows we have
ln ke+ ln ln ke
ln ln k
. (38)
A more precise estimate for jfront is again given by (29),
with λ given by (28). For j � jfront, (4) and (14) gener-
alize to
Qj(N) =
(k lnN)j
. (39)
Finally, the tail of q(x) is doubly exponential,
q(x) ≈ e−Ak
and the maximum depth is given by
jmax ≈ jfront +
ln lnN
. (41)
III. LARGEST DEPTH
We pause here to consider a model in which we reverse
our definition of the ‘better’ node, and attach each new
node to the contact node which is furthest from the root.
If k = 2, then we have Dj(N + 1) = Dj(N) + 1 whenever
the maximum depth of the two nodes is j − 1, and this
occurs with probability
(j−1∑
= N−2
D2j−1 + 2Dj−1
. (42)
For instance, the average number of the neighbors of the
root grows according to
Q1(N + 1) = Q1(N) +
and therefore
Q1(N) = H
N−1 . (44)
Thus the average number of neighbors of the root does
not diverge as in the smallest depth model, but instead
approaches the constant ζ(2) = π2/6. Generally, the
behavior of Qj(N) for small j is very different from (14),
viz. for j = O(1) the average number of nodes of depth j
remains finite in the N →∞ limit. Therefore in contrast
with the smallest depth model, the quantities Dj(∞) are
not self-averaging when j = O(1) and their averages do
not characterize them. Yet, the probability distribution
P (s) = Prob[D1(∞) = s] (45)
can be determined. For instance, D1(2) = 1 and the
probability that the root still has one neighbor when the
network size reaches N is
Prob[D1(N) = 1] =
and therefore
P (1) =
. (46)
Proceeding with this line of reasoning one obtains
P (s+ 1) =
2≤n1<···<ns
(n21 − 1)× · · · × (n2s − 1)
which can be expressed as a sum involving the zeta func-
tion at positive integers.
However, even though the Dj are not self-averaging,
there are many similarities between the smallest depth
model and this one. In particular, the cumulative depth
distribution has a traveling wave shape (22). Indeed, af-
ter several mappings [16] the model becomes identical to
one which has appeared in studies of collision processes in
gases [17], fragmentation processes [18], and other prob-
lems [14]. If we define the cumulative variable as
Qi , (47)
then writing qj(t) = q(j − vt) gives (19), (21) and (23)
again, but now with the boundary conditions
q(−∞) = 0, q(+∞) = 1 . (48)
With these boundary conditions, (23) admits a solution
whose tail in the positive direction is exponential,
1− q(x) ∝ e−µx as x→ +∞ (49)
and the dispersion relation is now
2eµ − 1
. (50)
The selection principle now suggests that v is the mini-
mum of (50). This is the larger of the two real roots of
the transcendental equation (15), which is v = 4.31107...
A more precise estimate of jfront is
jfront = v lnN −
ln lnN (51)
where µ = 0.768039... is the larger root of 2(1−µ) = e−µ.
More generally, for k > 2 the velocity v is the larger
real root of (36), or
v = −1/W1(−1/ke) (52)
which, as k grows, approaches
v ≈ ke− 1 . (53)
The position of the front is given by (51) with
µ = 1− 1/v . (54)
Finally, since the tail of q(x) in the positive direction is
given by (49), setting qj = 1 − 1/N gives the following
estimate of the maximum depth,
jmax = jfront +
lnN . (55)
Note that, unlike the minimum depth model, jmax−jfront
is O(logN) instead of O(log logN), since the tail (49) is
exponential rather than doubly exponential.
IV. HIGHEST DEGREE
We now consider a model in which quality is measured
not by depth, but by the degree of the contact node —
the higher the degree, the better. As we will show below,
in this case the degree distribution exhibits a power law
up to degree j ∼ k, beyond which it decays exponen-
tially. Therefore, in this model we need a large number
of choices, k � 1, in order to observe a power law over a
wide range of degrees.
A. Recurrence for the degree distribution
We start by writing a master equation for the degree
distribution of the network. We add one node at each
step, so at time t there are t nodes in the network.
Let Ni(t) be the number of nodes which have degree
i at time t, and let Ci(t) =
j=1Nj(t) be the corre-
sponding total number of nodes of degree i or less at
time t. Normalizing these numbers, let ai(t) = Ni(t)/t
be the fraction of nodes which have degree i, and let
ci(t) =
j=1 aj(t) = Ci(t)/t be the corresponding cu-
mulative distribution.
At each iteration, we choose k contact nodes at random
from the t existing nodes, and connect the new node to
the contact node of highest degree, with ties broken ran-
domly. The evolution of the expected cumulative degree
distribution can can be written as, for all i ≥ 1,
Ci(t+ 1) = Ci(t) + 1−
ci(t)
k − ci−1(t)k
, (56)
since Ci increases by 1 for each new node added, and
decreases precisely when the new node connects to a node
of degree i. This latter event occurs when all k nodes
have degree i or less, but not all have degree i−1 or less.
Writing ci(t) = Ci(t)/t and making the assumption that
a steady-state limit exists, we obtain the recurrence
ci = 1− (cki − c
i−1) . (57)
We note that in the case k = 1, where there is no choice,
the solution to (57) is simply
ci = 1− 2−i and ai = 2−i (58)
which is the degree distribution of a random recursive
tree.
B. The model with k ≥ 2 choices
We are particularly interested in the behavior for small
k. Recall that the “power of choice” comes from situa-
tions where results vary dramatically if k = 2 rather than
k = 1. For k ≥ 2 we can solve (57) analytically only in
the regime i � 1 as discussed in detail below. Yet, for
k = 2, equation (57) is very easy to solve numerically as
it reduces to the quadratic equation:
c2i + ci − (1 + c
i−1) = 0. (59)
Figure 2 is a plot of the degree distribution, ai, for k = 1
and k = 2. Recall ai = ci − ci−1. The data points are
from a numerical simulation with k = 2, grown to size
1×106 nodes. Note the excellent agreement. Though the
distribution for k = 2 decays less slowly than k = 1 both
exhibit exponential decay, thus the nature of the solution
is not altered with such minor amounts of choice.
From numerical simulation with k ≥ 2 we find different
behaviors for i > k than for i < k (see Fig. 3). For degree
i > k we observe ai ∼ exp(−i/k). For i < k we observe
what appears to be a power law in that regime, ai ∼ k−γ ,
with γ ≈ 1.5. The largest k we simulated was k = 32,
hence the “power law” regime is quite small. Rather
than computer simulation, we can look at the asymptotic
limits of (57) and arrive at these similar results in the
limit i � 1 and k � 1. Note, the asymptotic limit
will give γ = 1, and we can attribute the difference with
numerical results to finite size effects in simulation.
C. Asymptotic limits
In the asymptotic regime i � 1 we write ci = 1 − �i
and assume that �i � 1. To first order, cki = 1 − k�i.
Simplifying (57), we find (k+ 1)�i = k�i−1 and therefore
1− ci = Ak
k + 1
when i� 1, (60)
where Ak is a constant depending on k. We argue below
Ak ∼ k−1 as k →∞ (61)
In the rest of this section we always assume that k � 1.
Let us start with nodes of degree one (which are often
called ‘leaves’). In this case we have c1 = a1 and equa-
tion (57) reduces to
a1 = 1− ak1 . (62)
5 10 15 20
deg, i
FIG. 2: The degree distribution, ai, for the highest degree
model, for both k = 1 and k = 2. The points at data from
numerical simulation of the model with k = 2.
● ● ●●●●
●●●●●●●●●
●●●●●●●●●
●●●●●●●●●●●
●●●●●●●●●
1 2 5 10 20 50 100
deg, i
o k=16
a(i) ~ i^(−1.5)
a(i) ~ exp(−i/16)   
FIG. 3: Numerical simulation results for k = 16. Note that
for i < k we observe ai ∼ i−1.5, while for i > k we observe
i ∼ e−i/k.
Writing
a1 = 1−
and assuming that W � k yields ak1 = e−W . This allows
us to recast (62) into
WeW = k (64)
so W is Lambert’s function W (k). For large k, we have
W (k) ≈ ln k, justifying our assumption that W � k.
Thus almost all nodes are leaves: the fraction of nodes
whose degree exceeds one is 1−a1 = W (k)/k ≈ (ln k)/k.
Analyzing (57) for i = 2, 3, . . . one finds that the fol-
lowing ansatz is useful:
ci = 1−
W − wi
Plugging (65) into (57) we obtain
1 + ewi−1 − ewi = W−1wi (66)
Since W →∞ as k →∞, Eq. (66) simplifies to
1 + ewi−1 − ewi = 0 (67)
whose solution (satisfying w1 = 0) is wi = ln i. Plugging
this to (65) we find that ai = ci − ci−1 is given by
ai = k
−1 ln
when 2 ≤ i� k (68)
The upper bound i� k is necessary since we can use (67)
instead of (66) only when wi �W which is equivalent to
ln i� ln k. Note that we can further simplify (68) when
i� 1, viz.
when 1� i� k (69)
Thus up to a crossover at i = k, the degree distribution
exhibits an algebraic behavior ai ∼ i−1 with unusually
small exponent.
The derivation of (60) actually holds when i� k. Us-
ing (60) we compute ai = ci − ci−1 to give
ai = k
k + 1
when i� k (70)
The regions of the validity of (69) and (70) do not for-
mally overlap. It is reasonable to assume, however, that
they remain qualitatively correct. Then from Eq. (69)
we obtain ak ∼ k−2 while Eq. (70) leads to ak ∼ k−1Ak.
Matching this values we confirm the announced asymp-
totic of the amplitude, Eq. (61). Furthermore, we find
k + 1
≈ e−i/k when 1� k � i. (71)
V. LOWEST DEGREE
There are situations where one wants to ensure that all
nodes have low degree, for instance consider the case of
load-balancing discussed in Sec. I. Thus the final variant
we consider is when an incoming node connects to the
target node of lowest degree.
A. Recurrence for the degree distribution
As in Sec. IV, we begin by writing the master equa-
tion for the degree distribution of the network. Again
let Ni(t) be the number of nodes which have degree i
at time t, and now let Ci(t) =
j≥iNj(t) be the cor-
responding total number of nodes of degree i or greater
at time t. Normalizing, let ai(t) = Ni/t and let ci(t) =∑
j≥i aj(t) = Ci(t)/t be the complementary cumulative
distribution.
At each iteration, we choose k contact nodes at ran-
dom from the t existing nodes, and connect the new node
to the contact node of lowest degree, with ties broken
randomly. The evolution of the expected complementary
cumulative degree distribution can can be written, for all
i > 1, as
Ci(t+ 1) = Ci(t) +
ci−1(t)
k − ci(t)k
, (72)
since Ci increases precisely when the new node connects
to a node of degree i − 1. This event occurs when all
k nodes have degree i − 1 or greater, but not all have
degree i or greater. Writing ci(t) = Ci(t)/t and making
the assumption that a steady-state limit exists, we obtain
the recurrence
ci = c
i−1 − c
i . (73)
We note that in the case k = 1, where there is no choice,
the solution to (73) is simply
ci = 2
−(i−1) and ai = 2
−i (74)
which, as (58), is the degree distribution of a random
recursive tree.
B. The model with k ≥ 2 choices
For k = 2, (73) is very easy to solve numerically as it
reduces to the quadratic equation:
c2i + ci − c
i−1 = 0 . (75)
Figure 4 is a plot of the degree distribution, ai, for k = 1
and k = 2. Recall here, ai = ci − ci+1. The data points
are from a numerical simulation with k = 2, grown to
size 1 × 106 nodes. Note the excellent agreement. With
minor choice, the degree distribution is radically altered.
For all k ≥ 2 we can show the upper bound on the
maximum degree is O(log logN) using a method similar
to that in [19]. From (73), for i ≥ 3 we obtain the upper
bound, ci ≤ cki−1, and by recursion:
ci ≤ cki−1 ≤ c
2 , (76)
where K = k(i−2). Since c2 < 1, ci decreases doubly-
exponentially. To find imax, the typical largest degree
present after addition of N nodes, we set ci = 1/N . Solv-
ing this relation we find:
imax ≤ logk log1/c2 N = O(log logN). (77)
5 10 15 20
deg, i
FIG. 4: The degree distribution, ai, for the lowest degree
model, for both k = 1 and k = 2. The points at data from
numerical simulation of the model with k = 2.
VI. DISCUSSION
We explore the “power of choice” in network growth
by introducing a minimalist generalization of random re-
cursive trees. At each decision point k > 1 choices are
presented and the most desirable one selected. If the cri-
teria is to minimize or maximize network depth, a small
amount of choice has a dramatic effect. For k = 1 the
depth distribution decays with a Poisson behavior. For
k ≥ 2 this Poisson decay is seen for distances close to the
root, but for further distances, the depth distribution
obeys a traveling wave behavior. If the criteria instead
involves node degree, we must distinguish the maximum
degree model from the minimum degree one. For mini-
mum degree, choice has a dramatic effect. Going from
k = 1 to k = 2 the degree distribution changes from geo-
metric decay to double-exponential decay (and hence the
maximum degree observed in the network changes from
O(logN) to O(log logN)). In contrast, for maximum de-
gree, a large number of choices, k � 1, must be allowed
before a change from the k = 1 behavior is observed. The
degree distribution decays exponentially for all small val-
ues of k. Once k � 1 a power law distribution results
for nodes of degree i < k, while for nodes of degree i > k
the distribution decays exponentially.
We established many results about the depth distri-
bution. Some of them are exact, others (namely the
assumption that the maximum allowed value of veloc-
ity is realized, employed at the end of Sec. II B) utilize
a selection principle which is not rigorously established
for (21). There is no doubt of the validity of this principle
in a broad range of contexts, and there is firm numerical
support of all analytical results derived herein.
Acknowledgments. P.L.K. is thankful to CNLS (Los
Alamos National Laboratory) for hospitality during the
initial stage of this research, and to Renaud Lambiotte for
interesting correspondence. C.M. is supported by NSF
grant CCF-0524613 and ARO contract W911NF-04-R-
[1] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal. In
Proc. 26th ACM Symp. Theory of Computing, 593–602
(1994).
[2] Y. Azar, A. Z. Broder, A. R. Karlin, and E. Upfal, SIAM
J. Comp. 29, 180–200 (1999).
[3] M. Adler, S. Chakarabarti, M. Mitzenmacher, and
L. Rasmussen, Rand. Struct. Alg. 13, 159–188 (1998).
[4] M. Mitzenmacher and E. Upfal, Probability and Comput-
ing : Randomized Algorithms and Probabilistic Analysis
(Cambridge University Press, New York, 2005).
[5] R. T. Smythe and H. Mahmoud, Theory Probab. Math.
Statist. 51, 1–27 (1995).
[6] M. Drmota and B. Gittenberger, Random Struct. Alg.
10, 421–451 (1997); M. Drmota and H.-K. Hwang, Adv.
Appl. Probab. 37, 321–341 (2005).
[7] P. L. Krapivsky and S. Redner, Phys. Rev. Lett. 89,
258703 (2002); (cond-mat/0207370).
[8] S. Janson, Alea Lat. Am. J. Probab. Math. Stat. 1 347–
366 (2006); (math/0509471).
[9] We always assume that we start with a tree; we further
assume (if not stated otherwise) that the initial network
is a single node which is the root.
[10] A. L. Barabási and R. Albert, Science 286, 509–512
(1999).
[11] P. L. Krapivsky and S. Redner, Phys. Rev. E 63, 066123
(2001); (cond-mat/0011094).
[12] Equation (1) appears in many contexts, e.g. for networks
with copying: P. L. Krapivsky and S. Redner, Phys. Rev.
E 71, 036118 (2005); (cond-mat/0410379).
[13] R. L. Graham, D. E. Knuth, and O. Patashnik, Con-
crete Mathematics : A Foundation for Computer Science
(Reading, Mass.: Addison-Wesley, 1989).
[14] E. Ben-Naim, P. L. Krapivsky, and S. N. Majumdar,
Phys. Rev. E 64, 035101 (2001); (cond-mat/0105309).
[15] W. van Saarloos, Phys. Rep. 386, 29 (2003).
[16] S. N. Majumdar and P. L. Krapivsky, Physica A 318,
161–170 (2003); (cond-mat/0205581).
[17] R. van Zon, H. van Beijeren, and Ch. Dellago, Phys. Rev.
Lett. 80, 2035–2038 (1998).
[18] P. L. Krapivsky and S. N. Majumdar, Phys. Rev. Lett.
85, 5492–5495 (2000).
[19] M. Mitzenmacher, IEEE Trans. Paral. Dist. Sys. bf 12,
1094–1104 (2001).
http://arxiv.org/abs/cond-mat/0207370
http://arxiv.org/abs/math/0509471
http://arxiv.org/abs/cond-mat/0011094
http://arxiv.org/abs/cond-mat/0410379
http://arxiv.org/abs/cond-mat/0105309
http://arxiv.org/abs/cond-mat/0205581
	Formulation of the model
	Smallest Depth
	Random recursive trees and depth
	The model with k=2 choices
	The effect of choice
	Multiple choices
	Largest Depth
	Highest Degree
	Recurrence for the degree distribution
	The model with k 2 choices
	Asymptotic limits
	Lowest Degree
	Recurrence for the degree distribution
	The model with k2 choices
	Discussion
	References
