# Identifying time dependence in network growth

Max Falkenberg1,2<EMAIL_ADDRESS>Jong-Hyeok Lee3 Shun-ichi
Amano3 Ken-ichiro Ogawa3 Kazuo Yano4 Yoshihiro Miyake3 Tim S. Evans1,2 Kim
Christensen1,2 1Blackett Laboratory, Imperial College London, London SW7 2AZ,
United Kingdom  2Centre for Complexity Science, Imperial College London,
London SW7 2AZ, United Kingdom  3Department of Computer Science, Tokyo
Institute of Technology, Yokohama, Kanagawa, Japan  4Center Research
Laboratory, Hitachi Ltd., Kokubunji, Tokyo, Japan

###### Abstract

Identifying power-law scaling in real networks - indicative of preferential
attachment - has proved controversial. Critics argue that measuring the
temporal evolution of a network directly is better than measuring the degree
distribution when looking for preferential attachment. However, many of the
established methods do not account for any potential time-dependence in the
attachment kernels of growing networks, or methods assume that node degree is
the key observable determining network evolution. In this paper, we argue that
these assumptions may lead to misleading conclusions about the evolution of
growing networks. We illustrate this by introducing a simple adaptation of the
Barabási-Albert model, the “k2 model”, where new nodes attach to nodes in the
existing network in proportion to the number of nodes one or two steps from
the target node. The k2 model results in time dependent degree distributions
and attachment kernels, despite initially appearing to grow as linear
preferential attachment, and without the need to include explicit time
dependence in key network parameters (such as the average out-degree). We show
that similar effects are seen in several real world networks where constant
network growth rules do not describe their evolution. This implies that
measurements of specific degree distributions in real networks are also likely
to change over time.

###### pacs:

Valid PACS appear here

††preprint: APS/123-QED

##  I Introduction

The study of complex networks has expanded rapidly over the past 20 years.
Many real systems have been analyzed using networks with great success,
showing many non-trivial properties Vasiliauskaite and Rosas (2020). Model
networks have been defined to understand the origin and development of these
properties from elementary principles. For instance, the Watts-Strogatz model
generates networks with short average path lengths but high clustering
coefficients, explaining the small world phenomenon Watts and Strogatz (1998).
Similarly, the Barabási-Albert (BA) model, an undirected version of the Price
model Price (1976), demonstrates that scale free (power-law) degree
distributions in real networks can arise from a combination of growth and
preferential attachment Barabási and Albert (1999). These models have given
significant insight into the structure of real networks. However, real systems
almost never reflect the exact details of a model.

One of the most common features to study in a real network is the degree
distribution Broido and Clauset (2019). The degree, $k$, of a node in a
network is the number of direct connections a node has to other nodes in the
network. The degree distribution, $P(k)$, is the probability distribution of
the degree across all the nodes in the network. The degree distribution is
said to be scale free (the exact definition is argued over) if it displays
power-law scaling such that $P(k)\propto k^{-\kappa}$, where $\kappa$ is a
positive constant, often found to be in the range $\kappa\in\\{2,3\\}$ for
real networks Newman (2005). Plotting $P(k)$ vs. $k$ on a log-log scale, a
power-law distribution appears as a straight line with gradient $-\kappa$.

Since the late 1990s, many real networks have been reported as having scale
free, or nearly scale free degree distributions. This includes web-page links
on the internet Albert  _et al._ (1999), citation networks Redner (1998), the
co-occurrence of words in language i Cancho and Solé (2001), sexual contact
Liljeros  _et al._ (2001), social networks Java  _et al._ (2007), and others.
Identifying these networks as scale free has important consequences: (1) it
gives a potential mechanistic understanding of the origin and development of
these networks, notably that the network evolves according to preferential
attachment, and (2) it suggests these networks have a set of important
properties associated with scale free networks. These properties include the
presence of hub nodes which have degree much larger than the network average,
very small network diameters Cohen and Havlin (2003), and resistance to errors
but vulnerability to targeted attack Crucitti  _et al._ (2003).

Although the scale free paradigm has become a hallmark of complex networks
research, identifying scale free behavior in real networks is still very
controversial Holme (2019).

Significant effort has gone towards developing appropriate statistical
techniques to assess whether networks at a fixed point in time are scale free,
most notably in Clauset  _et al._ (2009); Broido and Clauset (2019). Given the
difficulty in distinguishing a power-law distribution, $P(k)\propto
k^{-\kappa}$, from similar distributions such as the log-normal, $P(k)\propto
k^{-1}\text{exp}[-\frac{(\text{ln}k-\mu)^{2}}{2\sigma^{2}}]$, or stretched
exponential, $P(k)\propto k^{\tau-1}\text{e}^{-\lambda k^{\tau}}$, these
statistical techniques are clearly important for understanding the statistical
properties of network degree distributions. Applying such techniques to a
large set of real world networks, a recent study found that true scale free
networks are rare, representing only about 4% of all networks Broido and
Clauset (2019). These results are broadly in line with a number of similar
criticisms of the scale free paradigm Radicchi  _et al._ (2008); Lima-Mendez
and van Helden (2009); Willinger  _et al._ (2009); Golosovsky (2017); Stumpf
and Porter (2012); Sendiña-Nadal  _et al._ (2016); Kang (2020). However,
despite broad support for these criticisms, many others in the networks
community are still strong believers that most complex networks exhibit
preferential attachment Goh  _et al._ (2002); House  _et al._ (2015); Barabási
_et al._ (2016); Voitalov  _et al._ (2019). Among these individuals, many have
taken issue with the methods to process the data in Broido and Clauset (2019)
and/or the strictness of the scale free definition Barabási  _et al._ (2016);
Holme (2019); Voitalov  _et al._ (2019); Gerlach and Altmann (2019). Arguing
that scale free networks are only well defined in the infinite system size
limit, looser definitions suggest that scale free networks are in fact not
rare at all Voitalov  _et al._ (2019). However, it can be argued that such a
loosening will naturally result in a larger number of positive
identifications, and that using weakened criteria for scale freeness defeats
the aim of using a statistically rigorous approach. Clearly, the issue of
which approach is best when analyzing network degree distributions is yet to
be fully resolved.

There is a third camp who argue that “knowledge of whether or not a
distribution is heavy-tailed is far more important than whether it can be fit
using a power-law” Stumpf and Porter (2012). However, great care must be take
with such an approach in a context dependent manner. For instance, in the case
of epidemic spreading, two networks may both be fat-tailed with similar
degree-distributions, yet exhibit very different epidemic mixing patterns due
to differences in network assortativity Kiss  _et al._ (2008); Piraveenan  _et
al._ (2012).

What all these approaches have in common is that they analyze the degree
distribution of a network at a fixed point in time. If such an analysis is to
give insight into the mechanistic origin and evolution of a network, it would
be prudent to ask whether the degree distribution is representative of the
network in general during its evolution, or only for a brief period of time?
Without an answer to this question, inferring the past and future evolution of
a network based on the current form of its degree distribution may give
misleading results.

A prominent example of a theoretical network model where the observed degree
distribution appears to change over time is super-linear preferential
attachment, where new nodes attach to existing nodes proportionally to their
degree to a power greater than 1 Krapivsky  _et al._ (2000). In the long time
limit, a gelation phenomenon is observed where almost all nodes connect to a
single hub node forming a star-like network. However, Krapivsky and Krioukov
Krapivsky and Krioukov (2008) showed that super-linear attachment has
significant pre-asymptotic regimes where the degree distribution appears to be
approximately scale free.

Given the difficulty of directly identifying preferential attachment from
static degree distributions, proponents of the scale free paradigm have argued
that preferential attachment can be identified directly from dynamical network
data (if available) Barabási  _et al._ (2016). Numerous approaches have been
introduced over the years, using a variety of different assumptions Newman
(2001); Jeong  _et al._ (2003); Massen and Doye (2007); Gómez  _et al._
(2011); Sheridan  _et al._ (2012); Kunegis  _et al._ (2013); Pham  _et al._
(2015). Most commonly, methods assume that the preferential attachment kernel
follows a functional form, $\Pi(k)\propto k^{\gamma}$, and primarily focus on
estimating the exponent $\gamma$ \- such methods will naturally assume that
the preferential attachment kernel of a network is time independent.

As an alternative approach, non-parametric methods have been proposed that do
not assume a functional form. The first of these methods by Jeong  _et al._
Jeong  _et al._ (2003) infers the form of the attachment kernel by
constructing a histogram of the degree of nodes to which new edges attach over
a short observation window. However, there is no clear guide as to how to
choose the start of the observation window and how long it must be - too short
and the result is very noisy, too long and the result is subject to bias Pham
_et al._ (2015). The method by Newman Newman (2001) avoids this problem by
constructing multiple histograms over different observation windows and
computes the attachment kernel by taking a weighted average over the different
histograms. Although this method avoids the issue of how to choose your
observation window, this approach seems to underestimate the attachment kernel
at large degrees Herdağdelen  _et al._ (2007), an issue since corrected by
Pham  _et al._ Pham  _et al._ (2015).

For networks in which the attachment kernel is time independent, the corrected
Newman method proposed in Pham  _et al._ (2015) gives an excellent fit to
data. However, it is still not clearly established whether the assumption of
time independence is valid for real networks, and in some cases (such as
citation networks) it is known to be false Leskovec  _et al._ (2005).
Similarly, the probability of attaching to a node may be a function of a
variable other than the degree. However, how to correctly identify which
feature of a node determines its attractiveness is not clear.

It is often argued that accurately calculating the attachment kernel of a
growing network is important because it can help to predict the future
evolution of a network Kunegis  _et al._ (2013). For instance, in the case of
non-linear preferential attachment, where the attachment kernel is given by
$\Pi(k)\propto k^{\gamma}$ with positive constant $\gamma$, it is known that
for $0<\gamma<1$, the limiting degree distribution is a stretched exponential,
whereas for $\gamma>1$, the degree distribution displays a gelation phenomenon
where a single dominant hub connects to almost all other nodes in the network
Krapivsky  _et al._ (2000). In between, $\gamma=1$ corresponds to traditional
linear preferential attachment where the degree distribution displays power-
law scaling. Hence, if we can estimate the value of $\gamma$ for the
attachment kernel of a real network, this can be used to predict its future
evolution.

Predictions regarding the future evolution of networks, explanations of the
historical development of networks, and investigations into whether
preferential attachment underlies the evolution of networks, based on measured
attachment kernels, are widespread in the literature. These include studies on
citation networks Ronda-Pupo and Pham (2018); Sheridan and Onodera (2018),
protein networks Eisenberg and Levanon (2003), the bitcoin network Kondor  _et
al._ (2014), common words in the English language Perc (2012), social dynamics
in online games Szell and Thurner (2010), actor networks Jeong  _et al._
(2003), and more.

