222020175791

# Analysis of a Model for Generating Weakly Scale-free Networks

Raheel Anwar1  Muhammad Irfan Yousuf2  Muhammad Abid3  Karl Franzens
Universität,Graz, Austria
Korea Institute of Science and Technology, Seoul, Korea
Pakistan Institute of Engineering and Applied Sciences, Islamabad, Pakistan

(2019-9-27; 2020-1-10; 2020-1-13)

###### Abstract

It is commonly believed that real networks are scale-free and the fraction of
nodes $P(k)$ with degree $k$ satisfies the power-law $P(k)\propto k^{-\gamma}$
for $k>k_{min}>0$. Preferential attachment is the mechanism that has been
considered responsible for such organization of these networks. In many real
networks, degree distribution before the $k_{min}$ varies very slowly to the
extent of being uniform as compared to the degree distribution for
$k>k_{min}$. In this paper, we propose a model that describes this particular
degree distribution for the whole range of $k>0$. We adopt a two step
approach. In the first step, at every time stamp we add a new node to the
network and attach it to an existing node using preferential attachment
method. In the second step, we add edges between existing pairs of nodes with
the node selection based on the uniform probability distribution. Our approach
generates weakly scale-free networks that closely follow the degree
distribution of real-world networks. We perform a comprehensive mathematical
analysis of the model in the discrete domain and compare the degree
distribution generated by this model with that of real-world networks.

###### keywords:

Generative Models, Preferential Attachment Model, Social Graphs,

##  1 Introduction

Complex Networks have a wide variety of applications in many domains including
economics, business, transportation, and natural, social and computer
sciences, to name a few. Examples of such networks include online social
networks, biological networks, technological networks, scientific
collaboration networks, citation networks and many more. The complex structure
of these networks has remained the main focus of studies in the past. Many
studies claim that these networks are scale-free networks. However, contrary
to this common belief, recent studies show that scale-freeness is rare in
real-world networks Broido and Clauset (2018). Generally, a network is scale-
free if the fraction of nodes with degree $k$ follows a power-law distribution
$k^{-\gamma}$, where $\gamma>$ 1\. Typically, it is believed that the
$\gamma\in[2,3]$ or in other words the degree distribution of such networks
follows a preferential attachment, i.e., the rich-get-richer mechanism. In
order to understand these networks in detail, many generative models have been
proposed to artificially generate such networks. In a recent study Broido and
Clauset (2018) the authors test the universality of the scale-free structure
by applying different statistical tools to a large corpus of nearly 1000
network data sets drawn from social, biological, technological, and
informational sources. They observe that only 4% of real-world networks show
strong evidence of scale-free structure. Furthermore, they find that social
networks are at best weakly scale-free, while only a handful of technological
and biological networks can be called strongly scale-free.

There are several studies, e.g., Barabasi and Albert (1999); Berger et al.
(2004); Collevecchio et al. (2013); Cooper and Frieze (2003); Deijfen et al.
(2009); Lansky et al. (2014) to generate scale-free networks such that the
value of $\gamma\in[2,3]$. However, to the best of our knowledge, there has
been no work to generate weakly scale-free networks. We define a weakly scale-
free network as a network that has the power-law exponent $\gamma>$ 3 for
$k>k_{min}$ and a flattish distribution of degree of nodes for $k<k_{min}$. In
this paper, we aim to generate weakly scale-free networks with a two step
approach. In the first step, named node-step, a new node enters the network
and connects to an existing node using the preferential attachment method.
While in the second step, named edge-step, we iteratively add a certain number
of edges between existing nodes at random. This adds the desired flatness in
the network before $k_{min}$ and the generated network follows the scale-free
structure after $k_{min}$ with $\gamma>$ 3\. Two mechanisms for creating edges
are discussed. In the first mechanism, a fixed number of edges are created
during the edge-step and the resulting model generates weakly scale-free
network having the distribution satisfying the power-law with exponent
$\gamma\in(3,\infty)$ corresponding to this fixed number in the range
$[1,\infty)$. While in the second mechanism, the number of edges to be added
is proportional to the fraction of the total number of existing edges by the
number of nodes, we get $m(t)\propto t^{\beta}$ (see Appendix B). Moreover, we
choose $\beta>1$ to further investigate network evolution when a large number
of edges are added at random in each time step. The growth of the resultant
network is accelerated growth. We have found a non-stationary degree
distribution for this case. The average degree, in this case, is proportional
to $t^{\beta-1}$ and grows over time $t$.

For each method of adding edges, we have performed a fully detailed analysis
in the discrete domain ($k$ and $t$ as discrete variables). During the edge-
step, edges are added iteratively and we update the number of nodes marked by
degree $k$ after each iteration. A detailed formulation for each step derived
in this paper depicts the process fully. An exact recurrence relation is
formulated that models the network transition from one state to another. It
describes the change in degree distribution from the node-step to the edge-
step. It also models the transition from the state at the previous time stamp
to the next time stamp when both the node- and edge- steps have been
accomplished.

The idea of adding edges between existing nodes for the network evolution is
not a new one. The authors in the paper Dorogovtsev and Mendes (2000) extended
the Barabasi-Albert (BA) model and presented the undirected network evolution
based on this idea. They proposed the model in which a new incoming node
preferentially connects to $m$ existing nodes of the network. Then,
simultaneously $cm,c>0$ edges appear between existing nodes. The selection of
nodes for these new edges is also made preferentially. For a new edge, a pair
of nodes is selected with the probability proportional to the product of their
degrees. They used the continuous approximation (considering $t$ and $k$ as
continuous variables, Dorogovtsev and Mendes (2002b)) and found that the
degree-distribution satisfies the power-law $k^{-\gamma}$ with
$\gamma=2+\frac{1}{1+2c}$. This approach was proved to describe quite well the
degree distributions of networks growing under the mechanism of preferential
linking. Dorogovtsev and Mendes (2002b)) discussed another method of growing
directed networks through mixing preferential and random linking. A new vertex
with $n$ incoming edges enters the network, at each time step. The target ends
of $m$ new edges are simultaneously distributed among vertices through the
preferential linking rule. The probability to select a node is proportional to
$q+A$, with $q$ is the in-degree of the nodes and $A$ is a constant with value
$A>-n-n_{r}$. Besides, the target ends of $n_{r}$ new edges are attached to
randomly chosen vertices with source ends of each edge may be anywhere. The
in-degree $P(q)$ of these nodes satisfies the relation $q^{-\gamma}$ with
$\gamma=2+\frac{n_{r}+n+A}{m}$. These were kind of non-equilibrium growing
networks. The average degree for networks having the exponent $\gamma>2$ tends
to some constant value. The total degree of the network is a linear function
of the number of nodes at time $t$. When the average degree does not approach
a constant value but grows over time(total degree grows at least super-
linearly), these networks are called networks with accelerated
growthDorogovtsev and Mendes (2002c). In general, the total number of edges in
networks with accelerated growth is $m(t)\propto t^{\beta}$ for $\beta>1$. In
Dorogovtsev and Mendes (2002a) authors present a network with acceleration
growth in which $ct$ number of edges emerge among old vertices at each time
step. This behavior is found in the Internet, collaboration networks, the
World Wide Web, and many other networks.

The rest of the paper is organized as follows. In section 2, we present a two-
step model for generating weakly scale-free networks. In section 3, we provide
a comprehensive mathematical analysis of our model and drive recurrence
relation for both the node- and edge- steps. In section 4, we compare the
graphs generated by our model with real-world networks. In section 5, we
discuss related work and conclude the paper in section 6.

##  2 Weakly Scale-free Model

In this section, we formally present our model called Weakly Scale-free Model
(WSM). WSM generates undirected graphs and can be run for any period of time
$t(t>0)$, given an initiator graph at $t=0$, that could be any connected
graph, e.g., a connected triplet. We represent a network as an undirected
graph $G=(V,E)$ where $V$ is the set of nodes and $E$ is the set of edges. We
represent nodes in the graph as $\\{v_{1},v_{2},v_{3},...,v_{n}\\}$ and edges
as $\\{e_{1},e_{2},e_{3},...,e_{m}\\}$, furthermore, $|V|=n$ and $|E|=m$. In
this model, a network evolves over time and at any instant of time $t$, there
are $|V_{t}|=n_{t}$ nodes and $|E_{t}|=m_{t}$ edges in the network. Let
$G_{t}(V_{t},E_{t})$ be the graph at time $t$ . In a single time stamp, we
perform two steps namely node-step and edge-step.
Node Step: A new node $x$ arrives and connects to an existing node $y$ via one
edge such that

$n_{t+1}=n_{t}+1$ (1)

we call it the node equation. The probability $P_{y}$ of selecting node $y$ is
proportional to its degree $d_{y}$ i.e.,

$P_{y}=\frac{d_{y}}{\sum_{i=1}^{n}d_{i}}$ (2)

This equation suggests that a high degree node attracts more nodes and helps
the network to follow a power-law for its degree distribution.
Edge Step: In the edge-step, we add $\Delta m_{t}$ number of edges in the
network at each time stamp such that

$m_{t+1}={m_{t}}+\Delta m_{t}+1$ (3)

