King’s College London

University Of London

This paper is part of an examination of the College counting towards the award of a degree.
Examinations are governed by the College Regulations under the authority of the Academic
Board.

PLACE this paper and any answer booklets in the EXAM ENVELOPE provided

Candidate No: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Desk No: . . . . . . . . . . . . . . . . . . . . . . .

MSc and MSci Examination

7CCMCS02/7CCMCS02U Theory of Complex Networks

Summer 2023

Time Allowed: Two Hours

This paper consists of two sections, Section A and Section B.

Section A contributes half of the total marks for the paper.
Answer all questions in Section A.
All questions in Section B carry equal marks, but if more than TWO questions
are attempted, then only the best two will count.

NO calculators are permitted.

DO NOT REMOVE THIS PAPER

FROM THE EXAMINATION ROOM
TURN OVER WHEN INSTRUCTED

2023 ©King’s College London

 7CCMCS02/7CCMCS02U

Section A

A 1. Consider a nondirected, N -node graph G represented by an adjacency matrix

A of dimensions N × N . Use the adjacency matrix A to define the following
graph theoretical quantities. Provide complete and precise definitions.

(a) [3 points] a simple (nondirected) graph;

(b) [3 points] the distribution p(k|A) of the degrees of nodes obtained by

sampling uniformly and randomly nodes from the set of vertices of the
graph represented by A;

(c) [4 points] the degree distribution W (k|A) of the degrees of nodes that are
the end points of edges selected uniformly and randomly from the set of
edges of the graph represented by A.

1 2 3 4

5 6

Figure 1: Graphical representation of a graph with 6 nodes.

A 2. Consider the graph in Figure 1, represented by the adjacency matrix A1 . Answer

the questions below:

(a) [5 points] show that the graph with adjacency matrix A1 is bipartite;

(b) [5 points] determine the degree distribution p(k|A1 );

(c) [5 points] determine the degree distribution W (k|A1 ).

-2- See Next Page

 7CCMCS02/7CCMCS02U

3 2 1 4

6 5

Figure 2: Graphical representation of a graph with 6 nodes, represented by A2 .

A 3. Let A be the adjacency matrix of an N -node graph that is a tree. Prove the
following claims.

(a) [5 points] The cluster coefficient Ci (A) of an arbitrary node i ∈ {1, 2, . . . , N }

is equal to zero.

(b) [15 points] Suppose that there exists a node of degree k, say node 1, such
that its removal would divide the tree into k isolated trees of sizes N1 , N2 ,
. . ., and Nk , with N = N1 + N2 + . . . + Nk + 1. Show that the betweenness
centrality of this node is
k
X
2
y1 (A) = N − Nα2 . (1)
α=1

(c) [5 points] Use Eq. (1) to determine the betweenness centrality y1 (A2 ) of
node 1 in the graph of Fig. 2.

-3- See Next Page

 7CCMCS02/7CCMCS02U

5 1 3

Figure 3: A star graph of 5 nodes.

Section B
B 4. Consider the linear voter model
N
d X
si = Aij sj − λsi (2)
dt j=1

with i ∈ {1, 2, . . . , N }, defined on a nondirected graph of N vertices and rep-

resented by the adjacency matrix A with entries Aij . The decay parameter
λ ∈ R+ , si (t) ∈ R, and t ≥ 0 is the time index.
(a) [10 points] Show that the solution s(t) of Eq. (2), which is the column
vector with entries si (t), is given by
N
X
s(t) = (êk · s(0))e(µk −λ)t êk , (3)
k=1
k
where ê , k = 1, 2, . . . , N are a set of orthonormal eigenvectors of the
adjacency matrix A, and µk are the corresponding eigenvalues.

(b) [5 points] Show that when λ > µmax , with µmax the largest eigenvalue of
A, then s(t) converges to zero as a function of t, i.e., limt→∞ s(t) = 0.

(c) [10 points] Determine the eigenvectors of the star graph shown in Fig. 3,
assuming that its eigenvalues are given by {2, −2, 0}. Subsequently, use
the obtained expressions for the eigenvalues and eigenvectors to show that
 
2 cosh(2t)
 sinh(2t) 
1 −λt  
s(t) = e  sinh(2t) 
 
2  
 sinh(2t) 
sinh(2t)
for all t ≥ 0, when the initial state s(0) = (1, 0, 0, 0, 0)T .

-4- See Next Page

 7CCMCS02/7CCMCS02U

B 5. Consider the random graph ensemble that assigns probabilities

1
p(A; N ) =
N
to all A that belong to the set G of adjacency matrices of nondirected, simple
N -node graphs. Here, N is a normalisation constant such that
X
p(A; N ) = 1.
A∈G

(a) [5 points] Determine the normalisation N .

(b) [4 points] What probability does the ensemble assign to the graph shown
in Figure 2.

(c) [5 points] Show that the ensemble averaged mean degree,

X
hk(A)i = p(A; N )k(A)
A∈G

is given by
N −1
hk(A)i = .
2

(d) [6 points] Show that the average number of triangles incident to a node i
equals

(N − 1)(N − 2)
hTi (A)i = ,
16
where
N N
1 X X
Ti (A) = Aij Aj` A`i .
2 j=1;j6=i `=1;`6=i,j

(e) [5 points] Consider the Erdős-Rényi ensemble that assigns probabilities

N Y
Y i−1
∗
 ?
p δAij ,1 + (1 − p? )δAij ,0

pER (A; p , N ) =
i=1 j=1

to nondirected, simple graphs. Show that for a specific value of p? the two
ensembles pER (A; p∗ , N ) and p(A; N ) are identical

-5- See Next Page

 7CCMCS02/7CCMCS02U

B 6. Consider an infinitely large, random graph with a prescribed degree distribution

pα,c (k) that is defined through its generating function
Gα,c (x) = αx + (1 − α) exp (−c(1 − x)) ,
where α ∈ [0, 1] and c ∈ R+ .

(a) [4 points] Derive an explicit expression for the degree distribution pα,c (k)
that is determined by the generating function Gα,c (x).

(b) [4 points] Derive an explicit expression for the mean degree hki and the
second moment hk 2 i of the distribution pα,c (k) as a function of α and c.

(c) [4 points] By using the Molloy-Reed condition, show that for each value
of c > 1 the critical parameter α∗ (c) at which a giant component emerges
in random graphs with a prescribed degree distribution pα,c (k) is given by
c(c − 1)
α∗ (c) = .
1 + c(c − 1)

(d) [4 points] Show that for c < 1 infinitely large, random graphs with a
prescribed degree distribution pα,c (k) do not have a giant component, i.e.,
a connected subgraph that contains a nonzero fraction of the nodes.

(e) [5 points] Use the theorem of Molloy and Reed that we have seen in the
lecture notes, to show that the fraction of nodes f in the largest connected
component is given by
f = 1 − αy − (1 − α) exp (−c(1 − y)) ,
where y is the smallest nonnegative solution of
α + c(1 − α) exp (−c(1 − y))
y= .
α + c(1 − α)

(f ) [4 points] Show that near the percolation transition the fraction of nodes
f that belong to the largest connected component is given by
f = [c(1 − α) + α]g(α, c) + O(g 2 )
with
[1 + c(c − 1)](α∗ (c) − α)
g(α, c) = ,
(1 − α)c3
and where O(g 2 ) indicates that we neglect terms that are quadratic or of
higher order in g.

-6- Final Page