The majority of these studies make three assumptions: (1) that the degree of a
node is the key feature determining a node’s attractiveness, (2) that the
attachment kernel can be approximated by $\Pi(k)\propto k^{\gamma}$, and (3)
that the measured attachment kernel is either time independent, or that the
time dependence is largely unimportant. For instance, looking at four
different periods in the evolution of the American Physical Society (APS)
citation network, and using the node degree (citation count) as the key
variable of interest, Sheridan and Onodera found that the exponent $\gamma$
ranges from 0.94 to 1.06 Sheridan and Onodera (2018). The authors assert that
this implies that the attachment probabilities in the APS citation network are
at least approximately time independent. However, as noted, $\gamma<1$ would
imply that the APS citation network’s degree distribution approaches a
stretched exponential, whereas $\gamma>1$ would result in a gelation effect.
Since both $\gamma<1$ and $\gamma>1$ were observed from the data, what does
this imply for the future evolution of the network?

The aim of this paper is to illustrate the risks of assuming time independence
in the rules governing the evolution of growing networks, and the risk of
assuming that the node degree determines node attractiveness. We will do this
by introducing the “k2 model”, a simple variant of the Barabási-Albert model
where new nodes do not attach to existing nodes proportionally to the number
of direct neighbors a node has, but rather proportionally to the number of
nodes within a distance two of the target node. This simple rule is rooted in
the idea that well connected neighbors are preferable to poorly connected
neighbors. The rule puts a particular focus on the role of nearest neighbor
correlations in network growth. Such mechanisms of mutual benefit may be
relevant to collaboration Li  _et al._ (2019), or citation Vazquez (2000)
networks. The mechanism may also have indirect relevance to node copying
processes Lambiotte  _et al._ (2016); Bhat  _et al._ (2016); Krapivsky and
Redner (2005). Similar ideas have been explored in Dangalchev (2004); Wang
_et al._ (2018); Topirceanu  _et al._ (2018); Amano  _et al._ (2018).

Although this simple rule has no explicit time dependence (i.e. time
dependence is not in built by including a time dependent parameter, e.g., the
average out-degree), the correlations that form between neighboring nodes
result in an implicit time dependence in the attachment kernel. Consequently,
the resulting network does not demonstrate any of the simple scaling observed
in traditional network models. This is despite an extended initial transient
phase during which the network appears to grow according to linear
preferential attachment. We support this argument with an analytical treatment
demonstrating that assumptions of simple scaling in the k2 model are not
robust.

The arguments we illustrate with the k2 model are highly relevant to real
networks. By calculating the ratio of network attachment kernels over
different time periods, we show that over short timescales, assumptions of
time independence for real networks are relatively well justified. However,
over longer time periods, the relative attachment kernels calculated show
clear time dependence, displaying a diversity of patterns. While the overall
effect may be small in some cases (such as for the Flickr friendship network
or the English Wikipedia hyperlink network Mislove (2009)), we argue that, at
a minimum, practitioners should test the degree of time dependence in their
data before making predictions about the future or past development of a
network.

##  II Methods

###  IIa Model Definition

The k2 model is defined as a simple, undirected network. The model is
initialized with a small connected network of $m_{0}$ nodes. Each time-step, a
new node is created with $m\leq m_{0}$ new edges. The $m$ edges are connected
to the new node and target nodes from the network. Each target node is chosen
with probability proportional to the number of neighbors which are one or two
steps away, $k_{i}^{(2)}$, from the target node, $i$. We refer to
$k_{i}^{(2)}$ as the second degree of node $i$, see Appendix A for a formal
definition. The attachment probability is identical to the BA model with the
exception that the BA model attaches proportionally to the number of nodes one
step away, $k_{i}^{(1)}$, from the target node, $i$. We refer to $k_{i}^{(1)}$
as the first degree, or just the degree, of node $i$. Computationally, we
prevent multiple edges being formed between two nodes by selecting $m$ unique
target nodes.

For clarity, whenever notation is presented with a subscript $i$ or $j$, for
instance $k_{i}^{(1)}$ or $k_{j}^{(2)}$, the focus is on the value of that
variable for the particular node $i$ or $j$. When the subscript is omitted,
for instance $k^{(1)}$ or $k^{(2)}$, the focus is on all nodes with the same
specific value of the variable in question. We use $k$ and $k^{(1)}$
interchangeably where appropriate.

Figure 1: A sketch of a simple tree network with four labeled nodes. The
values in the brackets correspond to the first and second degree,
$(k_{i}^{(1)},k_{i}^{(2)})$, of each node. The four labeled nodes have the
same degree, $k_{i}^{(1)}=3$, implying equal importance in the BA model, but
different second degrees, implying unequal importance in the k2 model. Figure
2: An illustration of how the k2 model can be thought of as generating two
distinct networks. (a) The observed network is the network of nodes which have
a direct connection to each other. In this network, the degree does not
account for the importance of next-nearest neighbors. (b) The influence
network where two nodes are connected if they are nearest or next-nearest
neighbors in the observed network.

Figure 1 illustrates the motivation for the k2 model. In the BA model, a
node’s importance is proportional to the number of nodes connected to it, i.e.
the first degree. However, there is no consideration for whether these
connected nodes are important or not. A node with three isolated neighbors is
considered equally important to a node neighboring three hubs. This is in
conflict with many real world scenarios, for instance in academic
collaboration networks, where it is known that junior researchers working
under top scientists are those most likely to be successful and reach tenure
in their careers Li  _et al._ (2019). In the k2 model, this effect is
accounted for, allowing nodes to benefit from connecting to hub nodes and
giving them the opportunity to become hubs themselves.

The principle of weighting neighbor importance reflects the role of friends-
of-friends in social network theory Granovetter (1977); Burt (1992), and is
the foundation for widely used network centrality measures built on self-
consistent equations, such as Katz centrality Katz (1953); Newman (2018) or
PageRank Brin and Page (1998); Newman (2018).

Mathematically, we define the attachment kernel, $\Pi$, as the function
specifying the probability of attaching to a specific node in the network. In
the BA model, $\Pi^{(BA)}\propto k^{(1)}$, whereas in the k2 model,
$\Pi^{(k2)}\propto k^{(2)}$. In the case of the k2 model, we can write the
normalized form of the attachment kernel as

$\Pi^{(k2)}_{i}=\frac{k^{(2)}_{i}}{\sum_{j=1}^{N}k_{j}^{(2)}}\approx\frac{k^{(2)}_{i}}{\sum_{j=1}^{N}(k_{j}^{(1)})^{2}},$
(1)

where for $m=1$, the approximation is an equality. For $m>1$ the approximation
holds as long as the number of non-unique second degree neighbors is small,
see Appendix A. By splitting the numerator of the attachment kernel into the
contribution of the first degree neighbors to node $i$, $k_{i}^{(1)}$, and the
contribution of the next-nearest neighbors, $k_{i}^{(2)}-k_{i}^{(1)}$, Eq. (1)
can be rewritten as

$\Pi_{i}^{(k2)}\approx\frac{k_{i}^{(1)}+\sum_{\alpha=1}^{k_{i}^{(1)}}(k_{i\alpha}^{(1)}-1)}{\sum_{j=1}^{N}(k_{j}^{(1)})^{2}},$
(2)

which is a function of the first neighbor degree only, where we have used

$k_{i}^{(2)}=\sum_{\alpha=1}^{k_{i}^{(1)}}k_{i\alpha}^{(1)}.$ (3)

Here, $\alpha$ labels the $k_{i}^{(1)}$ unique first neighbors of node $i$,
and $k_{i\alpha}^{(1)}$ is the first degree of node $\alpha$, connected to
node $i$. In Eq. (2), the first term indicates the contribution to the
attachment kernel from the direct neighbors of node $i$, and the second term
indicates the contribution from next-nearest neighbors to node $i$.

Conceptually, we can think of the k2 model as involving two separate networks.
In the observed network, each node represents an agent, and an edge between
two nodes represents a direct, first degree relationship between the two
nodes. However, new nodes do not connect to a target node according to the
node’s direct connections, but rather according to the number of nodes within
distance two of the target. These nodes are within the sphere of influence of
the target node. Hence, we define the influence network, in which an edge
between any two nodes signifies that the nodes are within each other’s sphere
of influence, i.e., two connected nodes are neighbors, or next-nearest
neighbors in the observed network, see Fig. 2.

The influence network has similarities to the node copying mechanism studied
in Lambiotte  _et al._ (2016); Bhat  _et al._ (2016), based on earlier models
in Krapivsky and Redner (2005), with relevance to social network formation
Granovetter (1977); Toivonen  _et al._ (2009), citation networks Goldberg  _et
al._ (2015); Vazquez (2000), evolution Ohno (2013), and protein interaction
networks Ispolatov  _et al._ (2005); Kim  _et al._ (2002). Although the k2
model is not designed to model such systems explicitly, it may be useful for
understanding the role of neighbor-neighbor correlations in the growth of such
networks.

In the influence network, new nodes connect to a target node proportionally to
the node’s degree, $k^{(2)}$. The new node then copies a fraction of the nodes
attached to the initial target node, and forms additional edges to these
copied neighbors. The copied neighbors correspond to those which are directly
connected to the target node in the observed network. In the node copying
model, new nodes select a target node at random and then copy a fraction of
the target node’s neighbors. As opposed to the k2 model, the copied neighbors
are selected at random with probability $p$. In this respect, the node copying
model where the original target node is chosen preferentially could represent
a mean-field version of the k2 model, where we neglect correlations between
neighboring nodes.

###  IIb Measuring Time Dependence of Preferential Attachment

To understand how the attachment kernel of a network changes over time, it is
helpful to consider relative attachment probabilities as opposed to absolute
attachment probabilities. In general we can write an arbitrary attachment
kernel, which is a function of the node degree only, as

$\Pi(k;t)=\frac{f(k)}{\sum_{j=1}^{N(t)}f(k_{j}(t))}$ (4)

with an arbitrary preference function $f$. The summation is over all nodes in
the network at time $t$. The function $f$ is time independent, however, as the
network grows and more nodes are added, $N(t)$ in the denominator changes, and
hence, the denominator is time dependent. Note, $f(k_{i}(t))$ for a specific
node $i$ is time dependent, since the degree of a specific node evolves over
time. We define the relative attachment kernel as

$\phi_{t}(k,k^{\prime})=\frac{\Pi(k;t)}{\Pi(k^{\prime};t)}=\frac{f(k)}{f(k^{\prime})}.$
(5)

As opposed to $\Pi(k;t)$, the relative attachment kernel has no dependence on
the network as a whole, but rather, is a function of the degree $k$ and
$k^{\prime}$ only. As a result, we can express the time independence of the
attachment kernel as

$\frac{\mathrm{d}\phi_{t}(k,k^{\prime})}{\mathrm{d}t}=0.$ (6)

For convenience, in the following we will consider $\phi_{t}(k,1)$, i.e., the
attachment probability of connecting to a node with degree $k$ relative to a
node with degree $k^{\prime}=1$. By definition, $\phi_{t}(k,k)=1$.