We call it the edge equation. Here, $+1$ corresponds to the edge added in the
node-step. We add edges between existing nodes at random. In order to add an
edge, we select two nodes $x$ and $y$ uniformly at random from the graph
$G_{t}$ and adds an edge between them. we repeat this process $\Delta m_{t}$
times. Here, $\Delta m_{t}$ is a natural number that can have any positive
values, $\Delta m_{t}\in[0,1,2,3,...]$. In other words, we add a fixed number
of edges in the edge-step. However, a formulation for the variable number of
edges is also presented in the appendix. To account for both of these two
cases, we used a more generic term $\Delta m_{t}$ to represent the number of
added edges during the edge-step. When $\Delta m_{t}=0$, our model generates a
standard Barabasi-Albert network and when $\Delta m_{t}>0$, we add random
links in the network and as a result we generate weakly scale-free networks.

##  3 Mathematical Analysis

In this section, we present the mathematical analysis of WSM in detail. For
analysis, let’s assume that the network starts with a single node at time
$t=1$. It grows over time through two steps, namely the node-step and edge-
step as described above. During the edge-step, $\Delta m_{t}$ number of edges
are created. For the creation of each edge, two nodes from the network are
selected according to the uniform probability distribution function. A
recurrence relation for degree distribution is formulated that incorporates
both node and edge steps and describes overall network evolution through time.

More formally, let $\\{v_{1},v_{2},v_{3},...,v_{n}\\}$ represents nodes in the
network and $\\{e_{1},e_{2},e_{3},...,e_{m}\\}$ edges. The network evolves
from a single node at time $t=1$. For ease of analysis, time $t$ also refers
to the total number of nodes in the network, i.e., at time $t$ there are a
total of $t$ nodes in the network. The degree of a node is represented as $k$.
The network evolves in two steps. In the first step, a new node is added that
connects with an existing node via one edge. In the second step, we add an
edge between two randomly selected nodes. This step is repeated until $\Delta
m_{t}$ new edges are created in the network. For creating edges, we consider a
simple scenario in which $\Delta m_{t}$ is a fixed positive integer $\alpha$.
Formulation keeps a record of the number of nodes of degree $k$ at each time
step $t$. $N_{k,t}$ is the number of nodes in a group marked by degree $k$ at
the completion of time step $t$. After the node-step, wherein $(t+1)$th node
connects to the network, number of nodes in the group becomes $N_{k,t+1,0}$.
$N_{k,t+1,l}$ represents nodes count of $k-th$ degree during the edge-step.
The subscript $l\in[1,\Delta m_{t}]$ tells that $l$ number of edges have been
added during the edge-step. The network state at the completion of both steps
is represented by $N_{k,t+1,\Delta m_{t}}$, which is also the initial
configuration $N_{k,t+1}$ for the next time step. The same process is repeated
for the next time step. To analyze the network behavior over time, the rank of
nodes marked by degree $k$, define as $P_{k,t}=\frac{N_{k,t}}{t}$, is more
helpful than just keeping a record of actual count of these nodes. $P_{k,t}$
represents fraction of nodes of degree $k$. Briefly, two consecutive stages
through which network grows, for each time step,

  1. 1.

(Node-step): At time $t+1$, $(t+1)$-th node arrives and connects to an member
node via one edge. The older node is picked with probability proportional to
its degree $k$.

  2. 2.

(Edge-step): At time $(t+1)$, after the node-step, two nodes are selected
randomly (with uniform probability) and an edge is created between them. This
step is repeated $\Delta m_{t}$ number of times. $\Delta m_{t}$ edges are
added during the edge-step.

First, we describe the model that incorporates the node-step only, and later
we extend it to include the edge-step.

###  3.1 The Standard BA Model

Our network is an undirected graph. In an undirected graph,
$\sum_{n=1}^{t}k_{n}=2m_{t}$ where $k_{n}$ is the degree of $n$-th node and
$m_{t}$ is the total number of edges in the graph at the completion of time
step $t$. In the case where network evolution does not include the edge-step,
it is described by the BA model. The network has $t-1$ edges at time step $t$.

The standard BA model gives following recurrence relation for the degree
distribution,

$P_{1}=\frac{2}{3}$ (4)

and

$P_{k}=P_{k-1}.\frac{k-1}{k+2}$ (5)

In a closed form,

$P_{k}=\frac{4}{k(k+1)(k+2)}\approx\frac{c}{k^{3}}~{}(\text{ for large
}k\text{'s})$ (6)

###  3.2 Edge Equation

In our work, the network configuration changes through two steps. First,
through the node-step when a new node is added to the network as described
above. Secondly, through the edge-step, when new edges are added between
existing pairs of nodes in the network. During the edge-step, we select two
nodes at random with uniform probability from the network and create an edge
between them. This step is repeated to add a total of $\Delta m_{t}$ number of
edges at the time step $t+1$. Following events may occur during the edge
creation:

  1. 1.

$E^{k,t+1,l}_{1}$ is the event that exactly one node is selected from the
group marked by the degree $k$. $p(E^{k,t+1,l}_{1})$ is the probability of
this event. The occurrence of this event reduces the population of nodes of
degree $k$ by 1.

  2. 2.

$E^{k,t+1,l}_{2}$ is the event that exactly two node are selected from the
group of nodes marked by the degree $k$. $p(E^{k,t+1,l}_{2})$ is the
probability of this event. The occurrence of this event reduces the population
of nodes of degree $k$ by 2.

  3. 3.

$E^{k-1,t+1,l}_{1}$ is the event that exactly one node is selected from the
group of nodes marked by the degree $k-1$. $p(E^{k-1,t+1,l}_{1})$ is the
probability of this event. The occurrence of this event increases the
population of nodes of degree $k$ by 1.

  4. 4.

$E^{k-1,t+1,l}_{2}$ is the event that exactly two nodes are selected from the
group of nodes marked by the degree $k-1$. $p(E^{k-1,t+1,l}_{2})$ is the
probability of this event.The occurrence of this event increases the
population of nodes of degree $k$ by 2.

$N_{k,t}$ describes the network state at the completion of time step $t$. Each
time step consists of the node-step and edge-step, in order. $N_{k,t}$ is also
the initial configuration for the next time step $t+1$. We call $N_{k,t+1,0}$
the expected number of nodes of degree $k$ after the completion of the node-
step and prior to the edge-step. The network at this stage has $t+1$ nodes.
$N_{k,t+1,1}$ be the expected number of nodes of degree $k$ after adding one
edge in the edge-step. The two network configurations could be related as, for
$k>1$,

$\displaystyle
N_{k,t+1,1}=N_{k,t+1,0}-1.p(E^{k,t+1,0}_{1})-2.p(E^{k,t+1,0}_{2})+1.p(E^{k-1,t+1,0}_{1})$
(7) $\displaystyle+2.p(E^{k-1,t+1,0}_{2})-0.p(E^{k-1,t+1,0}_{1}\cap
E^{k,t+1,0}_{1}).$

And, in general,

$\displaystyle
N_{k,t+1,l}=N_{k,t+1,l-1}-1.p(E^{k,t+1,l-1}_{1})-2.p(E^{k,t+1,l-1}_{2})+1.p(E^{k-1,t+1,l-1}_{1})$
(8) $\displaystyle+2.p(E^{k-1,t+1,l-1}_{2})-0.p(E^{k-1,t+1,l-1}_{1}\cap
E^{k,t+1,l-1}_{1}).$

For the sake of brevity, $N_{k,t+1,\Delta m_{t}}$ will be represented as
$N_{k,t+1}$.

Since, during the edge-step no node enters into the group marked by the degree
$1$, in the above relation (8) truncating terms involving $k-1$ and replacing
$k$ by $1$, we get following recurrence relation for $N_{1,t+,l}$,

$N_{1,t+1,l}=N_{1,t+1,l-1}-1.p(E^{1,t+1,l-1}_{1})-2.p(E^{1,t+1,l-1}_{2}).$ (9)

The total number of edges in the network varies during the node- and edge-
steps. At the completion of $t$-th time step when the $t$-th nodes is
connected to the network and $\alpha$ edges have been created, total number of
edges of the network are $m_{t}=(t-1)+\alpha(t-1)=(\alpha+1)(t-1)$. When
$(t+1)$th nodes arrives and connects, the number is increased by $1$, i.e.
$m_{t}+1$. And during the edge-step, when $l$ edges have been created, number
of edges become $m_{t}+1+l$. During edge creation, each node has equal chance
of selection.

$p(E^{k,t+1,l}_{1})=2\bigl{(}\frac{N_{k,t+1,l}}{t+1}\bigr{)}\bigl{(}\frac{t+1-N_{k,t+1,l}}{t}\bigr{)}=\frac{2(N_{k,t+1,l})(t+1-N_{k,t+1,l})}{t^{2}+t}$
(10)

and

$p(E^{k,t+1,l}_{2})=\bigl{(}\frac{N_{k,t+1,l}}{t+1}\bigr{)}\bigl{(}\frac{N_{k,t+1,l}-1}{t}\bigr{)}=\frac{({N_{k,t+1,l})}^{2}-N_{k,t+1,l}}{t^{2}+t}$
(11)

This probability formula is valid for all $l$’s and for all $k$’s. Next, we
formulate the edge- and node- steps.

Edge-step
For $k>1$,
Substituting probability functions given by (10) and (11) in (7) and
simplifying the expression, we get

$N_{k,t+1,1}=N_{k,t+1,0}+\frac{2}{t+1}[N_{k-1,t+1,0}-N_{k,t+1,0}].$

This relation describes addition of the first edge, i.e. $l=1$. Rewriting it
in the following form,

$N_{k,t+1,1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}N_{k,t+1,0}+\frac{2}{t+1}N_{k-1,t+1,0},$

Similarly for general $l$,

$N_{k,t+1,l}=\bigl{(}1-\frac{2}{t+1}\bigr{)}N_{k,t+1,l-1}+\frac{2}{t+1}N_{k-1,t+1,l-1}.$
(12)

For $k=1$

$N_{k,t+1,l}=\bigl{(}1-\frac{2}{t+1}\bigr{)}N_{k,t+1,l-1}.$ (13)

Node-step
The node step is carried through preferential attachment and is given by
following relationships,
For $k>1$,

$N_{k,t+1,0}=N_{k,t}+N_{k-1,t}\frac{k-1}{2m_{t}}-N_{k,t}\frac{k}{2m_{t}},$

or re-writing in the form

$N_{k,t+1,0}=\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}N_{k,t}+N_{k-1,t}\frac{k-1}{2m_{t}}.$
(14)

And for $k=1$

$N_{k,t+1,0}=\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}N_{k,t}+1$ (15)

