# The Magic of Networks Grown by Redirection

P. L. Krapivsky  Department of Physics, Boston University, Boston, MA 02215,
USA  Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA  S.
Redner  Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501, USA

###### Abstract

We highlight intriguing features of complex networks that are grown by
_redirection_. In this mechanism, a target node is chosen uniformly at random
from the pre-existing network nodes and the new node attaches either to this
initial target or to a neighbor of this target. This exceedingly simple
algorithm generates preferential attachment networks in an algorithmic time
that is linear in the number of network nodes $N$. Even though preferential
attachment ostensibly requires _global knowledge_ of the network, redirection
requires only _local knowledge_. We also show that changing just a _single_
attachment rate in linear preferential attachment leads to a non-universal
degree distribution. Finally, we present unexpected consequences of
redirection in networks with undirected links, where highly modular and non-
sparse networks arise.

##  I Introduction

Redirection is a natural mechanism to create growing networks. In a social
setting, you may meet somebody and ultimately befriend of one the friends of
your initial acquaintance. This redirection also underlies a growth mechanism
in Facebook, where you are encouraged to create new links to some of the
friends of your initial Facebook friend Jackson and Rogers (2007); Traud  _et
al._ (2012). The simplest implementation of redirection for networks where
each link has a prescribed directionality is the following (Fig. 1):

  1. 1.

A new node n picks a pre-existing node x from the network uniformly at random.

  2. 2.

With probability $0<1-r<1$, n attaches to ${\tt x}$.

  3. 3.

With probability $r$, n attaches to the (unique) ancestor node ${\tt y}$ of
${\tt x}$.

These steps are repeated until a network of a desired size is generated.

Figure 1: Illustration of redirection. The rate at which a new node
$\mathbf{n}$ attaches to the ancestor $\mathbf{y}$ of node $\mathbf{x}$ by
redirection is proportional to the number of upstream neighbors of
$\mathbf{y}$ (green nodes).

By construction, a network with a tree topology always remains a tree. While
it is straightforward to generalize to networks with loops by the new node
choosing multiple provisional targets, we focus on trees both for their
simplicity and because they illustrate many of the intriguing features of
networks that are grown by preferential attachment.

Without the redirection step, the above growth rules define a model that is
known as the _random recursive tree_ (RRT). We discuss this fundamental null
model Otter (1948) in Sec. II. Redirection represents a minimalist extension
of the RRT; this idea was suggested in Kleinberg  _et al._ (1999) and
developed in Krapivsky and Redner (2001). This latter work showed that
redirection is equivalent to _shifted linear preferential attachment_ , in
which the rate of attaching to a pre-existing network node of degree $k$ is
proportional to $k+\lambda$, with $\lambda=\frac{1}{r}-2$. This connection
highlights an fascinating aspect of redirection—it transforms a purely _local_
growth mechanism—namely the RRT plus redirection to the ancestor—into the
_global_ mechanism of linear preferential attachment. The motivation for
preferential attachment stems from the “rich get richer” parable Yule (1925);
Simon (1955); that is, popular high-degree nodes are more likely to attract
additional links merely by virtue of being popular. While enormous effort has
been devoted to understanding the properties of these types of networks (see,
e.g., Refs. Barabási and Albert (1999); Krapivsky  _et al._ (2000);
Dorogovtsev  _et al._ (2000); Dorogovtsev and Mendes (2002); Newman (2010)),
we will present, in Sec. III, a number of surprising and under-appreciated
features of preferential attachment.

As we will discuss in this section, networks that are built by the redirection
mechanism of Fig. 1 have a degree distribution that possesses a _non-
universal_ algebraic tail,

$\displaystyle N_{k}\sim\frac{N}{k^{\nu}}\,,\qquad\nu=1+\frac{1}{r}>2\,.$ (1)

The exponent must satisfy $\nu>2$ for all sparse networks whose degree
distribution has an algebraic tail. This bound follows from the identity
$\sum_{k\geq 1}kN_{k}=2L$ and the linear growth of the number of links $L$
with $N$, which is the defining property of sparse networks. For trees, in
particular, $\sum_{k\geq 1}kN_{k}=2L=2(N-1)$.

However, a disconcerting feature of several complex networks Kunegis  _et al._
(2013) is that they are apparently characterized by degree distributions with
tail exponent $\nu<2$, which violates the bound in Eq. (1). Mathematically,
this implies that the sum $\sum_{k\geq 1}kN_{k}$ grows superlinearly with $N$,
which cannot occur in sparse networks with $N_{k}\sim N/k^{\nu}$. An exponent
value $\nu<2$ may arise in densifying networks Lambiotte  _et al._ (2016);
Bhat  _et al._ (2016), where $L$ increases superlinearly with $N$.
Intriguingly, such an anomalously small exponent also occurs in _undirected_
growing trees that are generated by _complete_ redirection (Sec. IV.3). To be
consistent with the constraint $\sum_{k\leq N}kN_{k}\sim N$, the amplitude of
the degree distribution must grow sublinearly with $N$, namely

$N_{k}\sim\frac{N^{\nu-1}}{k^{\nu}}\,,~{}\qquad\nu<2\,.$ (2)

Networks grown by this parameter-free complete redirection mechanism: (a) are
highly modular; (b) have numerous macrohubs; (c) consist almost entirely of
leaves (nodes of degree 1); (d) the “core” of the network (nodes of degree
$k\geq 2$) comprises a vanishingly small fraction of the network as
$N\to\infty$; and (e) are non-self-averaging, namely, basic characteristics,
such as $N_{k}$ for any $k>1$, exhibit huge fluctuations from realization to
realization. In spite of the simplicity of complete redirection, there is
little analytical understanding of its intriguing consequences and these
represent an appealing future challenge.

We emphasize that the redirection algorithm is extremely efficient. To build a
network of $N$ nodes requires a computation time that scales linearly with
$N$, with a prefactor of the order of one. Redirection also allows one to
build networks with more general preferential attachment mechanisms, such as
sublinear preferential attachment, with nearly the same efficiency as the
original redirection algorithm (Sec. IV.2).

##  II The Random Recursive Tree (RRT)