Consider the relative attachment kernel calculated at time $t$, written as
$\phi_{t}(k,1)$, and at time $s$, $\phi_{s}(k,1)$. If Eq. (6) holds, then
$\phi_{t}(k,1)=\phi_{s}(k,1)$. For a real network, it is likely that there
will be small deviations from this ideal case. Hence, we can plot the ratio
$\phi_{t}(k,1)/\phi_{s}(k,1)$ against degree $k$ to gauge the extent of the
time dependence across a specific time interval. This ratio is only well
defined for networks which contain nodes with degree $k$ at both times $t$ and
$s$.

The BA model is a simple case where Eq. (6) should hold, with
$\phi_{t}(k,1)=k$ for all $t$. Likewise, for non-linear preferential
attachment, $\phi_{t}(k,1)\propto k^{\gamma}$ with positive constant $\gamma$.
In the case of the k2 model, Eq. (6) does not hold, due to the second term in
Eq. (2). The preference function in the k2 model is not a function of the
degree of a node, but the second degree, $k^{(2)}$. Clearly the second degree
is related to the first degree, and, when analyzing the k2 model, one could
mistakenly believe that the node degree, $k^{(1)}$ is the quantity determining
network growth. However, although this appears approximately true at first,
over time, the relation between the first and second degree changes,
$\left\langle k^{(2)}(t)\right\rangle\not\propto\left\langle
k^{(1)}(t)\right\rangle$. In other words, although the attachment kernel is
not explicitly time dependent (e.g., we have not included an explicit aging
mechanism), the local network structure, which determines a node’s second
degree, is time dependent.

This point cannot be overstated; while the k2 model clearly breaks the
assumptions outlined above, it does so in a way that, without prior knowledge
of the model rules, is wholly non-obvious. As we will outline, if sufficient
care is not taken, these assumptions risk misleading or incorrect predictions
about a networks past or future evolution.

##  III Results

###  IIIa Simulation Results

(a)

(b)

Figure 3: The (a) degree distribution and (b) relative attachment kernel for
the k2 model with $m=1$. The dashed lines show the expected scaling for the BA
model. Early in the growth of the k2 model, the evolution of the network is
largely indistinguishable from the BA model. As the network grows, both the
degree distribution and relative attachment kernel deviate significantly from
the simple BA model scaling.

(a)  (b)

(c)  (d)

Figure 4: An illustration that the relative attachment kernel in the k2 model
is time dependent. (a) The relative attachment kernel, $\phi_{t}(k,1)$, for
the k2 model with $m=1$ as calculated using the corrected Newman method. (b)
The ratio of the calculated relative attachment kernels. (c) The cumulative
sum and (d) corresponding ratio of the relative attachment kernels shown in
(a). The dashed lines indicate the prediction for the BA model in (a) and (c),
and the ratio expected for any time independent relative attachment kernel,
which is a function of node degree only, in (b) and (d).

(a)  (b)

(c)  (d)

Figure 5: An illustration that the relative attachment kernel in the BA model
is time independent. (a) The relative attachment kernel, $\phi_{t}(k,1)$, for
the BA model with $m=1$ as calculated using the corrected Newman method. (b)
The ratio of the calculated relative attachment kernels. (c) The cumulative
sum and (d) corresponding ratio of the relative attachment kernels shown in
(a). The dashed lines indicate the prediction for the BA model in (a) and (c),
and the ratio expected for any time independent relative attachment kernel,
which is a function of node degree only, in (b) and (d). Finite-size effects
result in small deviations from the expected scaling at large $k>100$, where
the data is noisy.

In the following, we will focus on analyzing the attachment kernel and the
degree distribution of the k2 model, using the BA model as a comparison. Each
simulation is initialized with a complete graph of $m_{0}=m+1$ nodes.

Figure 3 shows the degree distribution and the true relative attachment kernel
for the k2 model with $m=1$. Both sub-figures are averaged over 100
simulations. Early in the network development, there are only small
differences between the behavior of the k2 and BA models. However, as the
network grows, significant differences emerge. The duration of the initial BA-
like transient phase is longer and follows the BA model even more closely for
$m>1$, see Appendix B.

Over short timescales, the network growth appears largely indistinguishable
from linear preferential attachment. However, over longer timescales, the
attachment kernel shows clear deviations from this simple scaling, with a
plateau region at moderate degree preceding a super-linear tail. The anomalous
scaling observed is most clearly seen for nodes with moderate degree in the
range $k\approx 10$ to $k\approx 300$. This region suggests that there may be
multiple timescales of interest at play in the evolution of the k2 model.

As noted, the BA model incorporates a rich-get-richer mechanism, but does not
account for any mechanisms of mutual benefit between nodes; new nodes added to
the network receive no benefit from attaching to a hub node as opposed to any
other less important node. Conversely, in the k2 model, when a node $i$, added
to the network at time $t_{i}$, attaches to a hub node, the new node’s initial
attractiveness is given by

$\Pi_{i}(k_{i};t_{i})\propto
k_{i}^{(2)}(t_{i})=1+k_{\mathrm{hub}}^{(1)}(t_{i})\approx
k_{hub}^{(1)}(t_{i}),$ (7)

which is completely determined by the first degree of the targeted hub. This
has the counter-intuitive effect that the tail of the attachment kernel
appears to show super-linear preferential attachment, implying gelation, but
that the change in the number of new edges in the influence network is
dominated by new nodes with degree $k^{(1)}=1$. As a consequence, the k2 model
appears to show a gelation-like phenomenon to communities rather than hubs,
resulting in the plateaus shown in Fig. 3.

The true relative attachment kernel in Fig. 3 is typically not accessible for
a real network. To illustrate the risks this may pose, let us assume the k2
model is a real network and fit the relative attachment kernel, on the
assumption that $\phi_{t}(k,1)\propto k^{\gamma}$ for a positive exponent
$\gamma$. From Fig. 3(b) we may deduce that for $t=10^{3}$, the k2 model has
an approximately linear (or possibly slightly sub-linear) attachment kernel,
whereas at $t=10^{6}$, the attachment kernel is highly non-linear, but clearly
grows faster with $k$ than the simple prediction from linear preferential
attachment. If we were to use these results to infer the future scaling of the
network, the data at $t=10^{3}$ would suggest the network might approach a
stretched exponential degree distribution, whereas from the data for
$t=10^{6}$, we might paradoxically infer the network is approaching a gelation
state. In the case of the k2 model this approach is misleading, but for other
networks this approach may be a good first approximation. However, what is
clear is that simply calculating the attachment kernel of a network at one
point in time is not sufficient to determine the form of the attachment kernel
in the past or future. Likewise, since the degree distribution is determined
by the underlying dynamical process growing the network, we cannot accurately
know how the degree distribution will evolve in the future.

In the case of a real network, we can only estimate the relative attachment
kernel by observing the degree of nodes to which new nodes added to the
network attach. To simulate this real-network scenario, we apply the corrected
Newman method to a single simulation of the k2 model as shown in Fig. 4.
Figure 4(a) shows the calculated relative attachment kernel for the k2 model
at times $t=10^{5}$ and $t=10^{6}$. As in Fig. 3(b), nodes with moderate
degree, $k\approx 30$, show an excess in the relative attachment kernel. In
Fig. 4(b), deviations in the relative attachment kernel are shown explicitly
by taking the ratio to the relative attachment kernels at $t=10^{5}$ and
$t=10^{6}$. For very small degree nodes, the ratio is approximately one
indicating that the attachment kernel is time independent at these degrees.
Above $k=10$, the ratio clearly deviates from one, indicating that the
relative attachment kernel is time dependent. For visual clarity, Fig. 4(c) &
(d) show the equivalent as (a) & (b) but for the cumulative sum of the
relative attachment kernel, defined as

$\tilde{\phi}(k,1)=\sum_{\tilde{k}\leq k}\phi(\tilde{k},1).$ (8)

It is important to note that the estimated attachment kernel using Newman’s
method is not fully consistent with the true attachment kernel; the magnitude
of the excess in the attachment probabilities is much smaller using Newman’s
method than the true excess shown in Fig. 3(b). This is because Newman’s
method constructs the attachment kernel by collating multiple histograms from
different times in the network evolution. The consequence is that the
estimated form of the attachment kernel at $t=10^{6}$ is more consistent with
the true attachment kernel earlier in the evolution of the k2 model, rather
than the current value of the attachment kernel.

To verify that the deviations in the relative attachment kernel are due to the
evolution of the k2 model and not numerical errors, we repeat the analysis
shown in Fig. 4 for the BA model where the relative attachment kernel is
expected to be time independent. Figure 5(a) shows that the relative
attachment kernels are effectively indistinguishable at different times in the
network evolution. This is confirmed by Fig. 5(b) where the ratio of the
relative attachment kernels is approximately one for all nodes with degree
$k<100$. Noise in the tail obscures the ratio for $k>100$.

Overall, Fig. 5 indicates that using the corrected Newman method is effective,
to an extent, at estimating the relative attachment kernel of a network and
testing whether it exhibits time dependence. This suggests that the deviations
in the relative attachment kernel observed in Fig. 4 are due to the structural
properties of the k2 model, and not due to limitations in the method used to
estimate the relative attachment kernel. Hence, we can deduce that the
relative attachment kernel for the k2 model is time dependent.

###  IIIb Mathematical Results

Given the complexity of the k2 model, exact analytical results are hard to
derive. However, using simple arguments, we can demonstrate the
inconsistencies that arise from assuming the k2 model follows a simple form of
non-linear preferential attachment.

From the definition of the k2 model, we can make a continuum approximation and
write the evolution of the degree, $k_{i}^{(1)}(t)$, of a given node $i$ as

$\displaystyle\frac{dk_{i}^{(1)}(\mathrm{t})}{dt}$
$\displaystyle=m\Pi_{i}^{(k2)}(t),$ (9a) $\displaystyle\Pi_{i}^{(k2)}(t)$
$\displaystyle\equiv\frac{k_{i}^{(2)}(t)}{\sum_{j=1}^{N}k_{j}^{(2)}(t)}\approx\frac{k_{i}^{(2)}(t)}{\sum_{j=1}^{N}(k_{j}^{(1)}(t))^{2}},$
(9b)

where node $i$ is added to the network at time $t_{i}(\leq t)$. The second
degree, $k_{i}^{(2)}(t)$, is defined according to Eq. (3), the summation is
over all nodes in the network, and the approximation is an equality if $m=1$,
see Appendix A. We can write the evolution of the second degree as

$\frac{dk_{i}^{(2)}(\mathrm{t})}{dt}\approx
m\frac{\left(k_{i}^{(1)}(t)\right)^{2}+\xi_{i}(t)}{\sum_{j=1}^{N}\left(k_{j}^{(1)}(t)\right)^{2}},$
(10)

where

$\xi_{i}(t)\equiv\sum_{\beta=1}^{k_{i_{1}}^{(1)}(t)-1}k_{i_{1}(\beta)}^{(1)}(t)+\cdots+\sum_{\beta=1}^{k_{i\alpha}^{(1)}(t)-1}k_{i_{\alpha(\beta)}}^{(1)}(t),$
(11)

