Main Examination period 2017
MTH6142 / MTH6142P
Complex networks
Duration: 2 hours
Apart from this page, you are not permitted to read the contents of this
question paper until instructed to do so by an invigilator.
You should attempt ALL questions. Marks available are shown
next to the questions.
Calculators are not permitted in this examination. The unauthorised use of a
calculator constitutes an examination offence.
Complete all rough work in the answer book and cross through any work that is not
to be assessed.
Possession of unauthorised material at any time when under examination
conditions is an assessment offence and can lead to expulsion from QMUL. Check
now to ensure you do not have any notes, mobile phones, smartwatches or
unauthorised electronic devices on your person. If you do, raise your hand and give
them to an invigilator immediately.
It is also an offence to have any writing of any kind on your person, including on
your body. If you are found to have hidden unauthorised material elsewhere,
including toilets and cloakrooms, it shall be treated as being found in your
possession. Unauthorised material found on your mobile phone or other electronic
device will be considered the same as being in possession of paper notes. A mobile
phone that causes a disruption in the exam is also an assessment offence.
Exam papers must not be removed from the examination room.
Examiners: G. Bianconi & V. Latora
c© Queen Mary University of London (2017) Turn Over
Page 2 MTH6142 / MTH6142P (2017)
Question 1. [30 marks]
Structural properties of a given network.
Consider the adjacency matrix A of a network of size N = 4 given by
A =

0 1 0 0
0 0 0 0
0 0 0 1
0 0 1 0
 .
a) Is the network directed or undirected? (Justify your answer) [2]
b) Draw the network. [4]
c) How many weakly connected components are there in the network? Which
are the nodes in each weakly connected component? [2]
d) How many strongly connected components are there in the network? Which
are the nodes in each strongly connected component? [2]
e) Is there an out-component in the network? If yes, indicate the nodes in the
out-component of the network. [2]
f) Determine the in-degree sequence {kin1 , kin2 , kin3 , kin4 } and the out-degree
sequence {kout1 , kout2 , kout3 , kout4 }. [4]
g) Determine the in-degree distribution P in(k) and the out-degree distribution
P out(k). [4]
h) Calculate the eigenvector centrality xi of each node i = 1, 2, . . . , N of the
network with adjacency matrix A given by Eq. (1).
To this end start from the initial guess x(0) = 1
N
1 where 1 is the
N -dimensional column vector of elements 1i = 1 ∀i = 1, 2 . . . , N .
Consider the iteration
x(n) = Ax(n−1)
for n ∈ N.
Finally evaluate the eigenvector centrality xi of each node i of the network
by calculating the limit
xi = lim
n→∞
x
(n)
i∑N
j=1 x
(n)
j
.
[8]
i) Is the result obtained in point h) expected? (Why?) [2]
c© Queen Mary University of London (2017)
MTH6142 / MTH6142P (2017) Page 3
Question 2. [35 marks]
Diameter and clustering coefficient of networks
a) Which is the undirected network of N nodes with smallest diameter?
Does this network have the small-world distance property? Why? [5]
b) Which is the undirected network of N nodes which is connected and has the
largest diameter?
Does this network have the small-world distance property? Why? [5]
c) Consider a random Poisson network with average degree 〈k〉 = 4 and total
number of nodes N .
Indicate with ` the average shortest path in the network.
i) Using the properties of the generating function evaluate the average
branching ratio of a node reached by following a link given by
〈b〉 = 〈k(k−1)〉〈k〉 . [6]
ii) Approximate the number of nodes Nd at distance d ≥ 1 from a random
node of the network as Nd = 〈k〉
(
〈k(k−1)〉
〈k〉
)d−1
and show that Nd = 4d. [3]
iii) Using the properties of the geometric sum, evaluate the total number
Nd≤` of nodes at distance 0 ≤ d ≤ ` from a random node of the
network. [4]
iv) Impose that all the nodes of the Poisson network can be found within a
distance d ≤ ` from any random node. Using the result obtained in (ii),
express the average distance ` of the Poisson network in terms of the
total number of nodes N . [4]
v) Consider the expression found in (iii).
Find the leading term of ` in terms of the total number of nodes N in
the network, when N 1. [4]
vi) Estimate the local clustering coefficient of a generic node of the
network. [4]
c© Queen Mary University of London (2017) Turn Over
Page 4 MTH6142 / MTH6142P (2017)
Question 3. [35 marks]
Growing network model
Consider the following model for a growing simple network.
We adopt the following notation: N and L indicate respectively the total number of
nodes and links of the network, Air indicates the generic element of the adjacency
matrix A of the network and ki indicates the degree of node i.
At time t = 0 the network is formed by a n0 = 2 nodes and a single link (initial
number of links m0 = 1) connecting the two nodes.
At every time step t > 0 the network evolve according to the following rules:
- A single new node joins the network.
- A link (i, r) between a node i and a node r is chosen randomly with uniform
probability
pi(i,r) =
Ai,r
L
and the new node is linked to both node i and node r.
a) Show that in this network evolution at each time step the average number of
links Π˜i added to node i follows the preferential attachment rule, i.e.
Π˜i =
N∑
r=1
pi(i,r) = 2
ki∑N
j=1 kj
.
[6]
b) What is the total number of links in the network at time t? What is the total
number of nodes? [2]
c) What is the average degree 〈k〉 of the network at time t? [4]
d) Use the result at point a) to derive the time evolution ki = ki(t) of the average
degree ki of a node i for t 1 in the mean-field, continuous approximation. [6]
e) What is the degree distribution of the network at large times in the mean-field
approximation? [6]
f) Let Nk(t) be the average number of nodes with degree k at time t.
Write the master equation satisfied by Nk(t). [3]
g) Solve the master equation, finding the exact result for the degree distribution
P (k) in the limit N →∞. [8]
End of Paper.
c© Queen Mary University of London (2017)