We begin our discussion with the RRT, first introduced by Otter Otter (1948),
in which nodes are added to the network one by one. Each new node attaches to
a single “target” node that is chosen uniformly at random among the already
existing nodes; that is, the attachment $A_{k}=1$, for any degree $k$. By the
restriction that each new node has a single attachment point (equivalently,
the out degree of every node equals 1), the resulting network is a tree. If a
new node attaches to more than one pre-existing node, loops could form. The
degree distribution of a network with loops is modified only in the amplitude
of the degree distribution compared to growing trees. On the other hand,
topological features of networks with loops are different than trees, but our
focus is on the degree distribution, for which it is simplest to focus on tree
networks.

The growth rules of the RRT thus are:

  1. 1.

Pick one of the nodes of the RRT—defined as the target—with uniform
probability.

  2. 2.

Introduce a new node that links to the target node.

Starting with a single node, these two steps are repeated until the tree
reaches a desired number of nodes $N$.

Figure 2: A random recursive tree of 9 nodes, showing the ordering of the
nodes and each of their attachment points.

### The degree distribution

We first outline how to derive the exact degree distribution and then
determine the degree distribution in the limit $N\to\infty$. The degree state
of any network is characterized by the vector ${\bf
N}\equiv\\{N_{1},N_{2},\ldots\\}$, where $N_{k}$ denotes the number of nodes
of degree $k$. When a new node is introduced, the changes in the network state
vector ${\bf N}$ are Krapivsky and Redner (2002); Krapivsky  _et al._ (2010):

$\begin{split}&\mathrm{attach\ to\ node\ of\ degree\
1\\!:}~{}~{}~{}~{}~{}~{}~{}~{}\,(N_{1},N_{2})\to(N_{1},N_{2}+1)\\\
&\mathrm{attach\ to\ node\ of\ degree\
}k>1\\!:~{}~{}(N_{1},N_{k},N_{k+1})\to(N_{1}+1,N_{k}-1,N_{k+1}+1)\,,\end{split}$
(3)

while the state of all other network nodes are unchanged. Typically we are not
interested in the full probability distribution $P({\bf N})$, but just the
average number of nodes of a given degree, $\langle N_{k}\rangle$, namely, the
degree distribution; the angle brackets denote an average over all possible
growth histories of the network.

Let us determine how the $N_{k}$ change when a new node is added to the
network. As indicated by Eq. (3), we need to separately consider nodes of
degree 1 and nodes of degree greater than 1. The number of nodes of degree 1,
$N_{1}(N)$, is a random variable that changes with each node addition
according to

$N_{1}(N\\!+\\!1)=\begin{cases}N_{1}(N)&\qquad\mathrm{probability}\quad\frac{N_{1}}{N}\\\\[5.69054pt]
N_{1}(N)+1&\qquad\mathrm{probability}\quad 1-\frac{N_{1}}{N}\,.\end{cases}$
(4)

These equations apply for $N\geq 2$, while the natural initial condition is
$N_{1}(2)=2$. This equation expresses the two possibilities when a new node
joins the network: with probability $N_{1}/N$, the new node attaches to a node
of degree 1 and the number of such nodes does not change, while with
probability $(1-N_{1}/N)$, the new node attaches to a node of degree $k>1$ and
$N_{1}$ increases by 1.

The evolution equation for the average number of nodes of degree 1 therefore
is

$\displaystyle\big{\langle}N_{1}(N\\!+\\!1)\big{\rangle}$
$\displaystyle=\Big{\langle}N_{1}(N)\times\frac{N_{1}(N)}{N}\Big{\rangle}+\Big{\langle}\left(N_{1}(N)+1\right)\times\Big{(}1-\frac{N_{1}(N)}{N}\Big{)}\Big{\rangle}$
$\displaystyle=1+\Big{(}1-\frac{1}{N}\Big{)}\big{\langle}N_{1}(N)\big{\rangle}\,.$
(5)

Because the relevant time-like variable that characterizes the network size is
the total number of nodes $N$, we will always use $N$ as the time variable.
The solution to this recursion, for $N\geq 2$, is

$\big{\langle}N_{1}(N)\big{\rangle}=\frac{N}{2}+\frac{1}{(N-1)}~{}.$ (6)

The discrete approach can be used to determine higher moments of the random
variable $N_{1}(N)$. The second moment $\langle N_{1}^{2}(N)\rangle$ is
especially important as we can obtain the variance $\sigma^{2}=\langle
N_{1}^{2}(N)\rangle-\langle N_{1}(N)\rangle^{2}$ and thereby quantify degree
fluctuations. From Eq. (4), $\langle N_{1}^{2}(N)\rangle$ obeys the recursion

$\displaystyle\left\langle N_{1}^{2}(N+1)\right\rangle$
$\displaystyle=1+\left(1-\frac{2}{N}\right)\langle
N_{1}^{2}(N)\rangle+\left(2-\frac{1}{N}\right)\langle N_{1}(N)\rangle\,,$ (7)

whose solution is

$\displaystyle\left\langle
N_{1}^{2}(N)\right\rangle=\frac{N(3N+1)}{12}+\frac{N}{N-1}~{}.$ (8)

From the first two moments, the variance, for $N\geq 3$, is

$\displaystyle\sigma^{2}\equiv\left\langle
N_{1}^{2}(N)\right\rangle-\left\langle
N_{1}(N))\right\rangle^{2}=\frac{N}{12}-\frac{1}{(N-1)^{2}}~{},$ (9)

so the deviation of $N_{1}(N)$ from its average is of the order of $\sqrt{N}$.
Thus for large $N$, the number of nodes of degree 1 is sharply distributed
about its average value. For this reason, one may ignore fluctuations and
focus on the average number of nodes of degree 1. This same holds for all
nodes of higher degrees, so that again we focus on the average number of nodes
of any degree.

By similar reasoning as that used for $N_{1}$, the number of nodes of degree
$k\geq 2$, evolves according to

$N_{k}(N\\!+\\!1)=\begin{cases}N_{k}(N)-1&\qquad\mathrm{probability}\quad\frac{N_{k}}{N}\\\\[5.69054pt]
N_{k}(N)+1&\qquad\mathrm{probability}\quad\frac{N_{k-1}}{N}\\\\[5.69054pt]
N_{k}(N)&\qquad\mathrm{probability}\quad 1-\frac{N_{k-1}+N_{k}}{N}\end{cases}$
(10)

after each node addition. Following the same steps that led to Eq. (II), the
evolution equation for $\langle N_{k}\rangle$ is