see Appendix A for a derivation. Here $i_{\alpha(\beta)}$ represents the node
$\beta$ connected to node $i_{\alpha}$. Equation (11) represents the effect of
non-neighboring nodes on node $i$. Since the first degree of a node can only
grow over time, $\xi_{i}(t)$ is a positive semi-definite monotone increasing
function with respect to time $t$, that is,

$\displaystyle\xi_{i}(t)$ $\displaystyle\geq 0,$ (12a)
$\displaystyle\frac{d}{dt}\xi_{i}(t)$ $\displaystyle\geq 0.$ (12b)

Our aim in the following is to write $\xi_{i}(t)$ as a function of the first
degree, $k^{(1)}$, only. To do so we rearrange Eq. (10) to make $\xi_{i}(t)$
the subject and substitute in Eq. (9a) and Eq. (9b),

$\xi_{i}(t)=\frac{1}{m}\left(\sum_{j=1}^{N}\left(k_{j}^{(1)}(t)\right)^{2}\right)\cdot\\\
\frac{d}{dt}\left[\frac{1}{m}\left(\sum_{j=1}^{N}\left(k_{j}^{(1)}(t)\right)^{2}\right)\cdot\frac{dk_{i}^{(1)}(\mathrm{t})}{dt}\right]-\left(k_{i}^{(1)}(t)\right)^{2},$
(13)

which is a function of the first degree only. Here we note that the summations
in Eq. (13) correspond to the denominator in Eq. (9b). This is the sum over
$k_{i}^{(2)}(t)$ for each node in the network, and hence, corresponds to the
twice the total number of edges in the influence network, which we label as

$E^{(2)}(t)=\frac{1}{2}\sum_{j=1}^{N(t)}k^{(2)}_{j}(t)\approx\frac{1}{2}\sum_{j=1}^{N(t)}(k^{(1)}_{j}(t))^{2}.$
(14)

Figure 3 shows the degree distribution and the relative attachment kernel for
the k2 model obtained from simulations. As a thought experiment, let us
suppose that these simulations are not for a theoretical network model but
that the data represents a real world network. For the network at small times
in its evolution, the degree distribution and the attachment kernel are
closely approximated by the BA model.

For preferential attachment (linear or non-linear), it is known that, on
average, the degree of a given node $i$ evolves in time as a power function
given by

$k_{i}^{(1)}(t)=m\left(\frac{t}{t_{i}}\right)^{\delta},\ t\geq t_{i},$ (15)

where $t_{i}$ is the time at which node $i$ was added to the network, and
$\delta=1/2$ for linear preferential attachment Newman (2018). In the case of
sub- (super-) linear preferential attachment, $\delta<1/2$ ($\delta>1/2$). Let
us assume Eq. (15) holds and test whether this simple scaling is consistent
with the mathematical form of the k2 model. First, we substitute Eq. (14) into
Eq. (13),

$\xi_{i}(t)=\frac{4}{m^{2}}E^{(2)}(t)\frac{d}{dt}\left[E^{(2)}(t)\frac{dk^{(1)}_{i}(t)}{dt}\right]-(k^{(1)}_{i}(t))^{2}.$
(16)

In the case of the k2 model where one node is added to the network at each
time step, we initialize our network such that $t_{j}=j$ and note that the
number of nodes in the network at time $t$ is given by $N(t)=m_{0}+t\approx t$
for large $t$.

Using this initialization, we now calculate the value of $E^{(2)}(t)$ by
approximating the sum as an integral and substituting in Eq. (15),

$\displaystyle E^{(2)}(t)$
$\displaystyle\approx\frac{1}{2}\sum_{j=1}^{t}(k^{(1)}_{j}(t))^{2}$ (17)
$\displaystyle\approx\frac{m^{2}}{2}\int_{1}^{t}dt^{\prime}\;\left(\frac{t}{t^{\prime}}\right)^{2\delta}$
$\displaystyle\approx\frac{m^{2}t^{2\delta}}{2(1-2\delta)}\left[(t^{\prime})^{1-2\delta}\right]_{1}^{t}.$

There are three cases for the different possible values of $\delta$: Case (i)
$2\delta<1$. Corresponding to sub-linear preferential attachment, this
scenario is likely to be irrelevant for the k2 model since the influence
network cannot grow slower than the original network in the BA model. In this
case we expect to find linear growth in the number of edges in the influence
network

$E^{(2)}(t)\approx\frac{m^{2}}{2(1-2\delta)}t.$ (18)

Here $E^{(2)}(t)$ is dominated by the youngest nodes (created at the largest
times $t_{i}$) as the older nodes grow too slowly.

Case (ii) $2\delta=1$. Corresponding to linear preferential attachment, this
is the case for the BA model,

$E^{(2)}(t)\approx\frac{m^{2}}{2}\,t\ln(t).$ (19)

Case (iii) $2\delta>1$. Corresponding to super-linear preferential attachment
where there is some enhancement over linear preferential attachment. For the
k2 model, this scenario is plausible since we know that for any given node
$k^{(2)}_{i}(t)\geq k^{(1)}_{i}(t)$. In this case we find

$E^{(2)}(t)\approx\frac{m^{2}}{2(2\delta-1)}(t^{2\delta}-t),$ (20)

where the growth in the number of edges in the influence network is dominated
by the oldest nodes in the network.

Let us assume case (iii) is valid for the k2 model. Substituting Eq. (20) into
Eq. (16) we find,

$\displaystyle\xi_{i}(t)$
$\displaystyle=m^{3}\frac{\delta}{(2\delta-1)^{2}}\left(\frac{1}{t_{i}}\right)^{\delta}\cdot$
(21)
$\displaystyle\;\;\left[(3\delta-1)t^{5\delta-2}-(4\delta-1)t^{3\delta-1}+\delta
t^{\delta}\right]-m^{2}\left(\frac{t}{t_{i}}\right)^{2\delta}$
$\displaystyle=a_{1}t^{5\delta-2}+a_{2}t^{\delta}-a_{3}t^{3\delta-1}-a_{4}t^{2\delta},$

where in the final line we have grouped all the constants for each term into a
single positive prefactor, $a_{1}$ to $a_{4}$.

Recall that the k2 model requires that $\xi_{i}(t)$ is a positive, semi-
defined monotonically increasing function, and note that Eq. (21) is only
valid for $\delta>1/2$. As $t\rightarrow\infty$, the first term of Eq. (21)
will dominate the second if $5\delta-2\geq\delta$, $\delta\geq 1/2$. Likewise,
the third term will dominate the fourth if $3\delta-1\geq 2\delta$,
$\delta\geq 1$. Hence, as $t\rightarrow\infty$, the first term is the dominant
positive term and the fourth term is the dominant negative term. To ensure
$\xi_{i}(t)\geq 0$ for all $t>t_{i}$, this requires the first term to grow
faster than the fourth term giving $5\delta-2\geq 2\delta$, corresponding to
$\delta\geq 2/3$.

Returning to Eq. (10) and substituting in Eq. (15) and Eq. (20), we can also
write

$\frac{dk_{i}^{(2)}(\mathrm{t})}{dt}=m(2\delta-1)\frac{m^{2}\left(t/t_{i}\right)^{2\delta}+\xi_{i}(t)}{m^{2}(t^{2\delta}-t)}.$
(22)

We have established that to satisfy Eq. (12a), the leading term of
$\xi_{i}(t)$ must scale as $t^{5\delta-2}$, and $\delta\geq 2/3$. However, as
a consequence of the rules of the k2 model, at time $t>t_{i}$, node $i$ can
gain no more than $m$ new edges in the influence network in any given time
step (i.e., $k_{i}^{(2)}(t+1)-k_{i}^{(2)}(t)\leq m$). Hence, strictly for
$t>t_{i}$, we require

$\frac{dk_{i}^{(2)}(\mathrm{t})}{dt}\leq m,$ (23)

which is only satisfied if the denominator of Eq. (22) grows at least as fast
as the numerator of Eq. (22). This requires $t^{2\delta}\geq t^{5\delta-2}$ as
$t\rightarrow\infty$. Hence, $2\delta\geq 5\delta-2$, giving $\delta\leq 2/3$.
Combining the conditions in Eq. (12a) and Eq. (23), we find that a power
function of the form given in Eq. (15) can only satisfy the requirements of
the k2 model if $\delta=2/3$.

To test the validity of our argument, we simulate the growth in the number of
edges for the k2 influence network. This is shown in Fig. 6 for $m=1$ & $3$.
The figure shows that, at large $t$, the number of edges in the influence
network scales as approximately $t^{4/3}$ corresponding to $\delta=2/3$, in
agreement with our prediction.

Figure 6: The number of edges in the k2 influence network. Data is averaged
over 100 simulations. Error bars are negligible. For large $t$, the number of
edges scales approximately with $t^{4/3}$, as indicated by the dashed line.

However, further analysis appears to contradict this conclusion. Firstly, we
can simulate the k2 model and track the degree of specific nodes over time,
see Fig. 7. The data has been averaged over $10^{4}$ simulations with the
shaded regions indicating the standard deviation; only with a very large
sample size can the average evolution of node $i$ be observed. In most
simulations, a node hardly grows at all, whereas in a few simulations, nodes
grow very quickly.

(a)  Figure 7: The evolution of the degree of individual nodes added at time
$t_{i}$ for the k2 model with $m=1$. The shaded region around the solid lines
indicates the standard deviation across 10000 simulations. The dashed lines
indicate the scaling expected for the BA model, see Eq. (15).

For a transient period after being added to the network, the average degree
evolution of a node appears to scale as $t^{1/2}$ which is the expected
scaling for linear preferential attachment. This appears to contradict the
$\delta=2/3$ scaling identified previously, although we note that the integral
in Eq. (17) is dominated by the oldest nodes in the network for $\delta>1/2$,
which do appear to grow faster than $t^{1/2}$ towards the end of the
simulation.

For newer nodes, after a transient period, the degree evolution appears to
deviate from $t^{1/2}$ scaling, but the scaling appears to transition to
$\delta<1/2$ rather than $\delta>1/2$. The time over which this transition
takes place increases with the time nodes are added to the network.

This suggests that the true functional form for the degree evolution in the k2
model involves two competing terms, the first scaling as $t^{2/3}$ which is
suppressed by $t_{i}$, and a second term which scales as $t^{1/2}$ which is
suppressed by $t$. We hypothesize, but at this stage cannot prove, that this
implies two scaling regimes: For fixed $t_{i}$ and $t\rightarrow\infty$, the
scaling of the degree evolution is dominated by a $t^{2/3}$ term to ensure
that $E(t)\propto t^{4/3}$ as $t\rightarrow\infty$. For
$t_{i}\rightarrow\infty$ and $t=t_{i}+\epsilon$ where $\epsilon\ll t_{i}$, the
degree evolution of node $i$ is dominated by a $t^{1/2}$ term. Competing
regimes of this type are not seen in standard non-linear preferential
attachment.

It is interesting to consider the origin of the $t^{1/2}$ scaling. Our results
are inconclusive, however, if we let $t_{i}\rightarrow\infty$ and set
$t=t_{i}+\epsilon$ with $\epsilon\ll t_{i}$, a Taylor expansion of Eq. (21)
gives

