2.  Consider a complete graph, G, with N nodes. Let A be its adjacency matrix, and let L be its Laplacian. You are given that the eigenvalues of L are 0,N,...,N. Consider the ODE

(1)

or in vector form

x=β(x-a1)-αLx                                                              (2) where 1 is the N-element vector with all components equal to 1, and a and β are positive constants.

(a)   Show that for a complete graph, Ax = Nx-x and Lx = N(x-x) where x is the average of the elements in x. (4 marks)

(b)    Show that vi = 1 is an eigenvector of L with eigenvalue 0. (1 mark)

(c)    Let S be a matrix whose columns are the eigenvectors of L,{Vi,V2, … ,Vv},with vi =1. Let x =Sw,and show that (2) gives

w=Bw+c                                                                 (3)

where B is a diagonal matrix, and c is a N-element vector whose elements are constants. Clearly describe what the elements of B and c should be. (6 marks)

(d)   Given the initial condition, w(t =0), find the solution, w(t), of equation (3). (4 marks)

(e)   Provide a condition for aN which, when satisfied, leads to synchronization of non-trivial solutions of (1):|x;(t)-x;(t)|→0as t → x. Show that there is synchronization when this condition is satisfied. (5 marks)

(Total: 20 marks)

3.(a)       Consider three unweighted, undirected, connected graphs Gi,G₂ , and Gʒ which do not have

self-loops or multiedges. Each graph has N nodes and l links, and graph G; has adjacency matrix Aj. Let G be the graph that consists of Gi, Gz, and Gʒ collected together (so G is the disjoint union of the three graphs and will have 3N nodes and 3l links). The nodes in G that correspond to G1 are numbered from 1 to N; nodes corresponding to G₂ are numbered from N+1 to 2N, and the nodes corresponding to G3 are numbered from 2N+1 to 3N.

(i)   What is the adjacency matrix for G? Give your answer in terms of a block matrix which includes the three adjacency matrices A₁ ,Az,A₃ (3 marks)

(i)    Consider a partition of G into two parts (groups 1 and 2) defined by a vector v ∈ R³N, where the ith element of v is 1 if node i is in group 1 and is 0 if node i is in group

2. Provide three mutually orthogonal vectors,{vi,V2,V3} which each correspond to a partition which minimizes the cut size. Each partition should also have at least one node in each group, and group 2 should have more nodes than group 1.

For any one of the three vectors you have found, show that D1/2y is an eigenvector of A, the normalized adjacency matrix of G:A =D- 1/2AD- 1/2 where D is the diagonal degree matrix for G. Provide the corresponding eigenvalue for this eigenvector. (7 marks)

(b)    Consider the following definition of a random walk on a unweighted, undirected, connected graph, G, with N nodes which does not have self-loops or multiedges. A walker at node i takes a step to node j with transition probability

where Aij is the adjacency matrix for the graph, and hj is the degree of node j.

(i)    Provide a concise (1-2 sentence) interpretation of this random walk model. (2 marks)

(ii)    Show that this model is equivalent to the standard model for random walks on unweighted graphs when G is a complete graph. (3 marks)

(i)      Find the stationary probability distribution, P ∈ RN, for this model. Express your

solution in terms of the matrix M,j = k;Ajh;(matrix-vector form is not required). (5 marks)

(Total: 20 marks)

4. Let A be the adjacency matrix for an N-node unweighted, undirected, connected graph with no self-loops or multiedges. The network-SIR model equations for this graph are,

(susceptible)

(infectious)

(recovered),

where x;(t)=1 if node i is infectious at time t and x;(t)= 0 otherwise; s;(t)= 1 if node i is susceptible at time t and s;(t)=0 otherwise; and ri(t)= 1 if node i is recovered with immunity at time t and r;(t)=0 otherwise. The probability that a node which is susceptible at time t becomes infectious at time t + △t via a link to an infectious node is β △t, and the probability that a node which is infectious at time t becomes recovered at time t + △t is μ △t. Note that s;(t)+x;(t)+r;(t)=1.

(a)   Show that any infection-free state is an equilibrium state for the system. (2 marks)

(b)   Provide a concise (1-3 lines) interpretation of the expression (x;xj}/{xj〉= 1 in terms of the states of nodes i and j and how they relate to each other. (2 marks)

(c)   Show that the probability that a node is infectious at both times t and t + △t is (1- μ △t)(4 marks)

(d)    Recall that for the network-SI model, the governing equation for the second moment,(x;xj) is,

Construct a governing equation for {x;xj} for the network-SIR model and compare the terms on the right-hand-side of your final equation to those in the 2nd-moment equation for the network-SI         model. (6 marks)

(e)    Consider the following modification to the network-SIR model above. The probability that a node that is susceptible at time t is vaccinated and becomes recovered at time t+ △t is γ △t. Derive the governing ODEs for (s;(t)〉and 〈r;(t)〉 for this modified model (note that the equation for (x;(t)〉 will remain unchanged). (6 marks)

(Total: 20 marks)