$\left\langle N_{k}(N\\!+\\!1)\right\rangle=\left\langle
N_{k}(N)\right\rangle+\bigg{\langle}\frac{N_{k-1}(N)-N_{k}(N)}{N}\bigg{\rangle}.$
(11)

While this equation can again be solved to give the exact degree distribution
for finite networks, we now restrict ourselves to the leading behavior of the
degree distribution for $N\to\infty$. For simplicity, we drop the angle
brackets and the argument $N$, so that we write $N_{k}$ for the average number
of nodes of degree $k$ in a network that contains $N$ nodes. Next, we replace
the discrete differences with derivatives in Eqs. (II) and (11), so that the
asymptotic degree distribution evolves according to the master equation

$\dot{N}_{k}\equiv\frac{dN_{k}}{dN}=\frac{N_{k-1}-N_{k}}{N}+\delta_{k,1}~{}.$
(12a) The first equation is $\dot{N}_{1}=-{N_{1}}/{N}+1$, with solution
$N_{1}=N/2$. Then $\dot{N}_{2}=(N_{1}-N_{2})/{N}$, with solution $N_{2}=N/4$.
Continuing one finds that all the $N_{k}$ are proportional to $N$. Thus we
write $n_{k}\equiv N_{k}/N$ and reduce Eq. (12a) to
$n_{k}=n_{k-1}-n_{k}+\delta_{k,1}$ (12b)

leading to the exponential degree distribution $n_{k}=2^{-k}$.

##  III Preferential Attachment

In preferential attachment, the rate $A_{k}$ at which a node attaches to a
pre-existing node of degree $k$ is an increasing function of $k$. A ubiquitous
feature of preferential attachment networks is that their degree distributions
have broad tails, a fact that sparked much interest in this class of networks
over the past two decades. We now derive this scale-free degree distribution
using the approach of in Ref. Krapivsky and Redner (2001).

### Master equation

The evolution of the degree distribution for a network whose growth is
governed by an attachment rate $A_{k}$ is (compare with Eq. (12a) for the
RRT):

$\dot{N}_{k}=\frac{A_{k-1}N_{k-1}-A_{k}N_{k}}{A}+\delta_{k1}.$ (13)

The first term on the right accounts for the new node connecting to a pre-
existing node that already has $k-1$ links, thereby increasing $N_{k}$ by one.
Since there are $N_{k-1}$ nodes of degree $k-1$, the total rate at which such
processes occur is proportional to $A_{k-1}N_{k-1}$. The total rate $A\equiv
A(N)\equiv\sum_{j\geq 1}A_{j}N_{j}$ in the denominator means that $A_{k-1}/A$
is the probability for a node of degree $k-1$ to become a node of degree $k$.
A corresponding role is played by the second term on the right. The overall
amplitude of $A_{k}$ is immaterial, since only the ratio $A_{k}/A$ appears in
the master equation. The last term accounts for the introduction of a new node
that has one outgoing link and no incoming links. To determine the degree
distribution, we need to specify the attachment rate $A_{k}$. We focus on
power-law preferential attachment, $A_{k}=k^{\gamma}$, with $\gamma\geq 0$. We
will show that different behaviors arise for sublinear ($\gamma<1$),
superlinear ($\gamma>1$), and linear ($\gamma=1$) attachment rates. The linear
case is especially rich because the degree distribution is nonuniversal.

When confronted with determining a non-trivial distribution, it is often
instructive to first deal with the simpler problem of determining low-order
moments of the degree distribution
$M_{\alpha}(N)\equiv\sum_{j}j^{\alpha}N_{j}$. The zeroth and first moments of
this distribution have particularly simple $N$ dependences:
$\dot{M}_{0}=\sum_{j}\dot{N}_{j}=1$ and
$\dot{M}_{1}=\sum_{j}j\,\dot{N}_{j}=2$. The equation for $M_{0}$ states that
the total number of nodes (of any degree) increases by 1 each time a new node
is introduced. Similarly, the equation for $M_{1}$ states the total degree of
the network, $\sum jN_{j}$, increases by two when the single link associated
with the new node is added to the network. Since both the zeroth and first
moments of the degree distribution increase linearly with $N$, the total rate
$A=\sum_{j}j^{\gamma}N_{j}$ also grows linearly with $N$, because $A$ is
intermediate to the zeroth and first moments. Asymptotically, $A\simeq\mu N$,
with the as yet-undetermined amplitude $\mu$ that must range between 1 and 2
as $\gamma$ increases from 0 to 1.

Solving for the first few $N_{k}$ from Eq. (13), it becomes clear that each
$N_{k}$ is also proportional to $N$. This fact suggests substituting
$N_{k}(N)=n_{k}N$ and $A\simeq\mu N$ into these master equations. With this
step, the overall $N$ dependence cancels, leaving behind the recursion
relations $n_{k}=(A_{k-1}n_{k-1}-A_{k}n_{k})/\mu$ for $k>1$ and
$n_{1}=1-A_{1}n_{1}/\mu$. After straightforward algebra, the degree
distribution is

$n_{k}=\frac{\mu}{A_{k}}\prod_{1\leq j\leq
k}\left(1+\frac{\mu}{A_{j}}\right)^{-1}.$ (14a) Using the definition
$\mu=\sum_{j\geq 1}A_{j}n_{j}$ in (14a) we obtain $\sum_{k\geq 1}\prod_{1\leq
j\leq k}\left(1+\frac{\mu}{A_{j}}\right)^{-1}=1.$ (14b)

To extract the physical meaning of the general solution (14a) with $\mu$
implicitly determine by (14b) we examine the asymptotic behavior for the three
generic cases of sublinear, superlinear, and linear preferential attachment.

####  III.0.1 Sublinear preferential attachment

For $A_{k}=k^{\gamma}$ with $\gamma<1$, we rewrite the product in Eq. (14a) as
the exponential of a sum of logarithms, convert the sum to an integral, and
then expand the logarithm inside the integral in a Taylor series. These
straightforward steps lead to

$\displaystyle
n_{k}\sim\begin{cases}k^{-\gamma}\exp\left[-\mu\left(\frac{k^{1-\gamma}-2^{1-\gamma}}{1-\gamma}\right)\right]&\qquad\frac{1}{2}<\gamma<1,\\\
\\\
k^{(\mu^{2}-1)/2}\exp\left[-2\mu\,\sqrt{k}\right]&~{}~{}~{}~{}~{}~{}\qquad\gamma=\frac{1}{2},\\\
\\\
k^{-\gamma}\exp\left[-\mu\,\frac{k^{1-\gamma}}{1-\gamma}+\frac{\mu^{2}}{2}\,\frac{k^{1-2\gamma}}{1-2\gamma}\right]&\qquad\frac{1}{3}<\gamma<\frac{1}{2}\,,\end{cases}$
(15)