$\xi_{i}(t_{i})=b_{1}t_{i}^{4\delta-2}-b_{3}t_{i}^{2\delta-1}+\mathcal{O}(\epsilon),$
(24)

with positive constants $b_{1}$ and $b_{3}$, revealing that $\delta\geq 1/2$,
rather than $\delta\geq 2/3$, is sufficient for ensuring that
$\xi_{i}(t=t_{i})\geq 0$ as $t_{i}\rightarrow\infty$.

The mathematical argument presented here does not prove the limiting behavior
of the k2 model. However, the result does indicate that the inclusion of
simple nearest neighbor correlations in network growth can effect the scaling
of key observables. Despite initially appearing to grow as linear preferential
attachment, this simple scaling breaks down as the network grows. In the case
of real networks this may happen at an early stage in the evolution of a
network. However, as illustrated by the k2 model, the transient time during
which the model appears to grow according to linear preferential attachment
may be significant - it is not uncommon to analyze real networks with
$10^{4}-10^{5}$ nodes, yet in the case of the k2 model, particularly for
$m>1$, see Appendix B, the network is still in this transient period. In cases
like the k2 model with complex growth rules, oversimplified assumptions
derived from non-linear preferential attachment do not reflect reality.

###  IIIc Application to real world networks

(a)  (b)

(c)  (d)

(e)  (f)

Figure 8: The ratio of the cumulative relative attachment kernels for six real
world networks; (a) Facebook friendships Viswanath  _et al._ (2009), (b)
Youtube followers Mislove (2009), the APS citation network American Physical
Society (2018), (d) hep-ph arXiv collaborations Kunegis (2013), (e) the Flickr
network Mislove (2009), and (f) hyperlinks on English Wikipedia Mislove
(2009). For all networks the ratio is shown for early, $t/s=0.1$, and late,
$t/s=0.9$, in the evolution of the recorded network relative to the endpoint,
$s$; time is measured in the net number of edges added to the network.

Figure 8 shows the ratio of the cumulative relative attachment kernels for six
real world growing networks: (a) a regional friendship network on Facebook
Viswanath  _et al._ (2009), (b) the Youtube follower network Mislove (2009),
(c) the APS citation network American Physical Society (2018), (d) the hep-ph
arXiv collaboration network Kunegis  _et al._ (2013), (e) the Flickr follower
network Mislove (2009), and (f) the hyperlink network for English Wikipedia
Mislove (2009). For all networks, the cumulative relative attachment kernel is
calculated at two time points early and late in the network’s evolution
relative to the endpoint of the dataset. In some cases the full evolution of
the network is not known and is accounted for with a large initial graph at
$t=0$.

Two details are clear in Fig. 8. Firstly, on short timescales the relative
attachment kernels are approximately time independent, with only small
deviations observed. However, over longer time periods, the ratio of the
relative attachment kernels is not constant indicating time dependence.

There is significant diversity in the changes observed to the ratio of the
relative attachment kernels. In Fig. 8(a), (e) and (f), the ratio is (to a
good approximation) monotonically increasing. This implies that if we were to
approximate the attachment kernel of these networks using non-linear
preferential attachment, $\Pi(k)\propto k^{\gamma}$, the exponent $\gamma$
will appear to have reduced over time (the network growth is becoming more
sub-linear). Conversely, in Fig. 8(b) we see the opposite effect where the
ratio is approximately monotonically decreasing, implying an increase in the
exponent $\gamma$ (the network growth is becoming more super-linear). In the
cases of Fig. 8(a), (b) and (e), the form of non-linear attachment (i.e., sub-
linear, $\gamma<1$, or super-linear, $\gamma>1$) does not change. However, in
the case of the Wikipedia hyperlink network in Fig. 8(f), the relative
attachment kernel early in the network’s evolution appeared super-linear,
whereas by its endpoint, the attachment kernel was measured to be sub-linear.
Here we reiterate our previous criticism: if the attachment kernel of a
network is meant to predict its future evolution, how do we reconcile that
measurements across some time windows result in one prediction, while other
time windows result in a different, wholly incompatible prediction.

The story in Fig. 8(c) and (d) is more complex. In both cases, the ratios of
the relative attachment kernels initially appear to decrease below $1$, before
increasing at moderate degree and exceeding a ratio of $1$ at large degree.
This behavior is qualitatively very similar to the dynamics observed in Fig. 4
for the k2 model. In these cases, approximating the change in the attachment
kernel as a change in the non-linear preferential attachment kernel $\gamma$
is not easy since the data for small degree may imply an increase in $\gamma$
whereas the data for large degrees may imply a decrease in the exponent
$\gamma$. In such cases, simple assumptions of non-linear preferential
attachment are not sufficient to draw reliable conclusions about the future
evolution or past origin of a network.

A number of mechanisms may be responsible for the appearance of time
dependence in the relative attachment kernel. Generally, the simplest
explanations for time dependence in network growth relate to changes in
network parameters over time. In most network growth models (including in the
k2 model) these are assumed to be time independent for simplicity. An example
of such a parameter includes the number of edges added by each new node added
to a network, $m$.

In the BA model, the limiting degree distribution is given by

$p_{\infty}(k)=\frac{2m(m+1)}{k(k+1)(k+2)},$ (25)

where we note that this solution is valid for sufficiently large graphs given
any initial network at time $t_{0}$. As a result, if we let $m\rightarrow
m(t)$, it is plausible that we will observe transient behavior during which
the form of the degree distribution may change over time. The same argument
holds for measurements of the network attachment kernel. Such time dependence
in $m$ is not hypothetical and has been shown to be true by Leskovec  _et al._
Leskovec  _et al._ (2005) for a number of different growing networks including
citation networks, patent networks and affiliation networks. Some network
models consider growth in the average out-degree of nodes over time, see for
instance Barabási  _et al._ (2002). However, despite showing complex time
dependent scaling in the time evolution of individual nodes (the analytical
form for the degree distribution is not solvable), the authors argue that the
limiting degree evolution implies power-law scaling in the degree distribution
for large graphs. This may be true, but as the k2 model illustrates, in some
cases the transient phase of a network may be so long such that, for all
practical purposes, the limiting degree distribution is not necessarily
observed during the lifetime of a real world network. Slow convergence to a
limiting degree distribution has been noted previously for node copying models
in Ispolatov  _et al._ (2005).

Another simple parameters which may effect the time dependence of either the
degree distribution or attachment kernel of a network is the exponent for non-
linear preferential attachment. Consider letting $\gamma\rightarrow\gamma(t)$
for $\Pi(k)\propto k^{\gamma}$. It is already known that $\gamma$ effects the
limiting degree distribution of non-linear preferential attachment Krapivsky
_et al._ (2000), and that for $\gamma>1$, the degree distribution appears
scale free for a transient period Krapivsky and Krioukov (2008). Hence, any
variation in $\gamma$ is likely to add to the complexity of the time
dependence observed in network growth observables.

So far, we have provided only two examples of parameters whose time dependence
may alter the transient behavior of a network’s degree distribution or
attachment kernel. However, we would argue that any solvable network model
where a constant parameter appears in the analytical form for the degree
distribution is likely to exhibit time dependent transients if that constant
becomes time dependent itself.

In cases like the k2 model, where no individual parameter has been set to be
time dependent, the reasons for complex scaling in the observables of network
growth are less easily explained and may not be easy to elucidate from data.
In the k2 model, the origin lies in the implicit time dependence of the local
network structure which results in super-linear scaling in the influence
network, associated with gelation to important communities. However, any
network growth model where the attachment kernel is determined by an
observable which implicitly changes over time as the structure of the network
changes is likely to exhibit similar time dependence. For instance, network
growth based on attaching to nodes according to their betweenness is likely to
exhibit a time dependent network attachment kernel, as investigated by
Topirceanu  _et al._ (2018).

We note to the reader that it was our original intention to perform the
analysis in Fig. 8 with statistical rigor. However, this task has proven
difficult given that (1) our data breaks many of the assumptions underlying
common statistical tests, and (2) it is not yet fully understood how
techniques for estimating attachment kernels, like Newman’s method, are
effected/biased by time dependence – by construction, these techniques assume
the attachment kernel is time independent. We highlight the need to tackle
these problems with better statistical network analysis in future work.

##  IV Discussion & Conclusion

The study of complex networks has come to dominate complexity science in the
21st century, and is likely to become more prominent in a hyper-connected
world. Not only have complex networks become influential in physics and
mathematics, but their trans-disciplinary appeal has led to their use across
almost all areas of science and academia, from archaeology Knappett  _et al._
(2008) to neuroscience Bassett and Sporns (2017), economics Schweitzer  _et
al._ (2009) to epidemics Pastor-Satorras  _et al._ (2015), and many more.

A key feature of network science is the study of how networks emerge and
evolve over time, and numerous models and techniques have been developed to
explore this problem Barabási and Albert (1999); Krapivsky  _et al._ (2000);
Newman (2001); Vazquez (2000); Krapivsky and Redner (2001); Barabási  _et al._
(2002); Jeong  _et al._ (2003); Vázquez (2003); Chung  _et al._ (2003);
Saramäki and Kaski (2004); Evans and Saramäki (2005); Goldberg  _et al._
(2015); Pham  _et al._ (2015); Newman (2018); Barabási  _et al._ (2016). In
almost all cases, these models and techniques have their limitations and are
only applicable to the real world under a number of key constraints. Despite
this, the spread of network science has been so extensive that many of these
approaches are being used without a robust understanding of their underlying
assumptions. In this paper we have discussed two such assumptions: (1) that
the rules underlying network growth do not depend on time, and (2) that the
degree of nodes in a network is the key observable determining network
evolution.

The number of research papers discussing network growth and attempting to
infer their underlying mechanisms is vast, often guided by simple network
models to inform their analysis. However, the models most frequently discussed
in popular network science textbooks, for instance Newman (2018); Barabási
_et al._ (2016), almost always assume that underlying growth rules are fixed
in time. As a result, it is not particularly surprising that most papers
inferring network growth mechanisms also make these assumptions. In many
contexts such assumptions are sensible and essential, allowing for
analytically tractable calculations which may otherwise be impossible.
However, in some real world scenarios such approaches may not be suitable. A
selection of papers which do consider the implication of these assumptions
include Sun  _et al._ (2020); Dangalchev (2004) in the context of preferential
attachment models, Amati  _et al._ (2019); Amano  _et al._ (2018) in
organizational networks, Topirceanu  _et al._ (2018) in social networks, and
others Wang  _et al._ (2018); Lambiotte  _et al._ (2016); Bhat  _et al._
(2016).

