1.

(a)    Consider the graph, G, which corresponds to the following adjacency matrix,

l                        」

0   0   0   1   0

A =   1   0   0   0   1  .

0   1   0   0   0

「1   0   1   0   0

(i)    Draw the graph G.

(ii)    What is the Laplacian matrix, L, for G?

(iii)    Consider the scaled Laplacian defined as  = M− 1 LM with M ∈ R5x5 . Give a matrix M such that v = [1, 1, 1, 0, 0]T  is an eigenvector of , and include the reasoning used to construct the matrix.

What is the eigenvalue that corresponds to v?                                                                  (5 marks)

(b)    Let G correspond to a simple graph with N nodes and L links.

(i)    Consider a partition of the graph G where all N nodes are placed in a single set.  Show that the modularity of this partition is zero.  (4 marks)

(ii)    Now assume that G consists of two connected components.  Show that any partition of G which

assigns each node in G to one of two disjoint sets cannot have a modularity greater than  .   (6 marks)

(Total: 20 marks)

2.

(a)    Consider   N-node   graphs   generated   by   the   configuration   model   with   degree   sequence, d = {k1 , k2 , k3 , ..., kN } , where the sum of the degrees, K , is even.

(i)    Assume that k1  = 1. What is the probability that node 1 will be linked with node N?    (2 marks)

(ii)    Show that the probability that a graph will have one or more self-loops is at most )()   (6 marks)

(b)    Consider the following random graph model which progresses iteratively by removing one link at

each iteration. Begin with a complete graph, G0 , with N nodes and (2(N)) links. At each iteration, choose a link uniformly at random and remove it.

(i)    What will the degree distribution be after the first iteration?                                         (2 marks) (ii)    Determine ⟨ki (t = 1)⟩, the expected degree of node i after the first iteration                 (5 marks)

(iii)    For a graph generated after the tth  iteration, let Nk (t) be the number of nodes with degree k, and let Lk (t) be the number of links connecting a node pair where both nodes have degree k .  Given Nk (t) and Lk (t) for all k, compute ⟨N0 (t + 1)⟩, the expected number of nodes with degree zero

after the (t + 1)th  iteration.                                                                                               (5 marks)

(Total: 20 marks)

3.    Consider the following system of N differential equations:

dt                           j=1                    j=1 l=1

or in matrix-vector form:

 x,                                                    (2)

where x and y are N-element vectors, and the ith  element of y is yi  = xi(2) .  The initial condition is x(t = 0) = x0 , L is the Laplacian matrix for a simple graph with N nodes, the parameter µ is a non-negative constant, and you should assume that a complete set of mutually orthogonal eigenvectors for L, {v1 , v2 , ..., vN }, along with their corresponding eigenvalues are given.

(a)    Say that at time t = τ , xi  = µ for i = 1, 2, ..., N . Show that dt(d北)i    = 0 at t = τ for all i.

(5 marks)

(b)    Let xi  = µ + ϵui (t) for all i. Show that in the limit ϵ → 0, the N-element vector, u, satisfies the

following system of ODEs:

 u.                                                   (3)

(4 marks)

(c)    Let w = Mu where u satisfies (3).  Find a matrix M such that w satisfies a nontrivial decoupled

system of ODEs,

 = aiwi , i = 1, 2, ..., N,

and carefully explain what ai  should be for all i.                                                            (6 marks)

(d)    Let u(t) satisfy (3), let E (t) = u(t)T u(t), and assume that the initial condition u(t = 0) = u0 , is constrained to have length 1 (u0(T)u0   =  1).   Find the maximum possible value of E (t = t1 ) where t1  > 0 in terms of t1 , µ and ρ(L) where ρ(L) is the spectral radius of L.  Include a careful explanation of your reasoning.                                                                                        (5 marks)

(Total: 20 marks)

4.    Consider the spread of an infectious disease on an N-node simple graph, G, with adjacency matrix,

A. There are three state variables for each node, si (t), xi (t), and yi (t), i = 1, 2, ..., N, and each variable can be 0 or 1. A node is either susceptible (si  = 1), infected but not contagious (yi  = 1), or contagious (xi  = 1). The master equations are:

N

P (xi (t + ∆t) = 1) = P (xi (t) = 1)+β∆t工 Aij [P (si (t) = 1, xj (t) = 1)]+µ∆tP (yi (t) = 1)+O(∆t2 ),

j=1

N

P (si (t + ∆t) = 1) = P (si (t) = 1) − ∆t工 Aij [(β + γ) P (si (t) = 1, xj (t) = 1)] + O(∆t2 ),

j=1

(1b) and we require, si (t) + xi (t) + yi (t) = 1 for all nodes at all times.  The parameters β , γ, and µ are non-negative constants.

(a)    Show that ⟨xiyj ⟩ = P (xi  = 1, yj  = 1) and ⟨sixj ⟩−⟨sixj sl ⟩−⟨sixj xl ⟩ = P (si  = 1, xj  = 1, yl  = 1).

Note that all quantities are evaluated at time, t.                                                               (5 marks)

(b)    Apply the limit ∆t → 0 to this model, and derive an ODE for ⟨yi ⟩ of the form

 = RHS,

where RHS consists of some or all of: first and second moments of the state variables (including

mixed moments), the adjacency matrix, and the model parameters (β , γ , µ).                 (6 marks)

(c)    Say that G is a complete graph, and let x =  对 ⟨xi ⟩ and x2  =  对 (⟨xi ⟩2 ) . Assume that (北(北)2)2   ≪ N . Show that,

N    N

工 工 (⟨xi ⟩ Aij ⟨xj ⟩) ≈ N2 x2 .

i=1 j=1

(5 marks)

(d)    Consider the third moment, ⟨yi sj xl ⟩ .  Assuming that the states of nodes i and l are statistically independent, carefully show that ⟨yi sj xl ⟩ can be restated as an expression containing only first and second moments                                                                                                            (4 marks)

(Total: 20 marks)