###  3.3 Derivation of the Recurrence relation for $\Delta m_{t}=\alpha$

A general form of the recurrence relation describing the network evolution
through time, incorporating both the node- and edge- steps, is presented. (See
appendix A for the detailed formulation and derivation).

For $k=1$, the recurrence relations gives $P_{k,t+1}$ in term of $P_{k,t}$,

$(t+1)P_{k,t+1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{[}tP_{k,t}+1-\frac{k}{2m_{t}}tP_{k,t}\bigr{]}.$ (16)

For $k>1$, the recurrence relations gives $P_{k,t+1}$ in term of $P_{k-n,t}$’s
with $n=0,1,\dots$,

$(t+1)P_{k,t+1}=\sum_{n=0}^{q}tC_{k-n,\Delta m_{t}}P_{k-n,t}\\\ $ (17)

Coefficients $C_{k-n,\Delta m_{t}}$’s and $q$ are defined in the appendix A.

The stationary degree distribution for nodes is obtained on replacing $\Delta
m_{t}$ by $\alpha$ and applying the limit $t\to\infty$, .

For $k=1$

$P_{1}=\frac{2(\alpha+1)}{4\alpha^{2}+6\alpha+3}.$ (18)

In general, for $k>1$

$P_{k}=\frac{k+4\alpha^{2}+4\alpha-1}{k+4\alpha^{2}+6\alpha+2}P_{k-1}.$ (19)

$P_{k}$ can also be written in the closed form:

$P_{k}=\frac{(4\alpha^{2}+6\alpha+3)(4\alpha^{2}+6\alpha+2)\dots(4\alpha^{2}+4\alpha+1)}{(k+4\alpha^{2}+6\alpha+2)(k+4\alpha^{2}+6\alpha+1)\dots(k+4\alpha^{2}+4\alpha)}\frac{2(\alpha+1)}{4\alpha^{2}+6\alpha+3},$

or

$P_{k}=\frac{(4\alpha^{2}+6\alpha+2)\dots(4\alpha^{2}+4\alpha+1)}{(k+4\alpha^{2}+6\alpha+2)(k+4\alpha^{2}+6\alpha+1)\dots(k+4\alpha^{2}+4\alpha)}{2(\alpha+1)}.$
(20)

If $\alpha$ is replaced with $0$ in the equation (19), equation (5) is
obtained which is the recurrence relation when only the node-step is used.
Similarly, equation (18) reduces to equation (4). The degree distribution
$P_{k}$ follows the power-law $k^{-(2\alpha+3)}$, but only for very large
values of $k$. For large $\alpha$ and small $k$’s, distribution is almost
uniform, i.e., $P_{k}\approx P_{k-1}$. Also, the expression for $P_{1}$
approaches to $0$ as $\alpha$ becomes large and large. To prove the claim
about distribution slopes formally, let $\delta_{\alpha,k}\text{ for }k>1$
represents the slope of the $\log(P_{k})\text{ vs. }\log(k)$ graph, then

$\displaystyle\delta_{\alpha,k}=\frac{\log{P_{k}}-\log{P_{k-1}}}{\log{k}-\log{(k-1)}}=\frac{\log{(k+4\alpha^{2}+4\alpha-1)}-\log{(k+4\alpha^{2}+6\alpha+2)}}{\log{k}-\log{(k-1)}}$
(21)
$\displaystyle=\frac{\log{({1-\frac{2\alpha+3}{k+4\alpha^{2}+6\alpha+2}})}}{\log{(1+\frac{1}{k-1}})}$

For further analysis, let’s expand $\log$ terms to the first order,

$\delta_{\alpha,k}\approx-\frac{(2\alpha+3)(k-1)}{k+4\alpha^{2}+6\alpha+2}.$

Now, as $\alpha$ is a fixed constant value, for very large $k$, say, $k\gg
4\alpha^{2}+6\alpha+2$, expression becomes,

$\delta_{\alpha,k}\approx-\frac{(2\alpha+3)(k-1)}{k}\approx-(2\alpha+3).$ (22)

For small $k$’s, we get,

$\delta_{\alpha,k}\approx-\frac{(2\alpha+3)(k-1)}{4\alpha^{2}+6\alpha+2}\approx-\epsilon(k-1)$
(23)

where $\epsilon$ very small positive quantity of order
$\mathcal{O}(\frac{1}{\alpha})$. Informally, in the beginning when $k$ is
small, slope is very small.

We compare theoretical equations and practical results in Figure 1. For
theoretical results, we implement equation 19 for different values of
$\alpha=1,3,5$. For practical results, we implement the node- and edge- steps
of the WS model. We draw the degree of nodes again their frequency. We see in
Figure 1 that both the graphs overlap and this proves the correctness of our
mathematical analysis.

Figure 1: Theoretical vs. Practical Degree Distribution for $\alpha=1,3,5$

##  4 Experimental Results

In this section, we provide an overview of real datasets or graphs that we
will use for comparison with the networks generated by our model. All the real
networks are publicly available at KONECT (2017). We use the following six
citation networks, two peer-to-peer networks and four social networks. An
overview of these datasets is available in Table 1.

  * •

DBLP: This is the citation network of DBLP, a database of scientific
publications such as papers and books. Each node in the network is a
publication, and each edge represents a citation of a publication by another
publication.

  * •

HepTh: This is a citation network of authors of scientific papers from the
arXiv’s High Energy Physics (Theory) section.

  * •

Cora: This is the cora citation network. Nodes represent scientific papers. An
edge between two nodes indicates that the one node cites the other node.

  * •

HepPh: This is a citation network of scientific papers from the arXiv’s High
Energy Physics (Phenomenology) section.

  * •

CiteSeer: This is the citation network extracted from the CiteSeer digital
library. Nodes are publications and the edges denote citations.

  * •

Patents: This is the citation network of patents registered with the United
States Patent and Trademark Office. Each node is a patent and an edge
represents a citation.

  * •

Gnutella1: This is a network of Gnutella hosts from 2002. The nodes represent
Gnutella hosts, and the edges represent connections between them.

  * •

Gnutella2: This is a network of Gnutella hosts from 2002. The nodes represent
Gnutella hosts and the edges represent connections between them.

  * •

Facebook: This is a friendship network of facebook. The nodes are users and an
edge between two users shows a friendship relation between them.

  * •

Prosperloans: These are loans between users of the Prosper.com website. The
network denotes who loaned money to whom.

  * •

Amazon: This is the network of items on Amazon that have been mentioned by
Amazon’s ”People who bought X also bought Y” function. Nodes in the network
are products, and an edge from A to B denotes that product A is frequently co-
purchased with product B.

  * •

Pokec: This is the friendship network from the Slovak social network Pokec.
Nodes are users of Pokec and directed edges represent friendships.

For comparison, we compare our model with the standard Barabasi–Albert Model
Barabasi and Albert (1999). The Barabasi–Albert (BA) Model is a method for
generating scale-free networks using a preferential attachment mechanism.
Since our model also applies preferential attachment mechanism so it would be
interesting to compare it with the basic BA Model. In the very basic form of
the BA Model, the network begins with a small connected network of $w_{0}$
nodes. New nodes are added one-by-one at each time stamp and connect to
$w<w_{0}$ existing nodes with a probability that is proportional to the number
of links that the existing nodes already have. In our implementation, we start
with a small connected network and connect the new nodes with $w$ number of
existing nodes using the preferential attachment method described in Barabasi
and Albert (1999) where the value of $w$ is adjusted such that the resulting
graph has nearly the same number of edges as that of an original graph.

Table 1: Real-world datasets used in the experiments Datasets |  Total Nodes |  Total Edges |  Value of $\alpha$ (see section 4)
---|---|---|---
DBLP |  12,591 |  49,620 |  4
HepTh |  22,908 |  2,444,798 |  106
Cora |  23,166 |  89,157 |  4
HepPh |  28,093 |  3,148,447 |  112
CiteSeer |  384,413 |  1,736,145 |  4
Patents |  3,774,768 |  16,518,947 |  4
Gnutella1 |  36,682 |  88,328 |  2
Gnutella2 |  62,586 |  147,892 |  2
Facebook |  63,731 |  817,035 |  12
Prosperloans |  89,269 |  3,330,022 |  237
Amazon |  403,394 |  2,443,408 |  6
Pokec |  1,632,803 |  22,301,964 |  13

We implement our model and generate networks corresponding to each real-
network of Table 1. We set the value of $\Delta m_{t}=\alpha$ such that we
have nearly the same number of edges in our network as that of in the original
graph. It would be interesting to mention that if we apply the formula
$m_{t}=(\alpha+1)(t-1)$ to find $\alpha$, where, $t$ is the number of nodes
and $m_{t}$ is the number of edges, then the number of nodes and edges will be
same for theoretical and practical networks. We generate networks and plot the
Cumulative Distribution Function (CDF) of the degree of the original networks
along with the networks generated by our model and Barrabasi-Albert model. The
results are presented in Figure 2. First, these real-networks do not strictly
follow the power-law degree distribution as clear from the initial part of the
curve for small degree nodes. Second, we see that our model fits better than
the BA model as we follow the distribution curve more than the BA model. It
shows that we need to add some randomness in the graph for generating a weakly
scale-free network. However, we believe that this randomness should be limited
so that the degree distribution of the generated graph follows the original
graph more precisely.

We apply the method presented in Clauset et al. (2009) and give the values of
power-law exponent and $k_{min}$ of original and generated graphs in Table 2.
We also calculate the slope before $k_{min}$ for the original and generated
graphs of WSM. We see that $\gamma>$ 3 for all the networks. It has already
been observed in Ortuño et al. (2011); Brzezinski (2015) that $\gamma$ for
citation networks fall in the range [3, 4], i.e., $\gamma\in$ [3,4] for
citation networks. The table shows that $\gamma$ is almost equal to 3 for all
the networks for the BA model whereas WSM can generate networks with varying
values of $\gamma$.

The degree distribution over logarithm scales ($\log(N_{k,t})~{}\text{ versus
}\log(k)$) of chosen weakly scale-free networks starts with small slope (in
magnitude) for low-degree nodes and becomes more and more sharp for high-
degree nodes. After a particular degree value, say $k_{min}$, the distribution
almost acquires a fixed sharp slope. Our model for a small choice of $\alpha$,
generates weakly scale-free networks and the distribution given by the
proposed model behaves similarly. The model gives degree distribution starting
with a small slope, which becomes sharper, until at the $k_{min}(\alpha)$, it
almost acquires a sharp fixed slope $-(2\alpha+3)$. Slope variation of the
distribution is depicted in the Figure 3. In the beginning, the slope is small
(in magnitude), which gradually becomes sharper and finally acquires the fixed
value of $-9$. The BA model does not fit the first portion of the curve
corresponding to low degrees. This initial section of the distribution is more
uniform and cannot be obtained through preferential attachment alone. One
possible solution to obtain this uniformity lies in blending randomness to
preferential attachment, which can be obtained through the edge-step described
in the model. When we apply the edge-step to the network which initially
follows the power-law distribution, there is a high probability of nodes being
chosen from groups marked by low degrees (see Figure 4). This is because each
node has the same probability of selection and low-degree nodes are more in
number. As a result, these chosen nodes will move into the next higher degree
node group, increasing the rank of next higher-degree nodes and making the
degree distribution more uniform. The portion of the curve which tends to have
uniform distribution depends on the number $\alpha$. When ’$\alpha$’
increases, $k_{min}$ shifts towards the right and the slope of portion after
$k_{min}$ sharpens more, while the first portion characterized by flatness
stretches rightwards. For generating these networks, the value of $\alpha$ is
chosen as a small integer fixed for all time steps. Constant value gives the
desired result and makes the formulation simple. A larger value makes a larger
portion of the degree distribution uniform. So, choosing an appropriate value
of $\alpha$ is desired.

Figure 2: Degree distribution of generated and original graphs. The value of $\alpha$ used for each dataset is given in the last column of Table 1. Table 2: Values of power-law exponent $\gamma$ and $k_{min}$ of original and generated graphs. Dataset | Original | WSM | BA
---|---|---|---
$\gamma$ |  $k_{min}$ |  Slope before $k_{min}$ |  $\gamma$ |  $k_{min}$ |  Slope before $k_{min}$ |  $\gamma$ |  $k_{min}$
DBLP |  3.35 |  25 |  1.14 |  5.23 |  22 |  1.12 |  2.97 |  11
HepTh |  3.41 |  1244 |  0.97 |  5.46 |  895 |  0.77 |  2.95 |  109
Cora |  3.32 |  30 |  1.48 |  7.58 |  32 |  1.57 |  3.01 |  11
HepPh |  4.04 |  3226 |  0.91 |  5.48 |  953 |  0.72 |  2.96 |  111
CiteSeer |  3.05 |  74 |  1.95 |  7.47 |  51 |  1.75 |  3.07 |  19
Patents |  4.01 |  49 |  1.71 |  6.97 |  47 |  1.66 |  3.09 |  29
Gnutella1 |  4.92 |  11 |  1.44 |  5.89 |  18 |  1.39 |  3.32 |  15
Gnutella2 |  4.82 |  13 |  1.12 |  7.28 |  24 |  1.23 |  3.25 |  14
Facebook |  4.39 |  157 |  1.35 |  6.56 |  112 |  1.27 |  2.99 |  38
Pros.loans |  3.07 |  445 |  1.08 |  5.91 |  323 |  1.15 |  2.97 |  61
Amazon |  3.39 |  53 |  0.89 |  7.01 |  66 |  1.05 |  3.06 |  31
Pokec |  5.06 |  291 |  0.77 |  6.84 |  144 |  0.53 |  3.03 |  73
Figure 3: Model generated slopes for $\alpha=3$. Settling slope for
($\log(P_{k})~{}\text{ versus }\log(k)$) distribution is $-9$.  Figure 4:
Network is evolved using BA model first and then different number of edges
edges added using the edge-step. Number of nodes used are $10000$. A portion
of the graph is truncated. Graph marked by $0$, shows the distribution
obtained by BA model. Graphs marked by $2000$, $4000$ and $8000$ are
distributions obtained through adding different number of edges. Addition of
edges flattens the first part of the degree
distribution.($\log(P_{k})~{}\text{ versus }\log(k)$) distribution.

###  4.1 Discussion

We have implemented a two step approach to network evolution. The preferential
attachment used in the node-step tends to make the nodes distribution follow
the power-law. The edge creation probability function gives uniform
probability to each node, which tends the network to acquire uniform degree
distribution, especially the portion for low-degree nodes. In the case when
$\Delta m_{t}$ varies during each time step $t$, the edge-step dominates the
node-step and the distribution becomes uniform, implying that the network is
no longer a scale-free network, rather, is a random network. We see in Figure
2 that our model closely follows the original networks, better than the BA
model but not perfectly. We argue that our model fits the overall trend of the
degree distribution, however, it needs tweaking for matching the fine details
of a distribution. In the future, we would like to invest in this direction
and also consider other metrics for comparing our model with the real
networks.

##  5 Related Work

There have been many studies H. Strogatz (2001); Broder et al. (2000); Vazquez
et al. (2002); Amaral et al. (2000); Newman (2001); Ahn et al. (2007); Mislove
et al. (2007); Golder et al. (2007); Kumar et al. (2006) to explore the
structure of complex online networks. For example, the authors in Ahn et al.
(2007); Mislove et al. (2007) study the properties of real networks by
analyzing large scale Online Social Networks (OSNs) and discover link
symmetries, scale-free degree distributions, clustering phenomena, and
community formations. Golder et al. Golder et al. (2007) analyze the Facebook
network by studying the messaging pattern between friends and report that the
degree distribution of the Facebook network follows a power-law. Kumar et al.
Kumar et al. (2006) study the structure and dynamics of Online Social Networks
over time and proposes a generative model for OSNs. However, a very recent
study Broido and Clauset (2018) analyzes many real-world networks and
concludes that scale-free networks are rare and only a small number of real-
world graphs follow a power-law degree distribution. The study also finds that
a majority of real networks are weakly scale-free. In Dorogovtsev and Mendes
(2002b) authors presented a method of growing directed networks through mixing
preferential and random linking. Preferential linking is used to connect a new
node to the network. Then, the edges emerge in the network and nodes for these
edges are chosen through the preferential attachment method. In the last step,
the edges are created with end-nodes selected at random.

Generative models for complex networks produce graphs that typically satisfy
the scale-free degree distribution. For example, the preferential attachment
model Barabasi and Albert (1999), one of the best-known models for scale-free
networks, simulates this property. Real-world modeling instances motivated the
proposal of generalizations of the preferential attachment model, e.g., Berger
et al. (2004); Collevecchio et al. (2013); Cooper and Frieze (2003); Deijfen
et al. (2009); Krapivsky et al. (2000); Lansky et al. (2014, 2016); Ostroumova
et al. (2013); Rudas et al. (2007); Dorogovtsev et al. (2000); Pachón et al.
(2016); Albert and Barabási (2000). A common characteristic of many of these
models is the presence of the same attachment rule for all the nodes of the
network. However, this hypothesis is not always realistic and the graphs
generated by these models do not follow a weakly scale-free degree
distribution. In Magner et al. (2014), Magner et al. introduced a model in
which new vertices choose the nodes for their links within time-based windows.
Inspired by the idea of introducing windows, the authors in Pachón et al.
(2017) formulate their idea. They apply the preferential attachment rule to
any node but re-enforce this rule with a uniform choice for the most recent
nodes added to the network.

##  6 Conclusion

In this paper, we propose a generative model for generating weakly scale-free
networks. The model generated degree distribution is similar in trend with
real network data for the whole range of degree values $k>0$. We provide a
comprehensive mathematical analysis of the model in the discrete domain. We
compare the model with real networks and find that our graphs closely match
with the original graphs in their degree distribution.

## References

  * Ahn et al. (2007) Y.-Y. Ahn, S. Han, H. Kwak, S. Moon, and H. Jeong.  Analysis of topological characteristics of huge online social networking services.  In _Proceedings of the 16th International Conference on World Wide Web_ , WWW ’07, pages 835–844, 2007.
  * Albert and Barabási (2000) R. Albert and A.-L. Barabási.  Topology of evolving networks: Local events and universality.  _Physical Review Letters_ , 85:5234–5237, 2000.
  * Amaral et al. (2000) L. A. N. Amaral, A. Scala, M. Barthélémy, and H. E. Stanley.  Classes of small-world networks.  _Proceedings of the National Academy of Sciences_ , 97(21):11149–11152, 2000.
  * Barabasi and Albert (1999) A.-L. Barabasi and R. Albert.  Emergence of scaling in random networks.  _Science_ , 286(5439):509–512, 1999.
  * Berger et al. (2004) N. Berger, C. Borgs, J. T. Chayes, R. M. D’Souza, and R. D. Kleinberg.  Competition-induced preferential attachment.  In _Automata, Languages and Programming_ , pages 208–221, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg.
  * Broder et al. (2000) A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener.  Graph structure in the web.  In _Proceedings of the 9th International World Wide Web Conference on Computer Networks : The International Journal of Computer and Telecommunications Netowrking_ , pages 309–320, 2000.
  * Broido and Clauset (2018) A. D. Broido and A. Clauset.  Scale-free Networks are Rare, 2018.
  * Brzezinski (2015) M. Brzezinski.  Power laws in citation distributions: evidence from Scopus.  _Scientometrics_ , 103(1):213–228, April 2015\.
  * Clauset et al. (2009) A. Clauset, C. R. Shalizi, and M. E. J. Newman.  Power-law distributions in empirical data.  _SIAM Review_ , 51(4):661–703, 2009.
  * Collevecchio et al. (2013) A. Collevecchio, C. Cotar, and M. LiCalzi.  On a preferential attachment and generalized pÓlya’s urn model.  _The Annals of Applied Probability_ , 23(3):1219–1253, 2013.
  * Cooper and Frieze (2003) C. Cooper and A. Frieze.  A general model of web graphs.  _Random Struct. Algorithms_ , 22(3):311–335, May 2003.  ISSN 1042-9832.
  * Deijfen et al. (2009) M. Deijfen, H. van den Esker, R. van der Hofstad, and G. Hooghiemstra.  A preferential attachment model with random initial degrees.  _Arkiv för Matematik_ , 47(1):41–72, Apr 2009\.
  * Dorogovtsev and Mendes (2002a) S. Dorogovtsev and J. F. Mendes.  Language as an evolving word web.  _Proceedings. Biological sciences / The Royal Society_ , 268:2603–6, 01 2002a.
  * Dorogovtsev and Mendes (2002b) S. Dorogovtsev and J. F. Mendes.  Evolution of networks.  _Advances In Physics_ , 51:1079–1187, 06 2002b.
  * Dorogovtsev et al. (2000) S. Dorogovtsev, J. F. Mendes, and A. N Samukhin.  Structure of growing networks with preferential linking.  _Physical review letters_ , 85:4633–6, 11 2000.
  * Dorogovtsev and Mendes (2000) S. N. Dorogovtsev and J. F. F. Mendes.  Scaling behaviour of developing and decaying networks.  _Europhysics Letters (EPL)_ , 52(1):33–39, oct 2000.
  * Dorogovtsev and Mendes (2002c) S. N. Dorogovtsev and J. F. F. Mendes.  Accelerated growth of networks.  _CoRR_ , cond-mat/0204102, 2002c.
  * Golder et al. (2007) S. A. Golder, D. M. Wilkinson, and B. A. Huberman.  _Rhythms of Social Interaction: Messaging Within a Massive Online Network_ , pages 41–66.  Springer London, London, 2007.
  * H. Strogatz (2001) S. H. Strogatz.  Exploring complex networks.  _Nature, International Journal of Science_ , 410, 03 2001.
  * KONECT (2017) KONECT.  The Koblenz Network Collection - KONECT, Apr. 2017.  URL http://konect.uni-koblenz.de/networks/.
  * Krapivsky et al. (2000) P. L. Krapivsky, S. Redner, and F. Leyvraz.  Connectivity of growing random networks.  _Phys. Rev. Lett._ , 85:4629–4632, Nov 2000.
  * Kumar et al. (2006) R. Kumar, J. Novak, and A. Tomkins.  Structure and evolution of online social networks.  In _Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’06, pages 611–617, 2006.
  * Lansky et al. (2014) P. Lansky, F. Polito, and L. Sacerdote.  The role of detachment of in-links in scale-free networks.  _Journal of Physics A: Mathematical and Theoretical_ , 47(34), aug 2014.
  * Lansky et al. (2016) P. Lansky, F. Polito, and L. Sacerdote.  Generalized nonlinear yule models.  _Journal of Statistical Physics_ , 165(3):661–679, Nov 2016.
  * Magner et al. (2014) A. Magner, S. Janson, G. Kollias, and W. Szpankowski.  On symmetry of uniform and preferential attachment graphs.  _The Electronic Journal of Combinatorics [electronic only]_ , 21, 08 2014.
  * Mislove et al. (2007) A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee.  Measurement and analysis of online social networks.  In _Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement_ , IMC ’07, pages 29–42, 2007.
  * Newman (2001) M. E. J. Newman.  The structure of scientific collaboration networks.  _Proceedings of the National Academy of Sciences_ , 98(2):404–409, 2001.
  * Ortuño et al. (2011) I. Ortuño, J. A. Crespo, P. Albarrán, and J. Ruiz-Castillo.  The skewness of science in 219 sub-fields and a number of aggregates.  UC3M Working papers. Economics we1109, Universidad Carlos III de Madrid. Departamento de Economía, May 2011.  URL https://ideas.repec.org/p/cte/werepe/we1109.html.
  * Ostroumova et al. (2013) L. Ostroumova, A. Ryabchenko, and E. Samosvat.  Generalized preferential attachment: Tunable power-law degree distribution and clustering coefficient.  In _Algorithms and Models for the Web Graph_ , pages 185–202, Cham, 2013. Springer International Publishing.
  * Pachón et al. (2016) A. Pachón, F. Polito, and L. Sacerdote.  Random graphs associated to some discrete and continuous time preferential attachment models.  _Journal of Statistical Physics_ , 162:1608–1638, 03 2016\.  10.1007/s10955-016-1462-7.
  * Pachón et al. (2017) A. Pachón, L. Sacerdote, and S. Yang.  Scale-free behavior of networks with the copresence of preferential and uniform attachment rules.  _Physica D: Nonlinear Phenomena_ , 04 2017.  10.1016/j.physd.2018.01.005.
  * Rudas et al. (2007) A. Rudas, B. Tóth, and B. Valkó.  Random trees and general branching processes.  _Random Structures & Algorithms_, 31(2):186–202, 2007.
  * Vazquez et al. (2002) A. Vazquez, R. Pastor-Satorras, and A. Vespignani.  Large-scale topological and dynamical properties of the internet.  _Physical review. E, Statistical, nonlinear, and soft matter physics_ , 65, 07 2002.

##  Appendix A General form of Recurrence Relation for degree distribution

A general form of the recurrence relation for degree distribution will be
derived here. Recurrence formula writes $P_{k,t+1}$, rank of nodes of degree
$k$ at time $t+1$, in terms of $P_{h,t}$ for $h=k,k-1,\dots$. Network
evolution is based on both the node- and edge- steps. The formulation is valid
whether $\Delta m_{t}$ is constant for all time steps or varies by the rule
(given in B).

The relation for $k=1$.

Using Equation (13) repeatedly for $l=1,2,\dots,\Delta m_{t}$, we get

$\begin{split}N_{k,t+1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}N_{k,t+1,0}.\end{split}$

Now using the equation (15), $N_{k,t+1}$ after the execution of the node and
edge-step:

$N_{k,t+1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{[}\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}N_{k,t}+1\bigr{]},$

and writing the equation in terms of ranks $P_{k,t}$’s, following form is
obtained

$(t+1)P_{k,t+1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{[}tP_{k,t}+1-\frac{k}{2m_{t}}tP_{k,t}\bigr{]}.$ (A.1)

The derivation of recurrence relation for $k>1$.
We will write general form of the recurrence relation for $k>1$. Let
$\Phi=\frac{2}{t+1}$ and $\Psi=1-\frac{2}{t+1}$.

Then rewriting the recurrence relation (12), for for $l=1$ and general $l$, in
the following form:

$\begin{split}&N_{k,t+1,1}=\Psi N_{k,t+1,0}+\Phi N_{k-1,t+1,0},\\\
&N_{k,t+1,l}=\Psi N_{k,t+1,l-1}+\Phi N_{k-1,t+1,l-1}.\end{split}$

Next we will write $N_{k,t+1,l}$ in terms of $N_{h,t+1,0}$ for
$h=k,k-1,\dots,k-l$

$\begin{split}&N_{k,t+1,2}=\Psi N_{k,t+1,1}+\Phi N_{k-1,t+1,1}\text{, for
}k\geq 2,\\\ &N_{k,t+1,2}=\Psi^{2}N_{k,t+1,0}+2\Psi\Phi
N_{k-1,t+1,0}+\Phi^{2}N_{k-2,t+1,0}\text{, for }k\geq 3,\\\
&N_{k,t+1,3}=\Psi^{3}N_{k,t+1,0}+3\Psi^{2}\Phi
N_{k-1,t+1,0}+3\Psi\Phi^{2}N_{k-2,t+1,0}+\Phi^{3}N_{k-3,t+1,0}\text{, for
}k\geq 4.\end{split}$

Define $q=\min(k-1,\Delta m_{t})$ and write $N_{k,t+1}$ in a brief form,

$N_{k,t+1}=\sum_{n=0}^{q}C_{k-n,\Delta m_{t}}^{{}^{\prime}}N_{k-n,t+1,0}.$

Now, using the relation (14)

$N_{k,t+1,0}=\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}N_{k,t}+N_{k-1,t}\frac{k-1}{2m_{t}},$

we get $N_{k,t+1}$ in terms of $N_{k-n,t}$’s which represent network
configuration at previous sampling time.

$\begin{split}N_{k,t+1}=\sum_{n=0}^{q}C_{k-n,\Delta
m_{t}}^{{}^{\prime}}\bigl{(}1-\frac{k-n}{2m_{t}}\bigr{)}N_{k-n,t}+\sum_{n=0}^{q-1}C_{k-n,\Delta
m_{t}}^{{}^{\prime}}\frac{k-n-1}{2m_{t}}N_{k-n-1,t}\\\ +\bigl{[}C_{k-q,\Delta
m_{t}}^{{}^{\prime}}\frac{k-q-1}{2m_{t}}N_{k-q-1,t}\bigr{]}.\end{split}$

Last term in square brackets occurs only when $q=\Delta m_{t}<k-1$. During the
application of the limit, $\lim t\to\infty$, this situation can occur only
when $\Delta m_{t}$ is a fixed number. In the other case, where $\Delta m_{t}$
varies, $\Delta m_{t}\to\infty$, this term does not appear in the recurrence
relation. Simplifying further,we get

$\begin{split}N_{k,t+1}&=C_{k,\Delta
m_{t}}^{{}^{\prime}}\bigl{(}1-\frac{k-n}{2m_{t}}\bigr{)}N_{k,t}+\sum_{n=1}^{q}C_{k-n,\Delta
m_{t}}^{{}^{\prime}}\bigl{(}1-\frac{k-n}{2m_{t}}\bigr{)}N_{k-n,t},\\\
&=\sum_{n=0}^{q-1}C_{k-n,\Delta
m_{t}}^{{}^{\prime}}\frac{k-n-1}{2m_{t}}N_{k-n-1,t}+C_{k-q,\Delta
m_{t}}^{{}^{\prime}}\frac{k-q-1}{2m_{t}}N_{k-q-1,t}.\end{split}$

$\begin{split}\implies N_{k,t+1}=\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}C_{k,\Delta
m_{t}}^{{}^{\prime}}N_{k,t}+\sum_{n=1}^{q}\bigl{[}\bigl{(}1-\frac{k-n}{2m_{t}}\bigr{)}C_{k-n,\Delta
m_{t}}^{{}^{\prime}}+\frac{k-n}{2m_{t}}C_{k-n+1,\Delta
m_{t}}^{{}^{\prime}}\bigr{]}N_{k-n,t}\\\ +\bigl{[}\frac{k-\Delta
m_{t}-1}{2m_{t}}C_{k-\Delta m_{t},\Delta m_{t}}^{{}^{\prime}}N_{k-\Delta
m_{t}-1}\bigr{]}.\end{split}$