with similar, but more complicated expressions for $n_{k}$ for still smaller
values of $\gamma$. Each time $\gamma$ decreases through $\frac{1}{m}$, where
$m$ is an integer, an additional term is generated in the exponential that is
an increasing function of $k$. Nevertheless, for any value of $\gamma<1$, the
leading behavior is always the _universal_ stretched exponential decay,
$\exp(-{\rm const.}\times k^{1-\gamma})$.

####  III.0.2 Superlinear preferential attachment

For $\gamma>1$, a gelation-like phenomenon occurs in which nearly all links
attach to a single node. Let us first treat the ultra singular behavior that
arises for $\gamma>2$, for which there is a non-zero probability for a
“bible”to occur—a node that links to every other node in an infinite network,
while only a finite number of links exist between all other nodes. To
determine the probability for a bible, suppose that a network of $N+1$ nodes
contains a bible (Fig. 3). The probability that the next node links to the
bible is $N^{\gamma}/(N+N^{\gamma})$, and the probability that this pattern of
connections continues indefinitely is $\mathcal{P}=\prod_{N\geq
1}N^{\gamma}/(N+N^{\gamma})$. Using the same asymptotic analysis as above,
where we write the product as the exponential of a sum of logarithms, expand
the logarithm for large $N$, and approximate the sum as an integral, the
asymptotic behavior of this product is $\mathcal{P}=0$ for $\gamma\leq 2$, and
$\mathcal{P}>0$ for $\gamma>2$. Strikingly, there a non-zero probability for a
bible to exist in an infinite network for $\gamma>2$!

Figure 3: Creation of a “bible” in which each new node attaches only to the
bible (red).

When $1<\gamma<2$, the attachment pattern of low-degree nodes is not as simple
as in Fig. 3, but there continues to be a single node whose degree is of the
order of $N$. There is also an infinite sequence of transition points when
$\gamma$ passes through $\frac{m}{m-1}$, with $m$ an integer greater than 2,
in which number of nodes of degree $k\leq m$ grows as $N^{k-(k-1)\gamma}$,
while the number of nodes of degree $k>m$ remain finite for $N\to\infty$ (Fig.
4). To understand this behavior in a simple way, it is instructive to study
the governing equations for each $N_{k}$ one by one. For $N_{1}$ we have

$\displaystyle\dot{N}_{1}=1-\frac{N_{1}}{A}\,.$

We now make the assumption that the total attachment rate is governed by the
single highest-degree node, with degree of the order of $N$. Thus $A=\sum
j^{\gamma}N_{j}\sim N^{\gamma}$. Since $N_{1}$ can at most be of the order of
$N$, the second term in the above equation is negligible, so that
$\dot{N}_{1}\sim 1$ or $N_{1}\sim N$. Similarly, the equation for $N_{2}$ is

$\displaystyle\dot{N}_{2}\simeq\frac{N_{1}-2^{\gamma}N_{2}}{N^{\gamma}}\,.$

Again, neglecting the second term, gives $\dot{N}_{2}\simeq N^{1-\gamma}$,
from which $N_{2}\sim N^{2-\gamma}$. We can then verify that the term that we
dropped is indeed negligible. Continuing this self-consistent procedure for
general degree $k$, we find

$\displaystyle N_{k}\sim N^{k-(k-1)\gamma}\,,$ (16)

as long as the exponent of $N_{k}$ is positive, while $N_{k}$ will be finite
for $N\to\infty$ for values of $k$ for which $k-(k-1)\gamma$ is negative (Fig.
4).

Figure 4: Illustration of the sequence of phase transitions that arise in
superlinear preferential attachment. Starting with an ultra-condensed network
for $\gamma>2$, the network contains progressively more low-degree nodes each
time $\gamma$ passes through $m/(m-1)$. The network becomes sparse when
$\gamma$ reaches 1, where the number of nodes of any degree are all
proportional to $N$.

Thus we predict an infinite sequence of transitions at
$\gamma=\gamma_{m}=\frac{m}{m-1}$. For $\gamma>\gamma_{m}$, the number of
nodes of degree $k>m$ are all of $\mathcal{O}(1)$, while nodes of degrees
$k\leq m$ grows sublinearly with $N$, as $N^{k-(k-1)\gamma}$. This set of
transitions becomes progressively more dense as $\gamma\to 1$ from above. At
$\gamma=1$, the network changes its character from condensed, where a hub node
has degree of $\mathcal{O}(N)$, to sparse, where the number of nodes of any
degree is proportional to $N$.

####  III.0.3 Linear preferential attachment

Here, it is important to distinguish between _strictly linear_ preferential
attachment, $A_{k}=k$, and _asymptotically linear_ preferential attachment,
$A_{k}\simeq k$. In the former case, the total attachment rate is
$A=\sum_{k}A_{k}N_{k}=\sum_{k}kN_{k}=2N$. Substituting this value of $\mu=2$
into Eq. (14a) and performing some simple algebra immediately leads to the
discrete power-law form of the degree distribution

$n_{k}=\frac{4}{k(k+1)(k+2)}=\frac{4\,\Gamma(k)}{\Gamma(k+3)}~{},$ (17)

where $\Gamma$ is the Euler gamma function. From this power-law degree
distribution, the mean degree $\langle k\rangle=\sum_{k\geq 1}kn_{k}=2$, as it
must, but the mean-square degree $\langle k^{2}\rangle=\infty$. Thus
fluctuations in the mean degree, namely, the spread in the mean degree for
different realization of large networks of $N$ nodes, diverges for
$N\to\infty$.

The surprising feature of asymptotically linear preferential attachment growth
is that the degree distribution exponent is nonuniversal. This nonuniversality
is at odds with the common wisdom of statistical physics in which the absence
of a characteristic scale leads to universal scaling properties. One natural
form for an asymptotically linear attachment rate is $A_{k}=k+\lambda$, with
$\lambda$ a constant. This modification implies that the amplitude $\mu$ in
$A=\mu N$ is no longer equal to 2, but assume a wide range of values (see
below). Now Eq. (14a) becomes