In this paper, we have tried to highlight how very simple network growth rules
can break both the time-independence of the network degree distribution and
the time-independence of the node-node attachment probability. We have done
this by introducing the k2 model, a simple variant of the Barabási-Albert
model where the attractiveness of a node is correlated to the attractiveness
of a node’s neighbors. Even though such a network growth rule does not contain
an explicit time dependence, the formation of clusters means that a node’s
attractiveness is implicitly time dependent through its dependence on its
local environment. This mechanism is relevant for real-world networks
involving mutual benefit where a node gains an advantage from being connected
to an influential neighbor, such as in collaboration networks Li  _et al._
(2019), or citation networks Vazquez (2000), or indirectly in systems with
neighbor-neighbor interactions and copying processes Ohno (2013); Kang (2020);
Bhat  _et al._ (2016); Lambiotte  _et al._ (2016); Goldberg  _et al._ (2015);
Toivonen  _et al._ (2009); Ispolatov  _et al._ (2005); Kim  _et al._ (2002);
Granovetter (1977).

The k2 model shows that for small networks, the degree distribution appears
approximately power-law, and the attachment kernel is approximately linear,
both of which are consistent with preferential attachment. However, after a
lengthy transient period, both the degree distribution and attachment kernel
show significant deviations from the simple scaling predicted for preferential
attachment. These deviations grow over time showing strong time dependence. We
support these findings with an approximate analytical treatment showing that
assumptions of simple scaling forms in the evolution of individual nodes in
the k2 model results in inconsistencies in the mathematics, suggesting that
numerous scaling regimes are interacting and changing over time.

The k2 model is an idealized network growth model – it does not reflect real-
world networks, even if the underlying mechanism has explanatory value.
However, changes in the degree distribution and the attachment kernel can also
be seen in real data of varying origins. In six networks for which dynamic
network data is available (three social networks, one hyperlink network, one
collaboration network, and one citation network), we have found that these
networks are approximately time independent on short timescales, but show
significant time dependency, and diversity in that dependency, over longer
timescales. In some cases, this time dependency may have simple origins such
as node aging, changes in the average out-degree over time, or changes in the
exponent for preferential attachment. However, in some cases, time dependency
may arise implicitly resulting in complex scaling.

In the context of the wider debate on “scale free” networks, it is worth
considering the following. If the generative mechanisms underlying network
growth are not constant in time, is it plausible that the functional form for
network degree distributions will be constant in time? In many cases the
change over time may be very small. However, if we apply a strict definition
of “scale freeness,” small changes in the degree distribution may be
sufficient to induce changes in the most-likely functional form for the degree
distribution as predicted using the current state of the art measures Broido
and Clauset (2019). If this is in fact the case, this may explain why only
$4\%$ of real world networks have been identified as scale free Broido and
Clauset (2019).

To conclude, as long as network science techniques are being applied to the
real world by experts and non-experts alike, it is essential that we
understand the limitations of simple models and consider their underlying
assumptions. Here, we have shown how very simple, sociologically meaningful
changes to network growth models can profoundly effect both the time
dependence of network growth, and the assumption that node degree determines
network evolution.

While the k2 model serves an illustrative purpose, the ideas drawn from its
evolution apply to real networks, which show diverse time dependence over
extended durations. While this appears to be a disappointing conclusion, we
note that over short time periods network growth does appear to be
approximately time independent. In many cases the origin of the time
dependence may have a simple explanation, which, if accounted for in
prediction models, may avoid excessive errors in forecasting the evolution of
networks and the dynamics taking place on those networks. However, knowing the
impact of these assumptions is only possible if simple steps are taken to
check their validity. It is our hope that this paper will encourage more
people to do so.

###### Acknowledgements.

M.F. thanks Renaud Lambiotte, Henrik Jeldtoft Jensen and Vaiva Vasiliauskaite
for their comments. M.F. thanks the hospitality of the Miyake laboratory at
Tokyo Institute of Technology where much of this work was initiated and
carried out. M.F. gratefully acknowledges a PhD studentship from the
Engineering and Physical Sciences Research Council through Grant No.
EP/N509486/1. KO was supported by the Japan Society for the Promotion of
Science (KAKENHI), Grant-in-Aid for Scientific Research (C), Grant Number
18K11500.

M.F., J.L., S.A. and K.O. proposed the project and defined the k2 model. M.F.
and J.L. ran simulations and analyzed the k2 model. K.O., T.S.E. and M.F.
developed the mathematical background of the model. S.A., K.O. and Y.M.
proposed the second degree as a network variable of interest. M.F. proposed
challenging the assumptions of simple scaling in growing networks using the k2
model. J.L. analyzed the APS citation network. K.O., K.Y., Y.M., T.S.E. and
K.C. supervised the project. M.F. wrote the manuscript. All authors commented
on and approved the final manuscript.

Appendices

##  A Additional mathematical details

Generalization of the k2 model. It is possible to generalize the form of
attachment shown in Eq. (2) by including a coefficient to the second term that
adjusts the total weighting of next-nearest neighbors. This can be written as

$\Pi_{i}^{(k2)}=\frac{k_{i}^{(1)}+\epsilon\sum_{\alpha=1}^{k_{i}^{(1)}}(k_{i\alpha}^{(1)}-\delta)}{\sum_{j=1}^{N}\left(k_{j}^{(1)}+\epsilon\sum_{\alpha=1}^{k_{j}^{(1)}}(k_{j\alpha}^{(1)}-\delta)\right)},$
(A1)

where we require $\epsilon\geq 0$. If $\epsilon=0$, the k2 model reduces to
the BA model, $\Pi_{i}^{(k2)}\rightarrow\Pi_{i}^{(BA)}$. Alternatively, if
$\epsilon=1$, $\delta=1$, Eq. (A1) reduces to the k2 model, Eq. (2). In this
paper, to illustrate concerns about time invariance in the scaling of
attachment kernels and degree distributions, we will only focus on the
$\epsilon=1$, $\delta=1$, case shown in Eq. (2). Note that the general case
presented in Eq. (A1) is very closely related to the 2 levels model proposed
by Dangalchev Dangalchev (2004). However, the 2 levels model double counts the
first degree neighbors of node $i$, $\epsilon=1$, $\delta=0$, and in the
analysis of the model, Dangalchev only looked at very small networks in which
issues concerning the time invariance of the attachment kernel and degree
distributions cannot be seen.

Formal definition of the k2 model. We can define $k_{i}^{(\ell)}$ as the
number of unique nodes which are $\ell$ or fewer steps from the target node
$i$, excluding node $i$ itself. Let $\mathcal{N}_{i\ell}(t)$ be the set of
nodes which are distance $\ell$ from node $i$ in the network at time $t$, that
is $\mathcal{G}(t)$ which is after all nodes and edges have been added and
this has $m_{0}+t\approx t$ nodes. The distance between nodes $i$ and $j$ is
defined as the minimum number of edges which need to be crossed in order to
form a continuous path from node $i$ to node $j$. Then we define

$\displaystyle q^{(\ell)}_{i}(t)$ $\displaystyle=|\mathcal{N}_{i\ell}(t)|,$
(A2a) $\displaystyle k^{(\ell)}_{i}(t)$
$\displaystyle=\sum_{j=1}^{\ell}q^{(j)}_{i}(t).$ (A2b)

where $k_{i}^{(1)}(t)=q^{(1)}_{i}(t)$. In this paper we do not consider
attachment kernel’s proportional to $k_{i}^{(\ell)}(t)$ for $\ell>2$. However,
it is interesting to note that if the attachment kernel were proportional to
$k_{i}^{(\ell)}(t)$ and $\ell\geq D(t)$, where $D(t)$ is the network diameter,
this attachment kernel is equivalent to random attachment until the growing
network has diameter $D(t)>\ell$.

Derivation of Eq. (1). When $m=1$, $k_{j}^{(2)}(t)$ can be written as

$k_{j}^{(2)}(t)=\sum_{\alpha=1}^{k_{j}^{(1)}(t)}k_{j_{\alpha}}^{(1)}(t).$ (A3)

Thus, the denominator of Eq. (1) can be rewritten as

$\displaystyle\sum_{j=1}^{N}k_{j}^{(2)}(t)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{N}\sum_{\alpha=1}^{k_{j}^{(1)}(t)}k_{j_{\alpha}}^{(1)}(t)$
(A4) $\displaystyle=$ $\displaystyle\sum_{l=1}^{N}n_{l}(t)k_{l}^{(1)}(t)$

where

$n_{l}(t)=k_{l}^{(1)}(t).$ (A5)

Therefore, we obtain

$\sum_{j=1}^{N}k_{j}^{(2)}(t)=\sum_{l=1}^{N}\left(k_{l}^{(1)}(t)\right)^{2}.$
(A6)

For $m>1$, we can test the validity of Eq. (A6). Figure A1 plots the ratio of
the two sums, for $m=1,3$, defined as

$\frac{S_{2}(t)}{S_{1}(t)}=\frac{\sum_{j=1}^{N}k_{j}^{(2)}(t)}{\sum_{l=1}^{N}(k_{l}^{(1)}(t))^{2}},$
(A7)

against time. The figure has been averaged over 100 simulations of the k2
model. Figure A1 indicates that for $m=1$, $S_{2}(t)/S_{1}(t)=1$ for all $t$,
as expected. For $m>1$, there is a noticeable difference between $S_{2}(t)$
and $S_{1}(t)$ at very small times in the network’s evolution. This is to be
expected since when the network is small, the probability of acquiring non-
unique second degree neighbors is small, but not negligible. As the network
evolves, the ratio $S_{2}(t)/S_{1}(t)$ quickly converges to $1$, with
$S_{2}(t)/S_{1}(t)>0.9$ by $t=10^{3}$. This indicates that Eq. (A7) is a good
approximation even for $m>1$.

Figure A1: The ratio of the sum over the second degree of each node in the
network to the sum over the first degree squared for each node indicated in
the network, see Eq. (A7). The ratio equals one for $m=1$, and converges to
one for $m>1$.

Derivation of Eq. (10). Let’s consider a set of nodes $i$, the neighbors
$i_{\alpha}$ connected to node $i$, and the node $i_{\alpha(\beta)}$ connected
to node $i_{\alpha}$. Here, $\alpha=1,\cdots,k_{i}^{(1)}(t)$, and
$\beta=1,\cdots,k_{\alpha}^{(1)}(t)-1$. Then, the k2 model with $m=1$ is
applied to nodes $i_{\alpha}$ as follows:

$\frac{d}{dt}k_{i_{\alpha}}^{(1)}(t)=\frac{k_{i_{\alpha}}^{(2)}(t)}{\sum_{j=1}^{N}k_{j}^{(2)}(t)}\
\text{ for }\ \forall\alpha.$ (A8)

Next, by using Eq. (3), the numerator of the right side of Eq. (A8) can be
rewritten as

$k_{i_{\alpha}}^{(2)}(t)=k_{i}^{(1)}(t)+\sum_{\beta=1}^{k_{\alpha}^{(1)}(t)-1}k_{i_{\alpha(\beta)}}^{(1)}(t).$
(A9)

Therefore, we obtain the dynamical equations of node $i_{\alpha}$ as follows:

$\frac{d}{dt}k_{i_{\alpha}}^{(1)}(t)=\frac{k_{i}^{(1)}(t)+\sum_{\beta=1}^{k_{\alpha}^{(1)}(t)-1}k_{i_{\alpha(\beta)}}^{(1)}(t)}{\sum_{j=1}^{N}\left(k_{j}^{(1)}(t)\right)^{2}}.$
(A10)

Summing $k_{i_{\alpha}}^{(1)}(t)$ from $\alpha=1$ to $\alpha=k_{i}^{(1)}(t)$
for each side, we obtain

$\frac{d}{dt}\left(\sum_{\alpha=1}^{k_{i}^{(1)}(t)}k_{i_{\alpha}}^{(1)}(t)\right)=\\\
\frac{\sum_{\alpha=1}^{k_{i}^{(1)}(t)}\left(k_{i}^{(1)}(t)+\sum_{\beta=1}^{k_{\alpha}^{(1)}(t)-1}k_{i_{\alpha}(\beta)}^{(1)}(t)\right)}{\sum_{j=1}^{N}\left(k_{j}^{(1)}(t)\right)^{2}}.$
(A11)

Recall that,
$k_{i}^{(2)}(t)=\sum_{\alpha=1}^{k_{i}^{(1)}}k_{i_{\alpha}}^{(1)}(t)$. Thus,
Eq. (A11) can be modified as follows:

$\displaystyle\frac{d}{dt}k_{i}^{(2)}(t)$ $\displaystyle=$
$\displaystyle\frac{\sum_{\alpha=1}^{k_{i}^{(1)}(t)}k_{i}^{(1)}(t)+\sum_{\alpha=1}^{k_{i}^{(1)}(t)}\sum_{\beta=1}^{k_{\alpha}^{(1)}(t)-1}k_{i_{\alpha}(\beta)}^{(1)}(t)}{\sum_{j=1}^{N}\left(k_{j}^{(1)}(t)\right)^{2}}$
(A12) $\displaystyle=$
$\displaystyle\frac{k_{i}^{(1)}(t)k_{i}^{(1)}(t)+\sum_{\alpha=1}^{k_{i}^{(1)}(t)}\sum_{\beta=1}^{k_{\alpha}^{(1)}(t)-1}k_{i_{\alpha}(\beta)}^{(1)}(t)}{\sum_{j=1}^{N}\left(k_{j}^{(1)}(t)\right)^{2}}$
$\displaystyle=$
$\displaystyle\frac{\left(k_{i}^{(1)}(t)\right)^{2}+\sum_{\alpha=1}^{k_{i}^{(1)}(t)}\sum_{\beta=1}^{k_{\alpha}^{(1)}(t)-1}k_{i_{\alpha}(\beta)}^{(1)}(t)}{\sum_{j=1}^{N}\left(k_{j}^{(1)}(t)\right)^{2}}.$

This is equivalent to Eq. (10).

##  B Additional Simulation Results

Degree distribution and relative attachment kernel for $\bm{m=3}$. In addition
to the results presented in the main manuscript for the k2 model with $m=1$,
Fig. B2 shows the degree distribution and relative attachment kernel for the
k2 model with $m=3$. The results are fully consistent with those shown for
$m=1$ previously. Initially, the degree distribution appears qualitatively
similar to the power-law scaling expected from linear preferential attachment.
This is associated with an approximately linear relative attachment kernel.
However, as the network evolves, clear deviations from the simple scaling form
predicted by the BA model appear in both the degree distribution and the
relative attachment kernel. Note, the time for these deviations to become
significant increases and $m$ is increased. The magnitude of the deviations
shown for $m=1$ exceed those for $m=3$.

(a)

(b)

Figure B2: The (a) degree distribution and (b) relative attachment kernel for
the k2 model over time with $m=3$. The dashed lines show the expected scaling
for the BA model. Early in the growth of the k2 model, the evolution of the
network is largely indistinguishable from the BA model. As the k2 model grows,
both the degree distribution and relative attachment kernel deviate
significantly from the simple scaling predicted by the BA model. (a)  Figure
B3: The evolution of the degree of individual nodes added at time $t_{i}$ for
the k2 model with $m=3$, averaged over 10000 simulations. The shaded region
around the solid lines indicates the standard deviation across the
simulations. The dashed lines indicate the power function scaling that would
be expected from the BA model, see Eq. (15).

Degree evolution for $\bm{m=3}.$ Figure B3 shows the evolution of individual
nodes added at time $t_{i}$ in the k2 model for $m=3$. The figure is
consistent with the previous result shown for $m=1$. Note in particular that
the magnitude of the standard deviation is significantly smaller than for
$m=1$. This suggests that the results for $m=3$ better reflect the true
underlying degree scaling in the k2 model than the result for $m=1$. It is
especially clear how closely nodes added at large $t_{i}$ follow the $t^{1/2}$
scaling predicted by the BA model during the initial phase after the node is
added to the network.

Two additional details are worth highlighting: (1) After the initial transient
phase during which nodes scale approximately with $t^{1/2}$, the scaling
deviates from $\delta=1/2$ scaling to $\delta<1/2$, but the magnitude of the
change is much smaller than for $m=1$. This result is of particular interest
since extended transient times and smaller deviations from $\delta=1/2$
scaling may explain why the transient period for the degree distribution and
relative attachment kernel shown in Fig. B2 are longer, and follow the BA
model more closely, than the equivalent for $m=1$. (2) For $t_{i}=10$, it
appears that shortly after entering the $\delta<1/2$ phase, the exponent
increases again and appears to approach $\delta>1/2$, although the effect is
very small. Longer simulations are required to clearly elucidate the scaling
behavior of individual nodes, but these simulations are computationally
challenging in the current framework.