Using the relation $P_{k,t}=\frac{N_{k,t}}{t}$,we get

$\begin{split}(t+1)P_{k,t+1}=\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}C_{k,\Delta
m_{t}}^{{}^{\prime}}tP_{k,t}+\sum_{n=1}^{q}\bigl{[}\bigl{(}1-\frac{k-n}{2m_{t}}\bigr{)}C_{k-n,\Delta
m_{t}}^{{}^{\prime}}+\frac{k-n}{2m_{t}}C_{k-n+1,\Delta
m_{t}}^{{}^{\prime}}\bigr{]}tP_{k-n,t}\\\ +\frac{k-\Delta
m_{t}-1}{2m_{t}}C_{k-\Delta m_{t},\Delta m_{t}}^{{}^{\prime}}tP_{k-\Delta
m_{t}-1}.\end{split}$

In the brief form,

$(t+1)P_{k,t+1}=\sum_{n=0}^{q}tC_{k-n,\Delta m_{t}}P_{k-n,t},$ (A.2)

where coefficients $C_{k-n,\Delta m_{t}}$ are defined as
for $n=0$, we get

$C_{k,\Delta m_{t}}=\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}C_{k,\Delta
m_{t}}^{{}^{\prime}}.$

For $1<n\leq q$, expression becomes as:

