JAIST Repository
https://dspace.jaist.ac.jp/

Title

Asymptotic behavior of the node degrees in theensemble average of adjacency matrix

Author(s)Hayashi, Yukio

Citation

Network Science, 4(3): 385‑399

Issue Date

2016‑09

Type

Journal Article

Text version

publisher

URL

http://hdl.handle.net/10119/14055

RightsCopyright (C) Cambridge University Press 2016.
This is an Open Access article, distributed under
the terms of the Creative Commons Attribution
licence(http://creativecommons.org/licenses/by/4.0/),
which permits unrestricted re‑use, distribution,and reproduction in any medium, provided theoriginal work is properly cited.

Description

Japan Advanced Institute of Science and Technology

c Cambridge University Press 2016. This is an Open AccessNetwork Science 4 (3): 385–399, 2016. 
article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.
org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium,provided the original work is properly cited.
doi:10.1017/nws.2016.10

385

Asymptotic behavior of the node degrees in theensemble average of adjacency matrix
YUKIO HAYASHIJapan Advanced Institute of Science and Technology, Ishikawa, Japan(e-mail: yhayashi@jaist.ac.jp)

Abstract
Various important and useful quantities or measures that characterize the topological network
structure are usually investigated for a network, then they are averaged over the samples.
In this paper, we propose an explicit representation by the beforehand averaged adjacency
matrix over samples of growing networks as a new general framework for investigating
the characteristic quantities. It is applied to some network models, and shows a good
approximation of degree distribution asymptotically. In particular, our approach will beapplicable through the numerical calculations instead of intractable theoretical analyses,
when the time-course of degree is a monotone increasing function like power law or logarithm.
Keywords: ensemble average, growing networks, degree distribution, degree–degree correlations

1 Introduction
Many social, technological, and biological networks belong to a common scalefree (SF) structure (Babarási & Albert, 1999) which consists of many low-degree
nodes and a few high-degree nodes called as hubs. The degree distribution follows apower law, therefore an SF network has an extreme vulnerability against hub attacks(Albert et al., 2000). In addition, these real networks are classiﬁed into assortative anddisassortative networks (Newman, 2003). For examples, typical social networks, e.g.
coauthorships and actor collaborations, are assortative, while typical technologicaland biological networks, e.g. Internet, World-Wide-Web, protein-interaction, andfood webs, are disassortative. In assortative networks, nodes with similar degrees
tend to be connected, and thus positive degree–degree correlations appear. In
disassortative networks, nodes with diﬀerent degrees: low and high degrees tend
to be connected, and thus negative degree–degree correlations appear.
Through the above ﬁndings in network science, superior network theories andeﬃcient algorithms have been developed for analyzing network topology anddynamics (Newman, 2010). However, studies for the cases with degree–degreecorrelations are not clear enough for successful analyses of topological structuresand epidemics on networks except some percolation analyses. Recently, it has been
numerically and theoretically found that an onion-like structure with positive degree–degree correlations gives the nearly optimal robustness against hub attacks in an SF
network (Herrmann et al., 2011; Schneider et al., 2011; Tanizawa et al., 2012).
On the other hand, the average behavior of stochastically generated networkmodels or empirical data samples of real networks is discussed in many applications.

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

386

Y. Hayashi

Usually, some characteristic quantities such as degree distribution or clustering
coeﬃcient are investigated for a network, then their quantities are averaged over the
samples of networks in which the existence of a generation rule (mechanism) of the
networks is assumed. In this paper, we focus on the beforehand averaged network
structure over samples, and calculate the degree distribution for several models of
growing network with or without degree–degree correlations. This representation will
give a general framework for numerically investigating the characteristic topologicalquantities in growing networks. Since our framework is supported by the interesting
property of ordering that older nodes tend to have higher degrees in a randomly
growing network (Callaway et al., 2001), a wide range of application to growing
networks can be expected.
2 Representation by the ensemble average of adjacency matrix
We consider a set of growing networks in which a new node is added withprobabilistic links to existing nodes in a network at each time step. To study theaverage behavior of the stochastic processes in many samples, we use the ensemble
average of adjacency matrix deﬁned as follows:⎞⎛0
1 a13 . . . aij . . . a1i . . . a1n⎜ 1
0 a23 . . . a2j . . . a2i . . . a2n ⎟⎟⎜⎟⎜a⎜ 31 a32 0 . . . a3j . . . a3i . . . a3n ⎟
⎜ .
..
..
..
..
..
..
.. ⎟
..
⎜ ..
.
.
.
.
.
.
.
. ⎟
⎟
⎜
⎟
def ⎜
a
a
.
.
.
0
.
.
.
a
.
.
.
a
a
⎟
⎜
j1
j2
3j
ji
jn
A(t) = ⎜
..
..
..
..
..
..
.. ⎟
..
⎟
⎜ ..
. .
⎜ .
.
.
.
.
.
. ⎟
⎟
⎜
⎜ ai1 ai2 . . . . . . aij . . . 0 . . . ain ⎟
⎟
⎜
⎜ ..
..
..
..
..
..
.. . .
.. ⎟
⎝ .
.
.
.
.
.
.
.
. ⎠
an1

an2

...

...

...

...

ani

...

0

Here, without loss of generality, we set connected two nodes as the minimum initial
conﬁguration: a11 = a22 = 0, a12 = a21 = 1, and the degree k1 (0) = k2 (0) = 1.
Note that at each time step, the matrix is expanding with the inverse L shapeof elements a1n , a2n , . . . , an−1n , 0, ann−1 , . . . , an2 , an1 at the right-bottom corner. The
diagonal element aii is always 0 due to no self-loop at each node i. Other elements
are 0 6 aij 6 1, i = j, as the average number of links from i to j over the samplesof networks. The value of each element is deﬁned in order according to the passageof time. We assume that there are no adding links between existing nodes i, j < n
at any time t = n − 2. Only links between selected old nodes and new node n areadded in a growing network.
In the sample-based description, the ensemble average of adjacency matrix is
A(1) (t) + A(2) (t) + · · · + A(k) (t) + · · · + A(Ns ) (t),Ns
where A(k) (t) denotes an adjacency matrix of the k-th sample whose elements area(k)ij = 1 or 0 corresponded to the connection or disconnection from i to j, buta(k)ij = 0 or undeﬁned for i, j > t + 2 because of the size n = t + 2 at time t. Ns
denotes the number of samples. We remark that an adjacency matrix is fundamental
A(t) =

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

Ensemble average of adjacency matrix

387

and important because it includes the necessary and suﬃcient information about a
network structure and is useful for a mathematical treatment.
In this explicit representation of general framework, for each i-th node, i =1, 2, . . . , n − 1, the (out-)degree is updated from time t − 1 to t,ki (t) = ki (t − 1) + ain .

(1)

The (out-)degree of n-th node added at time t = n − 2 is deﬁned by the sum of links
from node n to nodes i,
n−1

def
kn (t) =
ani .
(2)
i=1

We should remark that the iterative calculations of Equations (1) and (2) areequivalent to the averaged values over the samples after calculating the degrees foreach sample of the networks at time t. With this equivalence in mind, we investigate
the asymptotic behavior of ki (t) for a large t. We note that ki (t) is a monotone
non-decreasing function of time t because of ki (t) − ki (t − 1) = ain > 0 from Equation(1) in growing networks.
3 Asymptotic behavior of the node degrees
As examples, we apply the ensemble average of adjacency matrix to some networkmodels. However, our approach is applicable to other growing networks especially ina wide class, e.g. with approximately power law or exponential degree distribution.
In the following, we assume that each link is undirected: aij = aji .
3.1 Babarási and Albert model
Since the continuous-time approximation of Equation (1) is generally
dki (t)= ain ,
dt
our approach is applicable to the Babarási and Albert (BA) model (Babarási et al.,1999) as follows:
Preferential attachment:ki (t − 1)
m × ki (t − 1)
≈
,
ani =
k
(t
−
1)
2t
l l
Uniform attachment:∀i ani =m,m0 + t − 1

where m0 denotes the initial number of nodes, and m denotes the number of adding
links at each time step.
For the two cases of preferential and uniform attachments, ki (t) = m t/ti andki (t) = m(log(m0 +t−1)−log(m0 +ti −1)+1) have been derived with the corresponding
degree distributions p(k) ∼ k −3 and p(k) ∼ e−k , respectively (Babarási et al., 1999).
The analysis in BA model is based on the invariant ordering property of degrees
in which older nodes get more links averagely at any time in the growth of

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

388

Y. Hayashi

Fig. 1. Basic linking processes at each time step from a new node to a randomly chosen node
and/or the neighbor nodes in the growing networks. The thick bold lines show adding links,
and the dashed line shows a deleted one. The thin lines show already existing links at thattime.

network. Under the invariant ordering property, our approach can be regarded as
an extension of mathematical treatment in the BA model through the representationby the ensemble average of adjacency matrix over samples of growing networks.
3.2 Duplication-divergence model
We preliminary introduce a duplication-divergence (D-D) model (Pastor-Satorras
et al., 2003; Sole et al., 2002) without mutations of random links between existingnodes, whose generation mechanism is known as fundamental in biological protein–protein interaction networks. In the D-D model, at each time step, a new nodeis added and links to neighbor nodes of a uniformly randomly chosen node (seeFigure 1(a)). Some duplication links are deleted with probability δ > 0. Here, nomutations are to simplify the discussion and to connect to the next subsection.
Although the degree distribution in the D-D model can be approximately analyzed
by the approach of mean-ﬁeld-rate equation (Pastor-Satorras et al., 2003; Sole etal., 2002), we show the applicability of our approach to the D-D model in order toextend it to more general networks. Moreover, in the next section, we reveal thatolder nodes tend to have higher degrees (Callaway et al., 2001) in the D-D model,
whose ordering of degree ki (t) for node index i was not found from the above
approach.
Since the n-th new node links to the neighbor node i of a chosen node j = i fromexisting nodes 1 6 i, j 6 n − 1 in a network of D-D model, we haveani =(1 − δ) n−1
1
j=1 aji=(1 − δ)ki (t − 1),
n−1
n−1

(3)

where we use the uniform selection probability 1/(n − 1) of each node j and theno-deletion rate 1 − δ for linking to the neighbor nodes.
From Equations (1)–(3), we obtainki (t) =

1+

1−δ
n−1

ki (t − 1),(4)

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

389

Ensemble average of adjacency matrix1−δ ki (t − 1).
n−1
n−1

kn (t) =(5)

i=1

By applying Equation (4) recursively, we deriveki (t) ==n − 1 + (1 − δ)n−1

n − 2 + (1 − δ)
n−2

...

i + (1 − δ)ikiΓ(n + (1 − δ))/Γ(i + (1 − δ))ki ∼ (t + 1)1−δ .
Γ(n)/Γ(i)In addition, the continuous-time approximation of Equation (4) isdki (t)1−δ= ani =ki (t).
dt
t+1
From the separation of variables method, we obtain the solutionki (t) = (t + 1)1−δ ∼ t1−δ .
When we denote the initial degree ki at the inserted time ti for a node i, the above
solution is rewritten as1−δt.
ki (t) ≈ kiti
From the existence of parallel curves shown in Figure 2, the ordering of degrees
kn (t) < kn−1 (t) < · · · < k3 (t) < k2 (t) = k1 (t),(6)

is not changed. In other word, older nodes get more links averagely. Thus, we obtain
1/(1−δ)1/(1−δ)kitki,t = 1 − 1/(1−δ)
p(ki (t) < k) = p ti >k
N0 + tk1∂p(ki (t) < k)
∼ k −(1+ 1−δ ) ,(7)∂kwhere N0 + t is the number of nodes at time t, and N0 denotes the initial number
1of nodes. In the tail of degree distribution, the exponent of power law is 1 + 1−δ
1asymptotically. Note that the slightly diﬀerent exponent 1 + 1−δ to the conventional
approximation (Kim et al., 2002; Pastor-Satorras et al., 2003) is not strange, since
the mutations are necessary for their D-D models.
Figure 3(a)–(c) shows the time-course of ki (t) ∼ t1−δ in the case of δ = 0.3, 0.5,
and 0.7, respectively, averaged over 100 samples. The black, orange, and magentalines are the numerical results of Equations (4) and (5) for the node i = 1, 10, and100. The cyan line guides the estimated slope of 1 − δ in log–log plot. In Figure 3(d),the red, green, and blue lines show the degree distributions for δ = 0.3, 0.5, and 0.7,
respectively, at the size n = 104 . The magenta, cyan, and gray dashed lines guides
1
for these δ.
the corresponding slopes of 1 + 1−δ

p(k) =

3.3 Copying model
A modiﬁcation (Hayashi, 2014) of the D-D model (Pastor-Satorras et al., 2003; Soleet al., 2002) by adding a mutual link between a new node and a randomly chosen

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

390

Y. Hayashi
3

2

10

10

102

1

ki (t )ki (t )

10
101

0

10

0

10

10−1 0
10

10

1

2

3

10
t

4

10

10

10−1 010110(a) δ = 0.3

10
t

2

3

10

4

10

(b) δ = 0.5

2ki (t)

10

1

10

0

10

10−1 0
10

1

10

2

10
t

3

10

4

10

(c) δ = 0.7

Fig. 2. Parallel curves of time-course ki (t) of degree in the D-D model with a rate δ of link
deletion. The color lines from top to bottom correspond to the nodes i = 1 or 2, 3, 4, . . . , 30.
Note that each node i is born at time ti = i − 2. (Color online)

node has been proposed. The mutual link contributes to avoid the singularity called
as non-self-averaging even for δ < 1/2 without mutations (Hayashi, 2014). The
growing network is constructed as shown in Figure 1(b). It is referred to as copying
model. At each time step, a new node is added. The new node links to a uniformly
randomly chosen node, and to its neighbor nodes with probability 1 − δ.
In the copying model, we haveani =1 + (1 − δ) n−1
1 + (1 − δ)ki (t − 1)
j=1 aji
=
,
n−1
n−1

(8)

since the n-th new node links to a uniformly randomly chosen node i and to theneighbor node i when other node j is chosen from existing nodes 1 6 i, j 6 n − 1
in the network. These eﬀects are in the ﬁrst term 1/(n − 1) and the second term
(1 − δ) n−1
j=1 aji /(n − 1) in Equation (8).
From Equations (1), (2) and (8), we obtainki (t) =

1−δ
1
+ 1+
n−1
n−1

ki (t − 1),1−δ ki (t − 1).
n−1

(9)

n−1

kn (t) = 1 +

(10)

i=1

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

391

Ensemble average of adjacency matrix
103

103
102

ki (t)ki (t )

102

101

1

10

100

100
101

102

103

10−1
101

104

103

t

t

(a) δ = 0.3(b) δ = 0.5

102

104

10−1

1

10−2
p (k)

10
ki (t )

102

100

10−3
−4

10
10−1

10−5
−6

10

10−2 1
10

2

10

10

3

10

4

10

t

(c) δ = 0.7

0

10
k

1

10

2

(d) p(k)Fig. 3. Results for the D-D model without mutations. (a)–(c) Time-courses ki (t) of degree fornode i = 1, 10, and 100 shown by black, orange, and magenta lines, respectively, at the typicalvalues of rate δ of link deletion. The cyan line guides the estimated slope 1 − δ of ki (t) ∼ t1−δ .
(d) Degree distribution p(k) in the cases of δ = 0.3, 0.5, and 0.7 shown by red, green, and bluelines, respectively. The dotted magenta, cyan, and gray lines show the estimated power law
1
distributions k −(1+ 1−δ ) . (Color online)

By applying Equation (9) recursively, we deriveki (t) =
=

1
+
t+1

t + 1 + (1 − δ)
t+1

1
+
t

t + (1 − δ)ki (t − 2)tt + 1 + (1 − δ)Γ(t + 2 + (1 − δ))/Γ(i)1++ ··· +ki (ti )t+1(t + 1)tΓ(t + 2)/Γ(i)≈ O(1/t) + (t + 1)1−δ ,(11)where we use n − 1 = t + 1 and the Staring formula Γ(x + 1) ≈ xx e−x .
In particular, by the mathematical induction, we conﬁrm that the case of δ = 0
generates a sequence of the complete graphs with ki (t) = t + 1 = n − 1 links at every
node of i = 1, 2, . . . , n. First, k1 (1) = k2 (1) = 2 and k3 (1) = 2 are obvious. Next, we
assume ki (t − 1) = (t − 1) + 1 = n − 2, from Equations (9) and (10), we deriveki (t) =
=

1
1
+ 1+
n−1
n−1

(n − 2) =1 + (n − 1)(n − 2) + (n − 2)n−1(n − 1)2= n − 1,n−1

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

392

Y. Hayashi

103

103

10

2

10

10

1

k i (t )ki (t)

2

1

10

100
100

101

102
t

103

100
100

104

101

(a) δ = 0.3

102
t

103

104

(b) δ = 0.5
2ki (t)

10

1

10

0

10

100

101

102
t

103

104

(c) δ = 0.7

Fig. 4. Parallel curves of time-course ki (t) of degree in the copying model with a rate δ of link
deletion. The color lines from top to bottom correspond to the nodes i = 1 or 2, 3, 4, . . . , 30.
Note that each node i is born at time ti = i − 2. (Color online)(n − 1)(n − 2)
= n − 1.
n−1
On the other hand, the continuous-time approximation of Equation (9) is
kn (t) = 1 +dki (t)1= ani =
+
dt
t+1

1−δ
t+1

ki (t).

Since this form is a ﬁrst-orderlinear diﬀerentialequation dki /dt + f(t)ki = g(t), by
applying the solution e− f(t)dt e f(t)dt g(t)dt + A , we obtain tki (t) = (t + 1)

1−δ1
dt + A
1+(1−δ)(t+
1)
0= A(t + 1)1−δ − C  ∼ t1−δ ,defwhere A and C  are constants of integration, and we use f(t) = −(1 − δ)/(t + 1) anddefg(t) = 1/(t + 1). Note that the solution t1−δ is only diﬀerent by O(1/t) to Equation(11), and can be ignored for a large t. As similar to the D-D model in subsection
3.2, from Equation (7) under the invariant ordering (6) in the parallel curves shownas Figure 4, the degree distribution asymptotically follows a power law with the1.
exponent 1 + 1−δ
Figure 5(a)–(c) shows the time-course of ki (t) ∼ t1−δ in the cases of δ = 0.3, 0.5,
and 0.7, respectively, averaged over 100 samples. The black, orange, and magentalines are the numerical results of Equations (9) and (10) for the node i = 1, 10, andDownloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

393

Ensemble average of adjacency matrix
10

3

10

3

10

2

10
ki (t)ki (t)

2

101

10

101

0

0

101

102

103

10

104

101

102

103

t

104

t

(a) δ = 0.3(b) δ = 0.5

102
10−1

p (k)

ki (t )

10

101

10
10
10

10

0

10

1

10

2

3

10
t

(c) δ = 0.7

4

10

−2
−3
−4
−5

10−6
0
10

1

10

10
k

2

3

10

4

10

(d) p(k)Fig. 5. Results for the copying model. (a)–(c) Time-courses ki (t) of degree for node i = 1, 10,
and 100 shown by black, orange, and magenta lines, respectively, at the typical values ofrate δ of link deletion. The cyan line guides the estimated slope 1 − δ of ki (t) ∼ t1−δ . (d)Degree distribution p(k) in the cases of δ = 0.3, 0.5, and 0.7 shown by red, green, and bluelines, respectively. The dotted magenta, cyan, and gray lines show the estimated power-law
1
distributions k −(1+ 1−δ ) . (Color online)

100. The cyan line guides the estimated slope of 1 − δ in log–log plot. It ﬁts to thelines of ki (t) for a large t. Moreover, as shown in Figure 5(d), Equation (7) gives
a good approximation at the size n = 104 . The red, green, and blue lines show thedegree distributions for δ = 0.3, 0.5, and 0.7, respectively. The magenta, cyan, and1
for these δ in the ﬁtting
gray dashed lines guides the corresponding slopes of 1 + 1−δto the tails.

3.4 Copying model with positive degree–degree correlations
In this subsection, we emphasize that our approach is eﬀective through the numericalestimation, even when an analytic derivation is intractable.
We consider a copying model with positive degree–degree correlations basedon a cooperative generation mechanism by linking homophily, in which densely
connected cores among high-degree nodes emerge (Hayashi, 2014). In more detail,the diﬀerence to the previously mentioned copying model is that the n-th new node
links to the neighbor nodes j of a randomly chosen node i with a probability

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

394

Y. Hayashi
16

14

14

12

12

10
ki (t )ki (t )

10
8
6

8
6

4

4

2

2

0
100

101

102

0
100

103

101

t

(a) δ = 0.3

ki (t )

102

103

t

(b) δ = 0.5
10
9
8
7
6
5
4
3
2
1
0
10

10

1

10

2

10

3

t

(c) δ = 0.7

Fig. 6. Parallel curves of time-course ki (t) of degree in the copying model with positive
degree–degree correlations and a rate δ of link deletion. The color lines from top to bottom
correspond to the nodes i = 1 or 2, 3, 4, . . . , 30. Note that each node i is born at time ti = i − 2.
(Color online)(1 − δ)f((1 − δ)ki (t − 1), kj (t − 1)) from existing nodes in the network. Such a functiondeff(x, y) =1,
1 + a|x − y|is necessary to enhance the degree–degree correlations, and a > 0 is a parameter(Wu & Holme, 2011). Since the degree of new node is unknown in advance due tothe stochastic process, it is temporary set as (1 − δ)ki (t − 1).
Thus, instead of Equation (8), we substitutedef 1 + (1 − δ)

ani =

n−1
j=1 aji × f((1 − δ)ki (t − 1), kj (t − 1))

n−1

,

(12)

for Equations (1) and (2).
Although the theoretical analysis of Equations (1) and (2) for Equation (12)is diﬃcult, the iterative calculations are possible numerically. When we assumeβki (t) ∼ log(t), we derive an exponential distribution as follows. From t ∼ eβki (t) , weobtaineβki
ti= βk (t) ,te ip(ki (t) < k) = p(ti >

eβki
t) =
eβk

1−

eβki
eβk

t
,
N0 + tDownloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

395

16

16

14

14

12

12

10

10

ki (t)ki (t)

Ensemble average of adjacency matrix

8

8

6

6

4

4

2
10

2
1

2

10
t

10

3

10

1

10
t

(a) δ = 0.3

3

100

14

10

12
10

p (k)

ki (t )

10(b) δ = 0.5

16

8
6

−1

10−2
10−3
10−4

4
2
101

2

102
t

103

10−5

5

10

15

20

25

30

35

40

k

(c) δ = 0.7(d) p(k)Fig. 7. Results for the copying model with positive degree–degree correlations. (a)–(c) Timecourses ki (t) of degree for node i = 1, 10, and 100 shown by black, orange, and magenta lines,
respectively, at the typical values of rate δ of link deletion. The cyan line guides the estimatedslope 1/β of ki (t) ∼ log(t)/β in semi-log plot. (d) Degree distribution p(k) in the cases ofδ = 0.3, 0.5, and 0.7 shown by red, green, and blue lines, respectively. The dotted magenta,
cyan, and gray lines show the estimated exponential distributions e−βk . (Color online)∂p(ki (t) < k)∼ e−βk ,∂kunder the invariant ordering (6) in the parallel curves shown as Figure 6.
Figure 7(a)–(c) shows that ki (t) denoted by black, orange, and magenta lines for
i = 1, 10, and 100 is approximated by log(t) in the copying model with degree–degree correlations. The cyan lines guide the estimated slopes β = 2.222, 1.818,
and 1.428 for δ = 0.3, 0.5, and 0.7, respectively, in the numerical ﬁttings for theiterative calculations of Equations (1), (2) and (12). Thus, as shown in Figure 7(d),the tails in p(k) denoted by red, green, and blue lines for δ = 0.3, 0.5, and 0.7 areapproximated by e−βk shown as magenta, cyan, and gray dashed lines at the sizen = 103 . Note that p(k) is only slightly deviated but the exponential part is remainedby adding shortcut links in order to self-organize a robust onion-like structure in
the incrementally growing network (Hayashi, 2014).
p(k) =

3.5 More general case
We consider the asymptotic behavior of the node degrees for a general casein growing networks. When the time-course ki (t) of degree follows a monotonedefincreasing function g(t) of time t, there exists the inverse function h(k) = g −1 (k) = t.

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

396

Y. Hayashi

It is possible that the time-course ki (t) is an average of observed real data for nodei, e.g. born at time t − 2. Fromh(ki )
ti
=
,
t
h(k)
we haveh(ki )p(ki (t) < k) = p ti >t .
h(k)Then, on the assumption of the invariant ordering (6) in parallel curves of {ki (t)},we derivep(k) =∂∂p(ki (t) < k)
=
∂k
∂k

1−

const.
h(k)th (k)∼ 2 ,N0 + th (k)where h (k) denote the derivative of h(k) by the variable k. We should remarkthat various degree distributions of non-power law may appear depending on the
shape of monotone increasing function ki (t) according to what type of generationin growing networks.
4 Analytic deviation for the invariant ordering of node degrees
We derive the invariant ordering (6) at any time t within parallel curves of monotone
increasing functions for the D-D and copying models discussed in subsections 3.2
and 3.3. In the following, we use double mathematical induction for node index iand time t.
Once ki (t − 1) − kj (t − 1) > 0 is satisﬁed for 1 or 2 6 i < j 6 n − 1 at t = n − 2 > 1,
ki (t) − kj (t) = (ki (t − 1) − kj (t − 1)) + (ain − ajn )1−δ= 1+(ki (t − 1) − kj (t − 1)) > 0,
n−1

(13)

is obtained from Equations (1), (4) and (9). Here, from Equations (4) and (5) atn = 3 with the initial condition k1 (0) = k2 (0) = 1, we obtain1−δ
, k3 (1) = 1 − δ < k1 (1) = k2 (1).
2
From Equations (9) and (10) at n = 3 with the same initial condition, we also obtaink1 (1) = k2 (1) = 1 +δ1−δ, k3 (1) = 1 +(1 + 1) < k1 (1) = k2 (1).
2
2
Since the assumption in Equation (13) is satisﬁed for i = 1 or 2 and j = 3 at t = 2,
we havek1 (1) = k2 (1) = 2 −k3 (2) < k2 (2) = k1 (2),..
.
k3 (t) < k2 (t) = k1 (t),(14)

by applying Equation (13) recursively for t > 2.
On the other hand, from Equations (4) and (5), we rewrite

n−2
1−δ 
kn (t) =ki (t − 1) + kn−1 (t − 1) ,n−1
i=1

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

397

Ensemble average of adjacency matrix
kn−1 (t) =

1−δ
n−1

1+

kn−1 (t − 1),1−δ ki (t − 2),n−2n−2kn−1 (t − 1) =i=1

at t = n − 2, andki (t − 1) =

1+

1−δ
n−2

1−

n−1−δ
n−1

ki (t − 2),for i = 1, 2, . . . , n − 2. Then, we havekn−1 (t) − kn (t) =

1−δ
n−2

n−2


ki (t − 2) > 0.

Similarly, from Equations (9) and (10), we rewrite
n−2


1−δ
kn (t) = 1 +n−1
kn−1 (t) =

(15)

i=1



ki (t − 1) + kn−1 (t − 1) ,

i=1

1−δ
1
+ 1+
n−1
n−1

kn−1 (t − 1),1−δ ki (t − 2),n−2n−2kn−1 (t − 1) = 1 +i=1at t = n − 2, andki (t − 1) =

1−δ
1
+ 1+
n−2
n−2

ki (t − 2),for i = 1, 2, . . . , n − 2. Then, we also havekn−1 (t) − kn (t) =1−δδ
+n−1 n−2

1−

n−1−δ
n−1

n−2


ki (t − 2) > 0.

(16)

i=1

By applying Equation (13) recursively for t > n − 2 after substituting Equation(15) or (16) to the right-hand side of Equation (13), we obtaink3 (t) − k4 (t) > 0,
k4 (t) − k5 (t) > 0,..
.
kn−1 (t) − kn (t) > 0.

(17)

From Equations (14) and (17), we obtain the ordering (6) after all.
Next, we consider the existing condition of the ordering (6) within parallel curvesof {ki (t)} for a general case of growing networks discussed in subsection 3.5.
From Equation (1) for 1 or 2 6 i < j 6 n − 1 at t = n − 2 > 2, we haveki (t) − kj (t) = (ki (t − 1) − kj (t − 1)) + (ain − ajn ).

(18)

If older nodes tend to get more links,
ain > ajn

(19)

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

398

Y. Hayashi

hold in the ensemble average of adjacency matrix. Then, we remark k3 (t) < k2 (t) =k1 (t) from Equation (19) and k3 (1) = k3 (0) + a13 + a23 < k1 (1) = k1 (0) + a31 or
k2 (1) = k2 (0) + a32 with the initial values k3 (0) = 0 and k1 (0) = k2 (0) = 1.
On the other hand, from Equations (1) and (2), we derivekn−1 (t) − kn (t) =n−2
(a(n−1)l − anl ).

l=1

If Equation (19) hold with aij = aji , for n > 4, we havekn−1 (t) − kn (t) > 0.

(20)

Therefore, on the condition (19), we obtain the ordering (6) from Equations (18)and (20).
5 Conclusion
We have proposed the explicit representation by the ensemble average of adjacency
matrix over samples of growing networks. The important point is that the adjacency
matrix is averaged in advance before calculating a characteristic quantity about
the topological structure for each sample. The ensemble average has been applied
to some network models: BA (Babarási et al., 1999), D-D (Pastor-Satorras et al.,
2003; Sole et al., 2002), and copying (Hayashi, 2014) models for investigating
the degree distributions in the asymptotic behavior by using the theoretical andnumerical analyses for diﬀerence equations and the corresponding continuous-time
approximation of diﬀerential equations with variables t and ki (t). We have derived
1
ki (t) ∼ t1−δ and p(k) ∼ k −(1+ 1−δ ) for the D-D and copying models under the invariant
ordering of degrees which is supported in randomly grown networks (Callaway etal., 2001). Moreover, for the copying model with positive degree–degree correlations,
we have shown that the numerical calculations of the diﬀerence equation give agood approximation of an estimated exponential distribution, even when an analytic
derivation is intractable. The copying model with positive degree–degree correlations
is related to the self-organization (Hayashi, 2014) of robust onion-like networks(Herrmann et al., 2011; Schneider et al., 2011; Tanizawa et al., 2012).
Our approach may be also applicable to data analysis for social networks, when
the observed time-course of degree is a monotone increasing function like powerlaw or logarithm in the average over samples by ignoring short-time ﬂuctuations,and a node index i or j represents an ordering of its birth time. This expectation
is supported as follows. It is helpful for grasping a trend to study the averagebehavior of many users (nodes) added at a same (sampling interval) time into a
network community. Random growth in a social network probably corresponds
to encountered chances among people. Moreover, as time goes by, the number ofhis/her friends for a member of social networks is usually increasing. It is naturalthat the connections to friends are maintained. However, we must consider the eﬀectof rewirings between old members in the deﬁnition of adjacency matrix. Also froma practical viewpoint, O(n2 ) space to store an adjacency matrix may cause a problem
for dig data.
From the conventional analysis for special network models to a general framework,
the representation by the ensemble average will open a door for investigating the

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10

Ensemble average of adjacency matrix

399

characteristic quantities, e.g. node degrees in growing networks. In particular, thetime-course of a quantity depending on the birth time of node is considered as a
key point. The discussion about other quantities such as clustering coeﬃcient or thenumber of paths of a given length requires further studies of how to analyze theaverage behavior related to the transitivity.
Acknowledgments
The author would like to thank anonymous reviewers for their valuable comments.
This research is supported in part by a Grant-in-Aid for Scientiﬁc Research inJapan, No. JP 25330100.
References
Albert, R., Jeong, H., & Babarási, A.-L. (2000). Error and attack tolerance of complex
networks. Nature, 406(6794), 378–382.
Babarási, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science,
286(5439), 509–512.
Babarási, A.-L., Albert, R., & Jeong, H. (1999). Mean-ﬁeld theory for scale-free random
networks. Physica A, 272(1–2), 173–187.
Callaway, D. S., Hopcroft, J. E., Kleinberg, J. M., Newman, M. E. J., & Strogatz, S. H. (2001).
Are randomly grown graphs really random?. Physical Review E, 64(4), 041902.
Hayashi, Y. (2014). Growing self-organized design of eﬃcient and robust
complexnetworks.
Proc. of 2014 IEEE 8th Int. Conf. on SASO: SelfAdaptive and Self-Organizing Systems, pp. 50–59. IEEE Xplore Digital Library,
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7001000, http://arxiv.org/abs/
1411.7719
Herrmann, H. J., Schneider, C. M., Moreira, A. A., Andrade Jr. J. S., & Havlin, S. (2011).
Onion-like network topology enhances robustness against malicious attacks. Journal of
Statistical Mechanics, Issue 01 P01027, doi: 10.1088/1742-5468/2011/01/P01027.
Kim, J., Krapivsky, P. L., & Redner, S. (2002). Inﬁnite-order percolation and giant ﬂuctuations
in a protein interaction networks. Physical Review E, 66(5), 055101(R).
Newman, M. E. J. (2003). Assortative mixing in networks. Physical Review Letters 89(20),208701.
Newman, M. E. J. (2010). Networks - an introduction. Oxford University Press, New York.
Pastor-Satorras, R., Smith, E., & Sole, R. V. (2003). Evolving protein interaction networks
through gene duplication. Journal of Theoretical Biology, 222(2), 199–210.
Schneider, C. M., Moreira, A. A., Andrade Jr. J. S., Havlin, S., & Herrmann, H. J. (2011).
Mitigation of malicious attacks on networks. Proceedings of the National Academy of
Sciences of the United States of America, 108(10), 3838–3841.
Sole, R. V., Pastor-Satorras, R., Smith, E., & Kepler, T. B. (2002). A model of large-scaleproteome evolution. Advances in Complex Systems, 5(1), 43–54.
Tanizawa, T., Havlin, S., & Stanley, H. E. (2012). Robustness of onionlike correlated networks
against targeted attacks. Physical Review E, 85(4), 046109.
Wu, Z.-X., & Holme, P. (2011). Onion structure and network robustness. Physical Review E,
84(2), 026106.

Downloaded from http:/www.cambridge.org/core. Japan Advanced Institute of Science and Technology (JAIST), on 08 Sep 2016 at 02:10:05, subject to the Cambridge
Core terms of use, available at http:/www.cambridge.org/core/terms. http://dx.doi.org/10.1017/nws.2016.10