$\displaystyle n_{k}=\frac{\mu}{A_{k}}\prod_{1\leq j\leq
k}\left(1+\frac{\mu}{A_{j}}\right)^{-1}$
$\displaystyle\sim\frac{\mu}{k}\exp\left[-\int_{1}^{k}\ln\left(1+\frac{\mu}{j}\right)\,dj\right]$
$\displaystyle\sim\frac{\mu}{k}\exp\left[-\mu\int_{1}^{k}\frac{dj}{j}\right]$
$\displaystyle\sim k^{-(1+\mu)}~{}.$ (18)

Thus the degree exponent $\nu=1+\mu$ can take any value larger than 2 merely
by tuning the amplitude $\mu$.

As an explicit and surprising example, consider the attachment rate $A_{k}=k$
for $k\geq 2$, while $A_{1}\equiv\alpha$ is arbitrary. It is now convenient to
separate $A_{1}$ and $A_{k}$ for $k\geq 2$ in Eq. (14a) to recast this
equation as

$\mu=A_{1}\sum_{k=2}^{\infty}\prod_{j=2}^{k}\left(1+\frac{\mu}{A_{j}}\right)^{-1}=\;\alpha\;\sum_{k=2}^{\infty}\Gamma(2+\mu)\,\frac{\Gamma(1+k)}{\Gamma(1+\mu+k)},$
(19)

where we express the product as the ratio of gamma functions.

The sum can be evaluated by employing the identity Graham  _et al._ (1994)

$\sum_{k=2}^{\infty}\frac{\Gamma(a+k)}{\Gamma(b+k)}=\frac{\Gamma(a+2)}{(b-a-1)\Gamma(b+1)}~{},$

so that Eq. (19) becomes $\mu(\mu-1)=2\alpha$, with solution
$\mu=(1+\sqrt{1+8\alpha})/2$. Thus the degree exponent $\nu=1+\mu$ is

$\nu=\frac{3+\sqrt{1+8\alpha}}{2}~{}.$ (20)

As examples, the degree distribution exponent is $\nu=4$ for $\alpha=3$ and
$\nu=5/2$ for $\alpha=3/8$. For $0<\alpha<1$, the exponent lies in the range
$2<\nu<3$, while for $\alpha>1$, $\nu>3$. While the degree distribution
exponent must satisfy the lower bound $\nu>2$, there is no upper bound for
$\nu$; in particular, $\nu\to\sqrt{2\alpha}$ as $\alpha\to\infty$. We
emphasize that changing just a _single_ attachment rate leads to a _global_
effect on the degree distribution. This global effect arises because the
amplitude $\mu$ appears inside the infinite product in Eq. (14a). This
multiplicative nature strongly affects the degree distribution itself and
thereby the degree distribution exponent.

##  IV Network Growth by Redirection

We now discuss a deceptively simple modification of the RRT with profound
consequences. This is the notion of _redirection_ where a new node may attach
to a pre-existing target node, or it to a neighbor of this target Kleinberg
_et al._ (1999); Krapivsky and Redner (2001).

###  IV.1 Constant redirection probability

First we treat the redirection algorithm Krapivsky and Redner (2001) that was
outlined in the introduction. There is one subtlety in this algorithm because
redirection requires that every node has an ancestor. To ensure this condition
always holds, the initial state, for example, could consist of at least two
nodes and one link, with each node defined as the ancestor of the other. Other
simple starting graphs are equally suitable, such as a triangle with cyclic
links.

According to the redirection algorithm, the degree distribution evolves
according to

$\displaystyle\dot{N}_{k}=\frac{1-r}{N}\Big{[}N_{k-1}-N_{k}+\delta_{k,1}\Big{]}+\frac{r}{N}\Big{[}(k-2)N_{k-1}-(k-1)N_{k}+\delta_{k,1}\Big{]}\,.$
(21a) The terms within the first square brackets correspond to attachment to
the initially selected node, whose evolution equation is just that of the RRT
(Eq. (12a)) for redirection probability $r=0$. The terms within the second
square brackets account for the change in $N_{k}$ due to redirection. To
understand their origin, consider first the gain term. Since the initial node
is chosen uniformly, if redirection does occur, then the probability that a
node of degree $k-1$ receives the newly redirected link is proportional to the
number of its upstream neighbors (green nodes in Fig. 1), which equals $k-2$.
A parallel argument applies for the redirection-driven loss term. The crucial
point is that the rate at which attachment occurs to a given node is
proportional to the number of its upstream neighbors, which, in turn, is
proportional its degree. Thus linear preferential attachment is implicit in
this purely local redirection rule.

The redirection mechanism has an unexpected connection to the friendship
paradox Hodas and Kooti (2013); Eom and Jo (2014), which states that the
neighbors of a randomly selected node are more popular (have higher degrees),
on average, than the initially selected node. As illustrated in Fig. 1, there
are three distinct ways to attach node $\mathbf{y}$ by redirection from
upstream nodes. The higher the degree of node $\mathbf{y}$, the more likely
attachment to it by redirection occurs. Thus we expect that node $\mathbf{y}$
will have more neighbors, on average, than the initial node $\mathbf{x}$

By a straightforward rearrangement of terms, (21a) may be re-expressed as

$\displaystyle\dot{N}_{k}$
$\displaystyle=\frac{r}{N}\left\\{\left[k-1+\left(\frac{1}{r}-2\right)\right]N_{k-1}-\left[k+\left(\frac{1}{r}-2\right)\right]N_{k}\right\\}+\delta_{k,1}$
$\displaystyle\equiv\frac{1}{A}\Big{\\{}\left(k-1+\lambda\right)N_{k-1}-\left(k+\lambda\right)N_{k}\Big{\\}}+\delta_{k,1}\,,$
(21b)

with $\lambda=\frac{1}{r}-2$ and total attachment rate $A=N/r=(2+\lambda)N$.
Thus uniform attachment, in conjunction with redirection, generates _shifted
linear preferential attachment_ , with $A_{k}=k+\lambda$. The particular case
of _strictly_ linear preferential attachment arises for the choice
$r=\frac{1}{2}$. When we now substitute attachment rate $A_{k}=k+\lambda$ and
$\mu=2+\lambda$ into the general formula (14a) for the degree distribution, we
obtain