$C_{k-n,\Delta m_{t}}=\bigl{(}1-\frac{k-n}{2m_{t}}\bigr{)}C_{k-n,\Delta
m_{t}}^{{}^{\prime}}+\frac{k-n}{2m_{t}}C_{k-n+1,\Delta m_{t}}^{{}^{\prime}},$

and if $\Delta m_{t}<k-1$, we get

$C_{k-\Delta m_{t},\Delta m_{t}}=\frac{k-\Delta m_{t}-1}{2m_{t}}C_{k-\Delta
m_{t},\Delta m_{t}}^{{}^{\prime}}.$

Next we derive formulas for $C_{k-n,l}^{{}^{\prime}}$’s and $C_{k-n,l}$’s.
Key observations: Before deriving exact form of these coefficients, we list
few key points about these coefficients.

$C_{k,l}^{{}^{\prime}}=\Psi C_{k,l-1}^{{}^{\prime}}\text{ for }l=1,2,\dots.$

It can be seen that $C_{k-n,l}^{{}^{\prime}}\text{ for }n=1,2,\dots$ term
appears first time in the expression after the addition of $l=n$ edges. For
$l<n,~{}~{}C_{k-n,l}=0$. Putting in the mathematical form, for $n=1,2...$ and
$n<k$,

$\begin{split}&C_{k-n,l}^{{}^{\prime}}=0,\text{ for }l<n,\\\
&C_{k-n,n}^{{}^{\prime}}=\Phi^{n}.\\\ \end{split}$