## References

  * Vasiliauskaite and Rosas (2020) Vaiva Vasiliauskaite and Fernando E. Rosas, “Understanding complexity via network theory: a gentle introduction,” (2020), arXiv:2004.14845 [physics.soc-ph] .
  * Watts and Strogatz (1998) Duncan J Watts and Steven H Strogatz, “Collective dynamics of ‘small-world’ networks,” Nature 393, 440 (1998).
  * Price (1976) D.J.de S. Price, “A general theory of bibliometric and other cumulative advantage processes,” Journal of the American Society for Information Science 27, 292–306 (1976).
  * Barabási and Albert (1999) Albert-László Barabási and Réka Albert, “Emergence of scaling in random networks,” Science 286, 509–512 (1999).
  * Broido and Clauset (2019) Anna D Broido and Aaron Clauset, “Scale-free networks are rare,” Nature Communications 10, 1017 (2019).
  * Newman (2005) Mark EJ Newman, “Power laws, pareto distributions and zipf’s law,” Contemporary Physics 46, 323–351 (2005).
  * Albert  _et al._ (1999) Réka Albert, Hawoong Jeong, and Albert-László Barabási, “Diameter of the World-Wide Web,” Nature 401, 130 (1999).
  * Redner (1998) Sidney Redner, “How popular is your paper? an empirical study of the citation distribution,” The European Physical Journal B-Condensed Matter and Complex Systems 4, 131–134 (1998).
  * i Cancho and Solé (2001) Ramon Ferrer i Cancho and Richard V Solé, “The small world of human language,” Proceedings of the Royal Society of London B: Biological Sciences 268, 2261–2265 (2001).
  * Liljeros  _et al._ (2001) Fredrik Liljeros, Christofer R Edling, Luis A Nunes Amaral, H Eugene Stanley, and Yvonne Åberg, “The web of human sexual contacts,” Nature 411, 907 (2001).
  * Java  _et al._ (2007) Akshay Java, Xiaodan Song, Tim Finin, and Belle Tseng, “Why we twitter: understanding microblogging usage and communities,” in  _Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis_ (ACM, 2007) pp. 56–65.
  * Cohen and Havlin (2003) Reuven Cohen and Shlomo Havlin, “Scale-free networks are ultrasmall,” Physical Review Letters 90, 058701 (2003).
  * Crucitti  _et al._ (2003) Paolo Crucitti, Vito Latora, Massimo Marchiori, and Andrea Rapisarda, “Efficiency of scale-free networks: error and attack tolerance,” Physica A: Statistical Mechanics and its Applications 320, 622–642 (2003).
  * Holme (2019) Petter Holme, “Rare and everywhere: Perspectives on scale-free networks,” Nature Communications 10, 1016 (2019).
  * Clauset  _et al._ (2009) Aaron Clauset, Cosma Rohilla Shalizi, and Mark EJ Newman, “Power-law distributions in empirical data,” SIAM review 51, 661–703 (2009).
  * Radicchi  _et al._ (2008) Filippo Radicchi, Santo Fortunato, and Claudio Castellano, “Universality of citation distributions: Toward an objective measure of scientific impact,” Proceedings of the National Academy of Sciences 105, 17268–17272 (2008).
  * Lima-Mendez and van Helden (2009) Gipsi Lima-Mendez and Jacques van Helden, “The powerful law of the power law and other myths in network biology,” Molecular BioSystems 5, 1482–1493 (2009).
  * Willinger  _et al._ (2009) Walter Willinger, David Alderson, and John C Doyle, “Mathematics and the internet: A source of enormous confusion and great potential,” Notices of the American Mathematical Society 56, 586–599 (2009).
  * Golosovsky (2017) Michael Golosovsky, “Power-law citation distributions are not scale-free,” Physical Review E 96, 032306 (2017).
  * Stumpf and Porter (2012) Michael PH Stumpf and Mason A Porter, “Critical truths about power laws,” Science 335, 665–666 (2012).
  * Sendiña-Nadal  _et al._ (2016) I Sendiña-Nadal, M M Danziger, Z Wang, S Havlin, and S Boccaletti, “Assortativity and leadership emerge from anti-preferential attachment in heterogeneous networks,” Scientific Reports 6, 21297 (2016).
  * Kang (2020) Anthony Minsuk Kang, “Connectivity in biological networks: Are they really scale-free?” Network Biology (2020).
  * Goh  _et al._ (2002) Kwang-Il Goh, Eulsik Oh, Hawoong Jeong, Byungnam Kahng, and Doochul Kim, “Classification of scale-free networks,” Proceedings of the National Academy of Sciences 99, 12583–12588 (2002).
  * House  _et al._ (2015) Thomas House, Jonathan M Read, Leon Danon, and Matthew J Keeling, “Testing the hypothesis of preferential attachment in social network formation,” EPJ Data Science 4, 13 (2015).
  * Barabási  _et al._ (2016) Albert-László Barabási _et al._ ,  _Network science_ (Cambridge university press, 2016).
  * Voitalov  _et al._ (2019) Ivan Voitalov, Pim van der Hoorn, Remco van der Hofstad, and Dmitri Krioukov, “Scale-free networks well done,” Physical Review Research 1, 033034 (2019).
  * Gerlach and Altmann (2019) Martin Gerlach and Eduardo G. Altmann, “Testing statistical laws in complex systems,” Physical Review Letters 122, 168301 (2019).
  * Kiss  _et al._ (2008) Istvan Z Kiss, Darren M Green, and Rowland R Kao, “The effect of network mixing patterns on epidemic dynamics and the efficacy of disease contact tracing,” Journal of The Royal Society Interface 5, 791–799 (2008).
  * Piraveenan  _et al._ (2012) M. Piraveenan, M. Prokopenko, and A. Zomaya, “Assortative mixing in directed biological networks,” IEEE/ACM Transactions on Computational Biology and Bioinformatics 9, 66–78 (2012).
  * Krapivsky  _et al._ (2000) P. L. Krapivsky, S. Redner, and F. Leyvraz, “Connectivity of growing random networks,” Physical Review Letters 85, 4629–4632 (2000).
  * Krapivsky and Krioukov (2008) Paul Krapivsky and Dmitri Krioukov, “Scale-free networks as preasymptotic regimes of superlinear preferential attachment,” Physical Review E 78, 026114 (2008).
  * Newman (2001) Mark EJ Newman, “Clustering and preferential attachment in growing networks,” Physical review E 64, 025102 (2001).
  * Jeong  _et al._ (2003) Hawoong Jeong, Zoltan Néda, and Albert-László Barabási, “Measuring preferential attachment in evolving networks,” Europhysics Letters 61, 567 (2003).
  * Massen and Doye (2007) Claire P. Massen and Jonathan P. K. Doye, “Preferential attachment during the evolution of a potential energy landscape,” The Journal of Chemical Physics 127, 114306 (2007).
  * Gómez  _et al._ (2011) Vicenç Gómez, Hilbert J. Kappen, and Andreas Kaltenbrunner, “Modeling the structure and evolution of discussion cascades,” in  _Proceedings of the 22Nd ACM Conference on Hypertext and Hypermedia_, HT ’11 (ACM, New York, NY, USA, 2011) pp. 181–190.
  * Sheridan  _et al._ (2012) Paul Sheridan, Yuichi Yagahara, and Hidetoshi Shimodaira, “Measuring preferential attachment in growing networks with missing-timelines using markov chain monte carlo,” Physica A: Statistical Mechanics and its Applications 391, 5031 – 5040 (2012).
  * Kunegis  _et al._ (2013) Jérôme Kunegis, Marcel Blattner, and Christine Moser, “Preferential attachment in online networks: Measurement and explanations,” in  _Proceedings of the 5th annual ACM web science conference_ (ACM, 2013) pp. 205–214.
  * Pham  _et al._ (2015) Thong Pham, Paul Sheridan, and Hidetoshi Shimodaira, “Pafit: A statistical method for measuring preferential attachment in temporal complex networks,” PloS One 10, e0137796 (2015).
  * Herdağdelen  _et al._ (2007) A. Herdağdelen, E. Aygün, and H. Bingol, “A formal treatment of generalized preferential attachment and its empirical validation,” Europhysics Letters 78, 60007 (2007).
  * Leskovec  _et al._ (2005) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos, “Graphs over time: densification laws, shrinking diameters and possible explanations,” in  _Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining_ (2005) pp. 177–187.
  * Ronda-Pupo and Pham (2018) Guillermo Armando Ronda-Pupo and Thong Pham, “The evolutions of the rich get richer and the fit get richer phenomena in scholarly networks: the case of the strategic management journal,” Scientometrics 116, 363–383 (2018).
  * Sheridan and Onodera (2018) Paul Sheridan and Taku Onodera, “A preferential attachment paradox: How preferential attachment combines with growth to produce networks with log-normal in-degree distributions,” Scientific Reports 8, 2811 (2018).
  * Eisenberg and Levanon (2003) Eli Eisenberg and Erez Y Levanon, “Preferential attachment in the protein network evolution,” Physical Review Letters 91, 138701 (2003).
  * Kondor  _et al._ (2014) Dániel Kondor, Márton Pósfai, István Csabai, and Gábor Vattay, “Do the rich get richer? an empirical analysis of the bitcoin transaction network,” PloS One 9, e86197 (2014).
  * Perc (2012) Matjaž Perc, “Evolution of the most common english words and phrases over the centuries,” Journal of The Royal Society Interface 9, 3323–3328 (2012).
  * Szell and Thurner (2010) Michael Szell and Stefan Thurner, “Measuring social dynamics in a massive multiplayer online game,” Social Networks 32, 313–329 (2010).
  * Li  _et al._ (2019) Weihua Li, Tomaso Aste, Fabio Caccioli, and Giacomo Livan, “Early coauthorship with top scientists predicts success in academic careers,” Nature Communications 10, 5170 (2019).
  * Vazquez (2000) Alexei Vazquez, “Knowing a network by walking on it: emergence of scaling,” (2000), arXiv:cond-mat/0006132 [cond-mat.stat-mech] .
  * Lambiotte  _et al._ (2016) R. Lambiotte, P. L. Krapivsky, U. Bhat, and S. Redner, “Structural transitions in densifying networks,” Physical Review Letters 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,” Physical Review E 94, 062302 (2016).
  * Krapivsky and Redner (2005) P. L. Krapivsky and S. Redner, “Network growth by copying,” Physical Review E 71, 036118 (2005).
  * Dangalchev (2004) Chavdar Dangalchev, “Generation models for scale-free networks,” Physica A: Statistical Mechanics and its Applications 338, 659 – 671 (2004).
  * Wang  _et al._ (2018) Shudong Wang, Xinzeng Wang, Qifang Song, and Yuanyuan Zhang, “High-Order Degree and Combined Degree in Complex Networks,” Mathematical Problems in Engineering 2018, 4925841 (2018).
  * Topirceanu  _et al._ (2018) Alexandru Topirceanu, Mihai Udrescu, and Radu Marculescu, “Weighted Betweenness Preferential Attachment: A New Mechanism Explaining Social Network Formation and Evolution,” Scientific Reports 8, 10871 (2018).
  * Amano  _et al._ (2018) Sun-ichi Amano, Ken-ichiro Ogawa, and Yoshihiro Miyake, “Node property of weighted networks considering connectability to nodes within two degrees of separation,” Scientific Reports 8, 8464 (2018).
  * Mislove (2009) Alan E Mislove,  _Online social networks: measurement, analysis, and applications to distributed information systems_ , Ph.D. thesis, Rice University (2009).
  * Granovetter (1977) Mark S Granovetter, “The strength of weak ties,” in  _Social Networks_ (Elsevier, 1977) pp. 347–367.
  * Burt (1992) Ronald S Burt,  _Structural holes: The social structure of competition_ (Harvard University Press, 1992).
  * Katz (1953) L. Katz, “A new status index derived from sociometric index,” Psychometrika 18, 39–43 (1953).
  * Newman (2018) M. Newman,  _Networks_, 2nd ed. (OUP Oxford, 2018).
  * Brin and Page (1998) S. Brin and L. Page, “The anatomy of a large-scale hypertextual web search engine,” Computer networks and ISDN systems 30, 107–117 (1998).
  * Toivonen  _et al._ (2009) Riitta Toivonen, Lauri Kovanen, Mikko Kivelä, Jukka-Pekka Onnela, Jari Saramäki, and Kimmo Kaski, “A comparative study of social network models: Network evolution models and nodal attribute models,” Social Networks 31, 240–254 (2009).
  * Goldberg  _et al._ (2015) S.R. Goldberg, H. Anthony, and T.S. Evans, “Modelling citation networks,” Scientometrics 105, 1577–1604 (2015).
  * Ohno (2013) Susumu Ohno,  _Evolution by gene duplication_ (Springer Science & Business Media, 2013).
  * Ispolatov  _et al._ (2005) Iaroslav Ispolatov, Pavel L Krapivsky, and Anton Yuryev, “Duplication-divergence model of protein interaction network,” Physical review E 71, 061911 (2005).
  * Kim  _et al._ (2002) J Kim, PL Krapivsky, Byungnam Kahng, and S Redner, “Infinite-order percolation and giant fluctuations in a protein interaction network,” Physical Review E 66, 055101 (2002).
  * Viswanath  _et al._ (2009) Bimal Viswanath, Alan Mislove, Meeyoung Cha, and Krishna P Gummadi, “On the evolution of user interaction in facebook,” in  _Proceedings of the 2nd ACM workshop on Online social networks_ (2009) pp. 37–42.
  * American Physical Society (2018) American Physical Society, “APS Data Sets for Research,” https://journals.aps.org/datasets (2018).
  * Kunegis (2013) Jérôme Kunegis, “Konect: The koblenz network collection,” in  _Proceedings of the 22nd International Conference on World Wide Web_, WWW ’13 Companion (Association for Computing Machinery, New York, NY, USA, 2013) p. 1343–1350.
  * Barabási  _et al._ (2002) Albert-Laszlo Barabási, Hawoong Jeong, Zoltan Néda, Erzsebet Ravasz, Andras Schubert, and Tamas Vicsek, “Evolution of the social network of scientific collaborations,” Physica A: Statistical mechanics and its applications 311, 590–614 (2002).
  * Knappett  _et al._ (2008) Carl Knappett, Tim Evans, and Ray Rivers, “Modelling maritime interaction in the aegean bronze age,” Antiquity 82, 1009–1024 (2008).
  * Bassett and Sporns (2017) Danielle S Bassett and Olaf Sporns, “Network neuroscience,” Nature Neuroscience 20, 353 (2017).
  * Schweitzer  _et al._ (2009) Frank Schweitzer, Giorgio Fagiolo, Didier Sornette, Fernando Vega-Redondo, Alessandro Vespignani, and Douglas R White, “Economic networks: The new challenges,” Science 325, 422–425 (2009).
  * Pastor-Satorras  _et al._ (2015) Romualdo Pastor-Satorras, Claudio Castellano, Piet Van Mieghem, and Alessandro Vespignani, “Epidemic processes in complex networks,” Reviews of Modern Physics 87, 925 (2015).
  * Krapivsky and Redner (2001) P. L. Krapivsky and S. Redner, “Organization of growing random networks,” Physical Review E 63, 066123 (2001).
  * Vázquez (2003) A. Vázquez, “Growing networks with local rules: preferential attachment, clustering hierarchy and degree correlations,” Physical Review E 67, 056104 (2003).
  * Chung  _et al._ (2003) Fan Chung, Linyuan Lu, T. Gregory Dewey, and David J. Galas, “Duplication models for biological networks,” Journal of Computational Biology 10, 677–687 (2003).
  * Saramäki and Kaski (2004) J. Saramäki and K. Kaski, “Scale-free networks generated by random walkers,” Physica A: Statistical Mechanics and its Applications 341, 80 (2004).
  * Evans and Saramäki (2005) T. S. Evans and J. P. Saramäki, “Scale free networks from self-organisation,” Physical Review E 72, 026138 (2005).
  * Sun  _et al._ (2020) Jun Sun, Matú š Medo, and Steffen Staab, “Time-invariant degree growth in preferential attachment network models,” Physical Review E 101, 022309 (2020).
  * Amati  _et al._ (2019) Viviana Amati, Alessandro Lomi, and Daniele Mascia, “Some days are better than others: Examining time-specific variation in the structuring of interorganizational relations,” Social Networks 57, 18 – 33 (2019).