$\displaystyle n_{k}=\frac{\mu}{A_{k}}\prod_{1\leq j\leq
k}\left(1+\frac{\mu}{A_{j}}\right)^{-1}=(2+\lambda)\frac{\Gamma(3+2\lambda)}{\Gamma(1+\lambda)}\frac{\Gamma(k+\lambda)}{\Gamma(k+3+2\lambda)}\sim
k^{-(3+\lambda)}\,.$ (21c)

Since the redirection probability lies between 0 and 1, the additive shift
$\lambda$ lies between $-1$ and $\infty$. Thus the degree distribution
exponent can take on _any_ value that is greater than 2. In the extreme case
of $r=1$ a star-like network arises whose detailed structure depends on the
initial condition.

It is also worth mentioning the many intriguing results that emerge from
simple extensions of this redirection mechanism. Starting with the RRT, each
node has a genealogical tree of ancestors. It is natural to grow a network in
which redirection can occur equiprobably to any node in the genealogical tree
of an initial target node Ben-Naim and Krapivsky (2010), or to all nodes in
this genealogical tree Krapivsky and Redner (2005). The latter leads to a
network that is no longer sparse, as the number of links $L$ grows as $N\ln
N$. Amusingly, this redirection mechanism to all encestors is isomorphic to a
basic hypergraph model, known as the random recursion hypergraph Krapivsky
(2023).

Finally, we wish to emphasize the extreme simplicity of this redirection
algorithm. Each node addition requires only two elemental operations: (i)
select a target node, and (ii) choose to attach either to this target or to
its ancestor. This algorithm allows one to generate a network of $N$ nodes in
roughly $2N$ algorithmic steps. It is therefore possible to quickly generate
very large networks. Crucially, a purely _local_ rule—tracking the ancestor of
each node—is equivalent to the _global_ rule that underlies preferential
attachment. Ostensibly, one needs to know the degrees of all the nodes in the
network to implement preferential attachment. As the redirection algorithm
shows, this global information is not needed.

###  IV.2 Degree-based redirection

To illustrate the utility and generality of redirection, we exploit the local
information that is readily available—the degree $a$ of the initial target
node and the degree $b$ of the ancestor—to efficiently generate sublinear
preferential attachment networks. In degree-based redirection Gabel and Redner
(2013), we merely define the redirection probability $r$ to be a suitably
chosen function of these two degrees $a$ and $b$; that is $r=r(a,b)$ (see Fig.
5).

Figure 5: Illustration of degree-based redirection. A new node (blue) attaches
to a random target of degree $a$ with probability $1-r(a,b)$ and attaches to
the ancestor node (degree $b$) of the target with probability $r(a,b)$.

To show how sublinear preferential attachment can be achieved from this still-
local information, we define $f_{k}$ as the total probability that an incoming
link is redirected _from_ a randomly selected target node of degree $k$ to the
parent of this target. Similarly, we define $t_{k}$ as the total probability
that an incoming link is redirected _to_ a parent node of degree $k$ after the
incoming node initially selected one of the child nodes of this parent.
Formally, these probabilities are defined in terms of the redirection
probabilities by

$f_{k}=\sum_{b\geq 1}\frac{r(k,b)N(k,b)}{N_{k}}\,,\qquad\qquad
t_{k}=\sum_{a\geq 1}\frac{r(a,k)N(a,k)}{(k-1)N_{k}}\,,$ (22)

where $N_{k}=\sum_{b\geq 1}N(k,b)$ and $N(a,b)$ is the correlation function
that specifies the number of nodes of degree $a$ that have a parent of degree
$b$. Thus $f_{k}$ is the mean redirection probability averaged over all
$N_{k}$ possible target nodes of degree $k$. Likewise, since each node of
degree $k$ has $k-1$ children, there are $(k-1)N_{k}$ possible target nodes
whose redirection probabilities are averaged to give $t_{k}$.

In terms of these probabilities $f_{k}$ and $t_{k}$, the master equation that
governs the evolution of $N_{k}$ is

$\dot{N}_{k}=\frac{(1\\!-\\!f_{k\\!-\\!1})N_{k-1}-(1\\!-\\!f_{k})N_{k}}{N}+\frac{(k\\!-\\!2)t_{k-1}N_{k\\!-\\!1}-(k-1)t_{k}N_{k}}{N}+\delta_{k,1}.$
(23)

The first ratio corresponds to instances of network growth for which the
incoming node actually attaches to the initial target. For example, the term
$(1-f_{k})N_{k}/N$ gives the probability that one of the $N_{k}$ target nodes
of degree $k$ is randomly selected and that the link from the new node is
_not_ redirected away from this target. Similarly, the second ratio
corresponds to instances in which the link to the target node _is_ redirected
to the ancestor. For example, the term $(k-1)t_{k}N_{k}/N$ gives the
probability that one of the $(k-1)N_{k}$ children of nodes of degree $k$ is
chosen as the target and that the new node _is_ redirected. Lastly, the term
$\delta_{k,1}$ accounts for the newly added node of degree 1.

By rearranging terms, we can express (23) in the generic form of Eq. (13),
with the attachment rate

$\frac{A_{k}}{A}=\frac{(k-1)t_{k}+1-f_{k}}{N}\,,$ (24a) whose asymptotic
behavior is $A_{k}\sim k\,t_{k}$. Thus a redirection probability $r(a,b)$ for
which $t_{k}$ is a decreasing function of $k$ will asymptotically correspond
to sublinear preferential attachment. A natural choice for such a redirection
probability is $r(a,b)=b^{\gamma-1}$, with $0<\gamma<1$, so that the
redirection probability decreases as the degree of the parent node increases.
Because $r$ depends only on the degree of the parent node (Fig. 5), Eq. (22)
reduces to $t_{k}=k^{\gamma-1}$. Using this form of $t_{k}$ in Eq. (24a)
yields $\frac{A_{k}}{A}=\frac{k^{\gamma}-k^{\gamma-1}+1-f_{k}}{N}\,,$ (24b)

whose leading behavior is indeed sublinear preferential attachment, $A_{k}\sim
k^{\gamma}$. Because of this equivalence to sublinear preferential attachment,
we can generate a network of $N$ nodes with stretched exponential degree
distribution in an algorithmic time that is also of the order of $N$.