Recurrence relation for coefficients is

$C_{k-n,l}^{{}^{\prime}}=\Psi C_{k-n,l-1}^{{}^{\prime}}+\Phi
C_{k-n+1,l-1}^{{}^{\prime}}\text{ for }l>n.$ (A.3)

Now we derive exact form of each coefficient $C_{k-n,\Delta m_{t}}\text{ for
}n=0,1,2,\dots$
$\bm{C_{k,\Delta m_{t}}}$

$\begin{split}C_{k,l}^{{}^{\prime}}=\Psi^{l}\text{ for }l=1,2,...,\Delta
m_{t},\\\ \end{split}$

$\implies C_{k,\Delta
m_{t}}=\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}.$ (A.4)

$\bm{C_{k-1,\Delta m_{t}}\text{ for }k>1}$

$\begin{split}C_{k-1,\Delta
m_{t}}=\bigl{(}1-\frac{k-1}{2m_{t}}\bigr{)}C_{k-1,\Delta
m_{t}}^{{}^{\prime}}+\frac{k-1}{2m_{t}}C_{k,\Delta m_{t}}^{{}^{\prime}}.\\\
\end{split}$

First we find an expression for $C_{k-1,\Delta m_{t}}^{{}^{\prime}}$.

$\begin{split}&C_{k-1,l}^{{}^{\prime}}=b_{l}^{k-1}\Psi^{l-1}\Phi\text{ with
}b_{l}^{k-1}=l,\text{ for }l=1,2,...,\Delta m_{t},\text{ using the relation
\ref{CoeefRecurr}}\\\ \implies&C_{k-1,\Delta m_{t}}^{{}^{\prime}}=\Delta
m_{t}\Psi^{\Delta m_{t}-1}\Phi,\\\ \implies&C_{k-1,\Delta
m_{t}}=\bigl{(}1-\frac{k-1}{2m_{t}}\bigr{)}\Delta m_{t}\Psi^{\Delta
m_{t}-1}\Phi+\frac{k-1}{2m_{t}}\Psi^{\Delta m_{t}}.\\\ \end{split}$

Finally,

$C_{k-1,\Delta m_{t}}=\bigl{(}1-\frac{k-1}{2m_{t}}\bigr{)}\Delta
m_{t}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}-1}\frac{2}{t+1}+\frac{k-1}{2m_{t}}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}.\\\ $ (A.5)

$\bm{C_{k-2,\Delta m_{t}}\text{ for }k>2}$

$C_{k-2,\Delta m_{t}}=\bigl{(}1-\frac{k-2}{2m_{t}}\bigr{)}C_{k-2,\Delta
m_{t}}^{{}^{\prime}}+\frac{k-2}{2m_{t}}C_{k-1,\Delta m_{t}}^{{}^{\prime}},\\\
$

$\begin{split}&C_{k-2,1}^{{}^{\prime}}=0,C_{k-2,l}^{{}^{\prime}}=b_{l}^{k-2}\Psi^{l-2}\Phi^{2}\text{
for }l=2,3,....\Delta m_{t},\\\ \text{with
}&b_{2}^{k-2}=1,~{}~{}b_{l+1}^{k-2}=b_{l}^{k-2}+b_{l}^{k-1}\text{ for
}l=2,3,\dots,\text{ using the relation \ref{CoeefRecurr}}.\\\ \\\
\implies&b_{l+1}^{k-2}=b_{l}^{k-2}+l\text{ for }l=2,3,\dots\\\
\implies&b_{l}^{k-2}=\frac{l(l-1)}{2},\\\ \text{Now
}&C_{k-2,l}^{{}^{\prime}}=\frac{l(l-1)}{2}\Psi^{l-2}\Phi^{2}\text{ for
}l=2,3,\dots\Delta m_{t},\\\ \implies&C_{k-2,\Delta
m_{t}}^{{}^{\prime}}=\frac{\Delta m_{t}(\Delta m_{t}-1)}{2}\Psi^{\Delta
m_{t}-2}\Phi^{2}.\end{split}$

