MATH6142 Complex Networks
Exam 2016
• Solution Problem 1
a) The network is directed because the adjacency matrix is not sym-
metric. (2 marks)[Unseen]
b) The network is shown in Figure 1.
(4 marks)[Unseen]
34
21
Figure 1: The directed network with adjacency matrix A.
c) The network contains two weakly connected components formed re-
spectivelly by the nodes {1, 2} and {3, 4}. (2
marks)[Unseen]
d) The network contains one strongly connected component formed by
the nodes {3, 4}. (2 marks)[Unseen]
e) The network does not have any out-component. (2 marks)[Unseen]
f) The in-degree sequence is fiven by {1, 0, 1, 1} the out-degree sequence
is given by {0, 1, 1, 1}.
(4 marks) [Unseen]
g) The in-degree distribution is given by P in(0) = 1/4, P in(1) = 3/4P in(k) =
0 for k = 2, 3.
(2 marks) [Unseen]
The out-degree distribution is given by P out(0) = 1/4, P out(1) =
3/4P out(k) = 0 for k = 2, 3.
(2 mark2) [Unseen]
h) The eigenvector centrality x can be found as following.
1
Given the initial guess x(0) = 1N 1 given by
x(0) =
1
4

1
1
1
1
 (1)
let us is calculate the result of the iteration
xn = Axn−1. (2)
We have
x(1) =

0 1 0 0
0 0 0 0
0 0 0 1
0 0 1 0
 14

1
1
1
1
 = 14

1
0
1
1
 .
(2 marks)[Unseen]
x(2) =

0 1 0 0
0 0 0 0
0 0 0 1
0 0 1 0
 14

1
0
1
1
 = 14

0
0
1
1
 .
(2 marks)[Unseen]
x(3) =

0 1 0 0
0 0 0 0
0 0 0 1
0 0 1 0
 14

0
0
1
1
 = 14

0
0
1
1
 .
Therefore
x(n) =
1
4

0
0
1
1
 . (3)
for every n ≥ 3. (2 marks)[Unseen]
It follows that
x =
1
2

0
0
1
1
 . (4)