What happens in the opposite case of _enhanced_ redirection, in which the
redirection probability is an increasing function of the degree of the parent
node Gabel and Redner (2013); Gabel  _et al._ (2014)? This attachment rule
leads to highly modular networks that contains multiple macrohubs, with most
nodes having degree 1 (leaves). Furthermore, the degree distribution exhibits
the anomalous scaling given in Eq. (2), with $\nu$ strictly less than 2\.
Similar phenomenology also occurs in the simpler example of redirection rule
for undirected networks (see below).

###  IV.3 Complete redirection in undirected networks

Link directionality is important in social and technological networks, but
there are many situations where networks are undirected Diestel (2017); Drmota
(2009); Frieze and Karoński (2016). The influence of redirection on undirected
networks is profound and there is little analytical understanding of this
enigmatic case.

The growth rule for isotropic redirection is nearly the same as that given in
Sec. IV for directed networks, but with a small but profound difference
Krapivsky and Redner (2017); Levens  _et al._ (2022) that is embodied by the
following growth rule:

  1. 1.

Pick a pre-existing node x from the network uniformly at random.

  2. 2.

With probability $1-r$, the new node n attaches to ${\tt x}$.

  3. 3.

With probability $r$, n attaches to _any_ neighbor of ${\tt x}$, chosen
uniformly at random.

Repeat these steps a until a network of a desired size is generated. The
growth rules for directed and undirected redirection are illustrated in Fig.
6.

Figure 6: Comparison of redirection for (a) directed and (b) undirected
networks. (a) The new node (blue) attaches by redirection to the unique
ancestor (black) of the target (red). (b) With the same target in an
undirected network, the new node attaches to any one of the red neighboring
nodes.

Figure 7: Examples of tree networks of $10^{4}$ nodes that are grown by
complete redirection. Green: nodes of degree $k=1$ (leaves); yellow,
$2\\!\leq\\!k\\!\leq\\!10$; cyan, $11\\!\leq\\!k\\!\leq\\!99$; blue
$100\\!\leq\\!k\\!\leq\\!500$; violet $\to$ red, $k\\!>\\!501$. The node
radius also indicates its degree.

We focus on the limit of $r=1$, which we term as complete redirection, both
for simplicity and because this limiting case leads to the most striking
phenomenology, as illustrated in Fig. 7. The network realizations in this
figure are highly modular and each consists of a number of well-resolved
modules. Each module contains a central macrohub whose degree is a finite
fraction of the total number of nodes $N$; thus each macrohub is connected to
a large number of leaves (nodes of degree 1). Typical networks consist almost
entirely of leaves as $N\to\infty$; that is, the number of leaves satisfies
$N_{1}/N\to 1$ as $N\to\infty$. Nodes with degrees $k\geq 2$ constitute what
we term the network “core”. This core comprises an infinitesimal fraction of
the network, as the number of core nodes $\mathcal{C}=\sum_{k\geq 2}N_{k}$
grows as $N^{\nu-1}$, with $\nu\approx 1.567$, as determined by numerical
simulations Krapivsky and Redner (2017).

A natural question raised by Fig. 7 is: why does this redirection mechanism
lead to such singular networks? Naively, the rate at which a new node attaches
to a given pre-existing node $\mathbf{n}$ is proportional to the number of its
neighbors, that is, proportional to its degree. However, when a new node
selects a neighbor $\mathbf{x}$ of node $\mathbf{n}$, redirection could lead
to attachment to another neighbor of $\mathbf{x}$ and not to $\mathbf{n}$. On
the other hand, if the degree of $\mathbf{n}$ is large, then typically its
neighbors $\mathbf{x}$ are mostly leaves (Fig. 7). This observation suggests
that the attachment rate could be more singular than linear preferential
attachment.

The degree distribution for complete redirection has an algebraic tail
$N_{k}\propto k^{-\nu}$ with $\nu\approx 1.567$. As discussed in the
introduction, a degree distribution with $\nu<2$ cannot occur in sparse
networks, which exhibit standard extensive $N_{k}\propto N$ scaling. However,
a degree distribution with such a fat tail can arise if the amplitude grows
sub-extensively with network size, that is, $N_{k}\sim N^{\nu-1}/k^{\nu}$.
Thus the number of nodes of _any_ fixed degree $k$ with $k\geq 2$ grows
sublinearly in $N$, with $N_{k}\sim N^{\nu-1}$.

Several features of networks grown by complete redirection can be understood
analytically Krapivsky and Redner (2017), while others, such as the exponent
$\nu$ are currently beyond the reach of available techniques. The difficulty
in making theoretical progress is that the change in the degree of a specific
node depends on the degrees of all its neighbors. This inherent non-locality
in the growth rule means that it is not possible to write a master equation
for the degree distribution alone. Instead, the equation for the degree
distribution must involve degree correlation functions between neighboring
nodes, and this quantity, in turn, involves higher-order correlation
functions.

##  V Concluding Remarks

Preferential attachment networks have been the focus of intense investigation
for the past two decades. Part of the reason for this explosion of interest
stemmed from the confluence of theoretical insights that were inspired by the
existence of new datasets about networked systems. The network paradigm is
alluring and a large number of seemingly unrelated many-body systems are now
studied within the context of complex networks.

While the field has advanced significantly, some basic facts about the
simplest network models seem underappreciated. One is that the degree
distribution of linear preferential attachment networks sensitively depends on
microscopic details of the network growth mechanism. While the earliest
theoretical studies of linear preferential attachment networks found a degree
distribution exponent of $\nu=3$, _any_ exponent value with $\nu>2$ can be
achieved by linear preferential attachment. This nonuniversality is surprising
because the standard lore from statistical physics suggests that exponent
values should be universal and independent of the details of the network
growth process.

Another important facet of complex networks that has yet to be fully exploited
is that they can be generated by simple redirection algorithms. When a new
node joins the network, it either attaches with a given probability to a pre-
existing node that is chosen uniformly at random, or it attaches to the
ancestor this target node with the complementary probability. This algorithm
is simple to implement and efficient because it generates networks of $N$
nodes in an algorithmic time that is also of the order of $N$. We showed how
to generate networks that are equivalent to sublinear preferential attachment
and to shifted linear preferential attachment by suitable redirection rules.
Our redirection perspective provides crucial insights that relate the random
recursive tree to preferential attachment networks.