Finally we get,

$C_{k-2,\Delta m_{t}}=\bigl{(}1-\frac{k-2}{2m_{t}}\bigr{)}C_{k-2,\Delta
m_{t}}^{{}^{\prime}}+\frac{k-2}{2m_{t}}C_{k-1,\Delta m_{t}}^{{}^{\prime}}.\\\
$ (A.6)

$\bm{C_{k-n,\Delta m_{t}}\text{ for }k>n,\text{ for }n=3,4...}$

$C_{k-n,\Delta m_{t}}^{{}^{\prime}}=b_{\Delta m_{t}}^{k-n}\Psi^{\Delta
m_{t}-n}\Phi^{n}.$ (A.7)

Determination of orders of these terms is sufficient. $b_{\Delta m_{t}}^{k-n}$
is of $\mathcal{O}({\Delta m_{t}}^{n})$. Order of $C_{k-n,\Delta m_{t}}$ and
$C_{k-n,\Delta m_{t}}^{{}^{\prime}}$ are the same. Order of $C_{k-n,\Delta
m_{t}}$ is $\mathcal{O}({\Delta
m_{t}}^{n})\times\mathcal{O}(\frac{1}{t^{n}})=\mathcal{O}(({\frac{\Delta
m_{t}}{t}})^{n})$.

###  A.1 $\Delta m_{t}=\alpha$

This section derives recurrence relation for ranks $P_{k}$’s when number of
edges is a fixed constant $\alpha$ for each time step $t$.
$k=1$

Consider eqn. (A.1) for $\Delta m_{t}=\alpha$

$(t+1)P_{k,t+1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha}\bigl{[}\bigl{(}1-\frac{k}{2(\alpha+1)(t-1)}\bigr{)}tP_{k,t}+1\bigr{]}$

$\begin{split}\implies&tP_{k,t+1}+P_{k,t+1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha}\bigl{[}tP_{k,t}-\frac{kt}{2(\alpha+1)(t-1)}P_{k,t}+1\bigr{]},\\\
\implies&tP_{k,t+1}+P_{k,t+1}=\bigl{(}1-\frac{2\alpha}{t+1}+\dots\bigr{)}\bigl{[}tP_{k,t}-\frac{kt}{2(\alpha+1)(t-1)}P_{k,t}+1\bigr{]},\\\
\implies&tP_{k,t+1}+P_{k,t+1}=tP_{k,t}-\frac{kt}{2(\alpha+1)(t-1)}P_{k,t}+1-\frac{2\alpha}{t+1}tP_{k,t}+\dots.\end{split}$

On applying limit $\lim t\to\infty$ this equation acquires the form

$P_{k}=-\frac{k}{2(\alpha+1)}P_{k}+1-2\alpha P_{k},$

or

$P_{k}=1-\bigl{[}2\alpha+\frac{k}{2(\alpha+1)}\bigr{]}P_{k}.$

$\implies P_{1}=\frac{2(\alpha+1)}{4\alpha^{2}+6\alpha+3}.$ (A.8)

$k>1$

We will find expressions for coefficients $C_{k-n,\Delta
m_{t}}~{}n=0,1,2\dots\text{ for }\Delta m_{t}=\alpha$ and evaluate the
recurrence relation eqn. (A.2).

$\bm{C_{k,\alpha}}$

$\begin{split}&C_{k,\alpha}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha}\bigl{(}1-\frac{k}{2m_{t}}\bigr{)},\\\
\implies&tC_{k,\alpha}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha}\bigl{(}t-k\frac{t}{2(\alpha+1)(t-1)}\bigr{)},\\\
\implies&tC_{k,\alpha}=\bigl{(}1-\frac{2\alpha}{t+1}+\dots\bigr{)}\bigl{(}t-k\frac{t}{2(\alpha+1)(t-1)}\bigr{)}.\\\
\implies&tC_{k,\alpha}P_{k,t}=tP_{k,t}-k\frac{t}{2(\alpha+1)(t-1)}P_{k,t}-\frac{2\alpha
t}{t+1}P_{k,t}+\dots.\end{split}$

$tP_{k,t}$ will be cancelled out by the term on L.H.S.(A.2).
$tC_{k,\alpha}P_{k,t}$ approaches to
$-\bigl{(}\frac{k}{2(\alpha+1)}+2\alpha\bigr{)}P_{k}$.

$\bm{C_{k-1,\alpha}}$

$\begin{split}&C_{k-1,\alpha}=\alpha\bigl{(}1-\frac{k-1}{2m_{t}}\bigr{)}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha-1}\frac{2}{t+1}+\frac{k-1}{2m_{t}}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha},\\\
\implies&tC_{k-1,\alpha}=\alpha\bigl{(}1-\frac{k-1}{2m_{t}}\bigr{)}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha-1}\frac{2t}{t+1}+(k-1)\frac{t}{2(\alpha+1)(t-1)}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha}\\\
\end{split}$

Term $tC_{k-1,\alpha}P_{k-1,t}$ approaches to
$(2\alpha+\frac{k-1}{2(\alpha+1)})P_{k-1}$.

$\bm{C_{k-2,\alpha}\text{ for }k>2}$

$\begin{split}&C_{k-2,\alpha}^{{}^{\prime}}=\frac{\alpha(\alpha-1)}{2}\Psi^{\alpha-2}\Phi^{2},\\\
\implies&C_{k-2,\alpha}^{{}^{\prime}}=\frac{\alpha(\alpha-1)}{2}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\alpha-2}\bigl{(}\frac{2}{t+1}\bigr{)}^{2},\\\
\text{with already determined
}&C_{k-1,\alpha}^{{}^{\prime}}=a_{l}^{k-1}\Psi^{\alpha-1}\Phi,\\\
\implies&tC_{k-2,\alpha}=\bigl{(}1-\frac{k-2}{2(\alpha+1)(t-1)}\bigr{)}tC_{k-2,\alpha}^{{}^{\prime}}+\frac{k-2}{2(\alpha+1)(t-1)}tC_{k-1,\alpha}^{{}^{\prime}}.\\\
\end{split}$

Maximum order term in the $tC_{k-2,\alpha}$ is of order
$\mathcal{O}(\frac{1}{t})$ .The term $tC_{k-2,\alpha}$ vanishes to $0$ on
taking limit $\lim_{t\to\infty}$.

$\bm{C_{k-n,\alpha}}\text{ for }k>n$ for $n=3,4,...$
$tC_{k-n,\alpha}$ is of order $\frac{1}{t^{n-1}}$. $tC_{k-n,\alpha}$ for
$n=3,4,...$ vanishes on applying the limit.

Now we have all limits $\lim_{t\to\infty}tC_{k-n,\alpha}$ required to
determine limiting value of the equation (A.2). Equation (A.2) on applying
limit becomes

$P_{k}=\bigl{[}2\alpha+\frac{k-1}{2(\alpha+1)}\bigr{]}P_{k-1}-\bigl{[}2\alpha+\frac{k}{2(\alpha+1)}\bigr{]}P_{k},$

$\implies
P_{k}=\frac{k+4\alpha^{2}+4\alpha-1}{k+4\alpha^{2}+6\alpha+2}P_{k-1}.$ (A.9)

##  Appendix B Variable $\Delta m_{t}$

Here, for the sake of completion, we will discuss the case when $\Delta m_{t}$
varies with time $t$ and find recurrence relation. It varies at each time step
$t$, with $\Delta m_{t}+1$ is proportional to the fraction of the total number
of edges by the number of nodes. Recurrence relation will be derived only
formally.

###  B.1 The number of edges in edge-step at time step $t$

The number of edges at the completion of time step $t$ (both node and edge-
step completed ) is $m_{t}$. $\Delta m_{t}$ is the number of edges to be added
during the edge-step. As mentioned earlier, this number is determined by the
fraction of edges by number of nodes. $\Delta m_{t}=\lceil\frac{\beta
m_{t}}{t}\rceil-1$, with parameter $\beta$ as a real number greater than $1$.
For the current analysis, $\beta\in(1,2)$. After the node-step, total number
of number of edges are $m_{t+1}$. $m_{t+1}$, the total number of edges after
the completion of both node- and edge- steps, is given by the relation

$m_{t+1}=m_{t}+\Delta m_{t}+1,$

We select $\beta$ such that $\frac{\beta m_{t}}{t}>>1$, $\Delta
m_{t}\approx\frac{\beta m_{t}}{t}$.
It implies that,

$\begin{split}&m_{t+1}\approx m_{t}(1+\frac{\beta}{t})\\\
\implies&m_{t+1}\approx
m_{1}(1+\frac{\beta}{t})(1+\frac{\beta}{t-1})...(1+\frac{\beta}{1}),\\\
\implies&m_{t+1}\approx
m_{1}\frac{(\beta+t)(\beta+t-1)(\beta+t-2)...(\beta+1)}{t!},\\\
\implies&m_{t+1}\approx
m_{1}\frac{\Gamma(\beta+t+1)}{\Gamma(t+1)\Gamma(\beta+1)}.\end{split}$

Stirling’s formula,

$\Gamma(t+1)\approx\sqrt{2\pi t}\bigl{(}\frac{t}{e}\bigr{)}^{t}$

which gives good approximation for the factorials of large number, can be used
here to get simplified form of the above expression. Using this approximation,
expression for $m_{t+1}$ reduces to