(2 marks)[Unseen]
2
i) The result of point h) is expected because nodes 1 and 2 are in
an in-component of the network and therefore have zero eigenvector
centrality. Nodes 3 and node 4 instead have the same eigevcetor
centrality because they form a dimer. (2 marks)[Unseen]
– Solution Problem 2
a) The undirected network of N nodes with smallest diameter is the
complete graph, formed by N nodes each one connected to all the
others. The diameter of this network is D = 1. (2 marks)[Unseen]
This network has the small-world distance property. In fact
lim
N→∞
D
lnN
= lim
N→∞
1
lnN
= 0. (5)
(3 marks)[Bookwork]
b) The undirected network of N nodes which is connected and has the
largest diameter is the (open) linear chain of N nodes that has di-
ameter D = N − 1. (2 marks)[Unseen]
This network does not have the small-world distance property. In
fact
lim
N→∞
D
lnN
= lim
N→∞
N
lnN
=∞. (6)
(3 marks)[Bookwork]
c) i) The degree distribution P (k) of the Poisson network with average
degree 〈k〉 = c = 4 is given by
P (k) =
1
k!
cke−c. (7)
(1 marks)[Bookwork]
The generating function G(x) is given by
G(x) =
∞∑
k=0
P (k)xk = e−c+cx. (8)
(2 marks)[Bookwork]
The first and second moment of the Poisson degree distribution
can be obtained by differentiating the generating function G(x).
In particular we have
〈k〉 = dGB(x)
dx
∣∣∣∣
x=1
= c
〈k(k − 1)〉 = d
2GB(x)
dx2
∣∣∣∣
x=1
= c2. (9)
3
(2 marks)[Bookwork]
It follows that
〈b〉 = 〈k(k − 1)〉〈k〉 = c = 4. (10)
(1 marks)[Bookwork]
ii) Using the result of point i) we get
Nd ' 〈k〉
( 〈k(k − 1)〉
〈k〉
)d−1
= 〈k〉d (11)
(2 marks)[Bookwork]
Therefore
Nd ' 4d. (12)
(1 marks)[Unseen]
iii) Since at distance d = 0 from the random node there is only one
node (the node itself) we have
Nd ' 4d (13)
for 0 ≤ d. (1 marks)[Unseen]
The total number of nodes Nd≤` at distance 0 ≤ d ≤ ` from any
random node of the Poisson network is given by
Nd≤` =
∑`
d=0
4d =
4`+1 − 1
4− 1 . (14)
(2 marks)[Unseen]
Therefore we have
N =
1
3
[
4`+1 − 1] (15)
(1 marks)[Unseen]
iv) By imposing that all the nodes of the network are found at dis-
tance d ≤ ` from a random node we have
N = Nd≤` =
1
3
[
4`+1 − 1] (1marks)
3N = 4`+1 − 1(1mark)
3N + 1 = 4`+1(1mark)
` =
1
2 ln 2
ln [3N + 1]− 1.(1mark) (16)
4
v) Using Eq. (16) and considering the leading term for N 1 we
have
` ' ln[3N ]
2 ln 2
' lnN
2 ln 2
. (17)
(4 marks) [Unseen]
vi) The local clustering coefficient Ci of a generic node i of a Poisson
network can be estimated to be
Ci =
Number of triangles passing through node i
ki(ki − 1)/2
' pki(ki − 1)/2
ki(ki − 1)/2 (18)
where ki is the degree of node i and p = 〈k〉/N is the probability
of a link between any two nodes of the network. (2 marks)
[Bookwork]
In fact each node i belongs in average to pki(ki − 1)/2 triangles
since any pair of its neighbor is connected with probability p. (2
marks) [Bookwork]
• Solution Problem 3
a) The average number of links Π˜i added to node i in timestep t is given
by
Π˜i =
N∑
r=1
pi(i,r) =
N∑
r=1
Air
L
. (19)
(2 marks) [Unseen]
Using
L =
1
2
N∑
j=1
kj
ki =
N∑
r=1
Air (20)
we get
Π˜i =
2ki∑N
j=1 kj
(21)
(4 marks) [Unseen]
b)Since initially the number of links is m0 = 1 and at each time we add
5
two links we have L = 1 + 2t. (1 mark) [Unseen]
Since initially we have n0 = 2 nodes and at each time we add a node we
have N = 2 + t. (1 mark) [Unseen]
c)The average degree 〈k〉 is given by
〈k〉 = 2L
N
=
2(1 + 2t)
2 + t
. (22)
(4 marks) [Bookwork]
d)In the mean-field approximation, the degree ki(t) of node i at time t
satisfies the following differential equation
dki(t)
dt
= Π˜i =
2ki∑N
j=1 kj
(23)
(2 marks)[Bookwork]
In the limit t 1, we have ∑j kj = 2L ' 4t. Therefore we can write the
dynamical mean-field equation for the degree ki(t) of node i, getting
dki
dt
=
2ki
4t
=
ki
2t
, (24)
with initial condition ki(ti) = 2. (2 marks)[Bookwork]
This equation has solution
ki(t) = 2
(
t
ti
)1/2
. (25)
(2 marks)[Bookwork]
e) The probability P (ki(t) > k) that a random node has degree ki(t) > k,
in the mean-field approximation can be calculated as follows
P (ki(t) > k) = P
(
2
(
t
ti
)(1/2)
> k
)
= P
(
ti < t
(
2
k
)2)
=
(
2
k
)2
. (26)
(3 marks)[Bookwork]
Therefore, the degree distribution P (k) is given by
P (k) =
dP (ki(t) < k)
dk
= − d
dk
(
2
k
)2
=
(
2
k
)3
. (27)
(3 marks)[Bookwork]
f) The master equation for Nk(t) reads
Nk(t+ 1) = Nk(t) +
k − 1
2t
Nk−1(t)(1− δk,2)− k2tNk(t) + δk,2 (28)
6
(3 marks)[Bookwork]
g) Assuming Nk(t) ' (t+ n0)P (k) for large t
1 we get
P (k) =
k − 1
2
P (k − 1)(1− δk,2)− k2P (k) + δk,2. (29)
(3 marks)[Bookwork]
giving
P (k) =
k − 1
k + 2
P (k − 1) (30)
for k > 2 and
P (2) =
1
2
. (31)
(3 marks)[Bookwork]
Solving these equations we get
P (k) =
12
k(k + 1)(k + 2)
. (32)
(2 marks)[Bookwork]
7