We also briefly discussed undirected networks that are grown by complete
redirection. The resulting networks are highly modular in structure: the
number of core (nodes of degree $\geq 2$) scales sublinearly with the total
number of nodes, as $N^{\nu-1}$, with $\nu\approx 1.567$. The master equation
approach, which works so well for directed networks, is inadequate to describe
the structure this class of networks. This inadequacy stems from the effective
non-locality in the growth mechanism, and different approaches seem to be
needed to truly understand the behavior of this network. An even deeper reason
is the lack of self averaging: the random quantities $N_{k}$ for any $k>1$
exhibit huge fluctuations from realization to realization. Therefore averages
$\langle N_{k}\rangle$ incompletely characterize each $N_{k}$, and, by
construction, the master equation approach only gives average quantities.

This research was partially supported by various NSF awards over the past two
decades, and most recently by NSF grant DMR-1910736.

## References

  * Jackson and Rogers (2007) M. O. Jackson and B. W. Rogers, “Meeting strangers and friends of friends: How random are social networks?” Amer. Econ. Rev. 97, 890–915 (2007).
  * Traud  _et al._ (2012) A. L. Traud, P. J. Mucha, and M. A. Porter, “Social structure of facebook networks,” Physica A 391, 4165–4180 (2012).
  * Otter (1948) R. Otter, “The number of trees,” Ann. Math. 49, 583–599 (1948).
  * Kleinberg  _et al._ (1999) J. M. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins, “The web as a graph: Measurements, models and methods,” in  _Computing and Combinatorics. COCOON 1999. Lecture Notes in Computer Science_, Vol. 1627, edited by T. Asano, H. Imai, D. T. Lee, S. Nakano, and T. Tokuyama (Springer, Berlin, 1999) pp. 1–18.
  * Krapivsky and Redner (2001) P. L. Krapivsky and S. Redner, “Organization of growing random networks,” Phys. Rev. E 63, 066123 (2001).
  * Yule (1925) G. U. Yule, “A mathematical theory of evolution,” Phil. Trans. Roy. Soc. Series B 213, 21–87 (1925).
  * Simon (1955) H. A. Simon, Biometrika 42, 425–440 (1955).
  * Barabási and Albert (1999) A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science 286, 509–512 (1999).
  * Krapivsky  _et al._ (2000) P. L. Krapivsky, S. Redner, and F. Leyvraz, “Connectivity of growing random networks,” Phys. Rev. Lett. 85, 4629–4632 (2000).
  * Dorogovtsev  _et al._ (2000) S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, “Structure of growing networks with preferential linking,” Phys. Rev. Lett. 85, 4633–4636 (2000).
  * Dorogovtsev and Mendes (2002) S. N. Dorogovtsev and J. F. F. Mendes, “Evolution of networks,” Adv. Phys. 51, 1079–1187 (2002).
  * Newman (2010) M. Newman,  _Networks: An Introduction_ (Oxford University Press, New York, USA, 2010).
  * Kunegis  _et al._ (2013) J. Kunegis, M. Blattner, and C. Moser, “Preferential attachment in online networks: Measurement and explanations,” in  _WebSci ’13: Proceedings of the 5th Annual ACM Web Science Conference_ (ACM, New York, NY, 2013).
  * Lambiotte  _et al._ (2016) R. Lambiotte, P. L. Krapivsky, U. Bhat, and S. Redner, “Structural transitions in densifying networks,” Phys. Rev. Lett. 117, 218301 (2016).
  * Bhat  _et al._ (2016) U. Bhat, P. L. Krapivsky, R. Lambiotte, and S. Redner, “Densification and structural transitions in networks that grow by node copying,” Phys. Rev. E 94, 062302 (2016).
  * Krapivsky and Redner (2002) P. L. Krapivsky and S. Redner, “Finiteness and fluctuations in growing networks,” J. Phys. A 35, 9517–9534 (2002).
  * Krapivsky  _et al._ (2010) P. L. Krapivsky, S. Redner, and E. Ben-Naim,  _A Kinetic View of Statistical Physics_ (Cambridge University Press, Cambridge, UK, 2010).
  * Graham  _et al._ (1994) R. L. Graham, D. E. Knuth, and O. Patashnik,  _Concrete Mathematics: A Foundation for Computer Science_ (Addison-Wesley, Reading, Massachusetts, 1994).
  * Hodas and Kooti (2013) N. Hodas and K. Kooti, F.and Lerman, “Friendship paradox redux: Your friends are more interesting than you,” in  _Proceedings of the International AAAI Conference on Web and Social Media_, Vol. 7 (2013) pp. 225–233.
  * Eom and Jo (2014) Young-Ho Eom and Hang-Hyun Jo, “Generalized friendship paradox in complex networks: The case of scientific collaboration,” Scientific reports 4, 1–6 (2014).
  * Ben-Naim and Krapivsky (2010) E. Ben-Naim and P. L. Krapivsky, “Random ancestor trees,” J. Stat. Mech. 2010, P06004 (2010).
  * Krapivsky and Redner (2005) P. L. Krapivsky and S. Redner, “Network growth by copying,” Phys. Rev. E 71, 036118 (2005).
  * Krapivsky (2023) P. L. Krapivsky, “Random recursive hypergraphs,” J. Phys. A 56, 195001 (2023).
  * Gabel and Redner (2013) A. Gabel and S. Redner, “Sublinear but never superlinear preferential attachment by local network growth,” J. Stat. Mech. 2013, P02043 (2013).
  * Gabel  _et al._ (2014) A Gabel, P. L. Krapivsky, and S. Redner, “Highly dispersed networks generated by enhanced redirection,” J. Stat. Mech. 2014, P04009 (2014).
  * Diestel (2017) R. Diestel,  _Graph Theory_ (Springer, Heidelberg, 2017).
  * Drmota (2009) M. Drmota,  _Random Trees_ (Springer, Vienna, 2009).
  * Frieze and Karoński (2016) A. Frieze and M. Karoński,  _Introduction to Random Graphs_ (Cambridge University Press, Cambridge, UK, 2016).
  * Krapivsky and Redner (2017) P. L. Krapivsky and S. Redner, “Emergent network modularity,” J. Stat. Mech. 2017, 073405 (2017).
  * Levens  _et al._ (2022) W. Levens, A. Szorkovszky, and D. J. T. Sumpter, “Friend of a friend models of network growth,” R. Soc. Open Sci. 9, 221200 (2022).