$m_{t+1}\approx\frac{1}{\sqrt{2\pi\beta^{3\beta}}}\frac{(\beta+t)^{\beta+t+\frac{1}{2}}}{t^{t+\frac{1}{2}}},$

or

$m_{t+1}\approx\frac{\bigl{(}{1+\frac{\beta}{t}}\bigr{)}^{\beta+t+\frac{1}{2}}}{\sqrt{2\pi\beta^{3\beta}}}t^{\beta},$

$m_{t+1}\approx m^{*}_{1}t^{\beta}.$ (B.1)

where $m^{*}_{1}=\frac{m_{1}e^{\beta}}{\sqrt{2\pi\beta^{3\beta}}}$.

Thus,

$\lim_{t\to\infty}m_{t}=\lim_{t\to\infty}m^{*}_{1}t^{\beta}.$ (B.2)

This formulation is valid only for $\Delta m_{t}>>1$. It implies that
$\beta>1$.

###  B.2 Recurrence relation for degree distribution

$k=1$

Consider the equation A.1 once again.

$(t+1)P_{k,t+1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{[}tP_{k,t}+1-\frac{k}{2m_{t}}tP_{k,t}\bigr{]}.$

Formally speaking, if equation is divided by $t+1$ and limit
$\lim_{t\to\infty}$ is applied, we get $P_{k,t+1}\to P_{k,t}$. Let us write
equation into the form where we can cancel the highest order terms.

$\bigl{[}(t+1)-\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}t\bigr{]}P_{k,t+1}=\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{[}1-\frac{k}{2m_{t}}tP_{k,t}\bigr{]}.$

The $\lim_{t\to\infty}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}=\lim_{t\to\infty}\exp({\Delta
m_{t}\ln{\bigl{(}1-\frac{2}{t+1}\bigr{)}}})=1$ for $\beta<2$. On applying the
limit, R.H.S. becomes $1$. Let us now evaluate L.H.S. limit.

$\begin{split}&\lim_{t\to\infty}\bigl{[}(t+1)-\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}t\bigr{]}\\\
&=\lim_{t\to\infty}\bigl{[}(t+1)-\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}t\bigr{]}\\\ &=\lim_{t\to\infty}\bigl{[}(t+1)-\bigl{(}1-\frac{2\Delta
m_{t}}{t+1}+\dots\bigr{)}t\bigr{]}\\\ &=\lim_{t\to\infty}\bigl{[}1+2\Delta
m_{t}+\dots\bigr{]}\\\ \end{split}$

is the reduced form of the L.H.S. limit.

Equating both limits,

$\implies\lim_{t\to\infty}\bigl{[}1+2\Delta m_{t}+\dots\bigr{]}P_{k,t+1}=1.$

It can be seen that for $\beta\in(1,2)$, the highest order term in the
expression $\bigl{[}(t+1)-\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}t\bigr{]}$ is $t^{\beta-1}$, whereas
the R.H.S. of the equation has order $1$.

This implies that

$P_{1}\to 0.$

Now consider the case for $k>1$ . We will evaluate limiting values of
coefficients $tC_{k-n,\Delta m_{t}},n=0,1,\dots$

$\bm{C_{k,\Delta m_{t}}}$

$\begin{split}C_{k,\Delta
m_{t}}=\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}.\\\ \end{split}$

Gathering terms with $k$ on L.H.S, coefficient of $P_{k,t}$ in (A.2) for very
large $t$ becomes $((t+1)-tC_{k,\Delta m_{t}})$, with

$\begin{split}(t+1)-tC_{k,\Delta
m_{t}}&=\bigl{[}(t+1)-\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}t\bigr{]}\\\
&=\bigl{[}(t+1)-\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta m_{t}}t\bigr{]}\\\
&=\bigl{[}(t+1)-\bigl{(}1-\frac{2\Delta m_{t}}{t+1}+\dots\bigr{)}t\bigr{]}\\\
&=\bigl{[}1+\frac{2t\Delta m_{t}}{t+1}+\dots\bigr{]}\\\ \end{split}$

Limiting value of the $[(t+1)-tC_{k,\Delta m_{t}}]P_{k,t}$ becomes:

$\lim_{t\to\infty}\bigl{[}1+\frac{2t\Delta
m_{t}}{t+1}+\dots\bigr{]}P_{k,t}=\lim_{t\to\infty}\bigl{[}1+{2\Delta
m_{t}}+\dots\bigr{]}P_{k}.$

The highest order term in the expression
$\bigl{[}(t+1)-\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}\bigl{(}1-\frac{k}{2m_{t}}\bigr{)}t\bigr{]}$ is of order
$\mathcal{O}{(\Delta m_{t})}$ or of order $t^{\beta-1}$. Thus the coefficient
of is of $P_{k,t}$ has order $\mathcal{O}{(\Delta m_{t})}$.

$\bm{C_{k-1,\Delta m_{t}}}$

This coefficient exists for $k>1$.

$\begin{split}C_{k-1,\Delta m_{t}}=\bigl{(}1-\frac{k-1}{2m_{t}}\bigr{)}\Delta
m_{t}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}-1}\frac{2}{t+1}+\frac{k-1}{2m_{t}}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}.\\\ \end{split}$

Consider $tC_{k-1,\Delta m_{t}}$,

$\begin{split}tC_{k-1,\Delta m_{t}}=\bigl{(}1-\frac{k-1}{2m_{t}}\bigr{)}\Delta
m_{t}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}-1}\frac{2t}{t+1}+\frac{(k-1)t}{2m_{t}}\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta
m_{t}}.\\\ \end{split}$

As already shown that $\bigl{(}1-\frac{2}{t+1}\bigr{)}^{\Delta m_{t}}\to 1$,
second term in the sum will approach to $0$. The first term contains $2\Delta
m_{t}$ as a maximum order term. Thus $2\Delta m_{t}$ is maximum order
coefficient of $P_{k-1,t}$. In short, $O(t^{\beta-1})$ is the order of
$tC_{k-1,\Delta m_{t}}P_{k-1,t}$.

$\bm{C_{k-2,\Delta m_{t}}\text{ for }k>2}$

This coefficient exists for $k>2$.

$C_{k-2,\Delta m_{t}}=\bigl{(}1-\frac{k-2}{2m_{t}}\bigr{)}C_{k-2,\Delta
m_{t}}^{{}^{\prime}}+\frac{k-2}{2m_{t}}C_{k-1,\Delta m_{t}}^{{}^{\prime}}.\\\
$

Consider $tC_{k-2,\Delta m_{t}}$. Highest order term in the expression is of
$O(\frac{\Delta m_{t}(\Delta
m_{t}-1)}{2}t\Phi^{2})=\mathcal{O}(t^{2\beta-3})$. Thus maximum order
coefficient of $P_{k-2,t}$ has the order $\mathcal{O}(t^{2\beta-3})$. This
term when divided by the term of the order $\mathcal{O}(t^{\beta-1})$, results
into a term of order $t^{\beta-2}$, which will approach to $0$ for $\beta<2$.

$\bm{C_{k-n,\Delta m_{t}}\text{ for }k>n}$ for $n=3,4,...$

$C_{k-n,\Delta m_{t}}=a_{\Delta m_{t}}^{k-n}\Psi^{\Delta m_{t}-n}\Phi^{n}$
with $a_{\Delta m_{t}}^{k-n}$ is of $\mathcal{O}({\Delta m_{t}}^{n})$.

It is sufficient to find only orders of these terms. Order of $tC_{k-n,\Delta
m_{t}}$ is $\mathcal{O}(t^{n(\beta-1)-1})$. On dividing the equation by
$t^{\beta-1}$, we get coefficients of $P_{k-n,t}$ of order
$t^{(n-1)(\beta-2)}$ that vanishes to $0$ for $\beta<2$ on applying the limit
$\lim_{t\to\infty}$. Thus, on applying $\lim_{t\to\infty}$ to (A.2), following
expression is obtained:

$\lim_{t\to\infty}\bigl{[}1+2\Delta
m_{t}+\dots\bigr{]}P_{k}=\lim_{t\to\infty}[2\Delta m_{t}]P_{k-1}.$

$P_{k}=\lim_{t\to\infty}[\frac{2\Delta m_{t}}{2\Delta m_{t}+1}]P_{k-1}.$

Thus for $k=2,3,\dots$

$P_{k}=P_{k-1}.$

or

$P_{k}=P_{1}.$

At each time step $P_{k,t}$ must satisfy the constraint
$\sum_{k=1}^{\infty}P_{k,t}=1$. For a moment, assume that $P_{k}$ is a
stationary degree distribution. Then the above relationship shows that
$\lim_{t\to\infty}P_{k,t}\to P_{k}$ and results into $P_{k}\equiv
0~{}~{}\forall k$, which contradicts the constraint. It means that we do not
get a stationary distribution and it is a time dependent satisfying the
constraint $\sum_{k=1}^{K_{t}}P_{k,t}=1$, with $K_{t}$ as the maximum degree
of the network node, growing at each time step. The network is no longer a
scale-free network but converts to a network with uniform degree distribution.
We can estimate the value of $K_{t}$. For large $t$, and for all $k>1$,

$P_{k,t}\approx P_{1,t}$

Now,

$\begin{split}\sum_{k=1}^{K_{t}}P_{1,t}=1\\\
K_{t}=\frac{1}{P_{1,t}}\end{split}$

Thus if $P_{1,t}$ is of order $\frac{1}{t^{\beta-1}}$, $K_{t}$ is of order
$t^{\beta-1}$.