Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH50007

BSc, MSci and MSc EXAMINATIONS (MATHEMATICS)

May-June 2021

Network Science

1.    In this question you will work with k-regular Cayley trees with diameter D .  Assume that k > 2 and that D > 2. The nodes with degree=1 are termed leaf nodes, and the root node is the node

that is equidistant from each leaf node.

(a)    Set k = 3 and D = 4.

(i)    Draw the graph (2 marks)

(ii)    What is the degree distribution for the graph? (2 marks)

(iii)    Assume  that  x1 ,  the  Katz  centrality  for  the  root  node,  has  been  computed  and  is

known.   Recall that the  Katz centrality for node i in a graph with adjacency matrix A is xi  = α    Aij xj + 1. Here, α is unknown, but assume that it has been chosen so that the solution is unique. Determine the Katz centralities of the leaf nodes. (3 marks)

(b)    Let G0  be a k-regular Cayley tree with k = 3 and D = 4, and let Gt  be the graph generated by

the Barabasi-Albert model after t iterations where: 1 link and 1 node are added per iteration, and G0  is the initial graph prior to the first iteration.

(i)    What is the probability that a link will be added to one of the leaf nodes in G0  during the first iteration? (2 marks)

(ii)    What is the expected number of nodes with degree=3 after 2 iterations? (6 marks)

(c)    Consider the following random graph model. Begin with a k-regular Cayley tree with diameter

D . Then, a link is randomly added between each distinct pair of leaf nodes with probability p.

(i)    What is the number of links in the graph when p = 1?                                   (2 marks)

(ii)    For general p, what is the expected degree of a node that is a leaf node in the initial Cayley tree?           (3 marks)

(Total: 20 marks)

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

N

x˙i  = β (xi _ α) _ α      Lij xj , i = 1, 2, . . . , N                                  (1)

j=1

or in vector form

x˙ = β (x _ αl) _ αLx                                                       (2)

where l is the N-element vector with all components equal to 1, and α 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 v1  = l is an eigenvector of L with eigenvalue 0. (1 mark)

(c)    Let S be a matrix whose columns are the eigenvectors of L, {v1 , v2 , . . . , vN }, with v1  = l. 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 αN which, when satisfied,  leads to synchronization of non-trivial

solutions of (1):  Ixi (t) _ xj (t)I _ 0 as t _ o.  Show that there is synchronization when this condition is satisfied.   (5 marks)

(Total: 20 marks)

3.   (a)    Consider three unweighted, undirected, connected graphs G1 , G2 , and G3  which do not have self-loops or multiedges.  Each graph has N nodes and l links, and graph Gi  has adjacency matrix Ai .  Let G be the graph that consists of G1 , G2 , and G3  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 G2  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 A1 , A2 , A3 (3 marks)

(ii)    Consider a partition of G into two parts (groups 1 and 2) defined by a vector v o R3N ,

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, {v1 , 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/2v  is an eigenvector of

, the normalized adjacency matrix of G :   = D- 1/2AD- 1/2  where D is the diagonal

degree matrix for G.  Provide the corresponding eigenvalue for this eigenvector. (7 marks)

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

πij  = Aij kj / _  Ail kl _

where Aij  is the adjacency matrix for the graph, and kj  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)

(iii)    Find the stationary  probability distribution,  po   o RN , for this  model.   Express your

solution in terms of the matrix Mij  = ki Aij kj  (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,

d (si )  = _β N  Ail (si xl )       (susceptible)

dt           l=1

 = µ (xi )       (recovered),

where xi (t) = 1 if node i is infectious at time t and xi (t) = 0 otherwise; si (t) = 1 if node i is susceptible at time t and si (t) = 0 otherwise; and ri (t) = 1 if node i is recovered with immunity at time t and ri (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 si (t) + xi (t) + ri (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 (xi 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) (xi (t)) . (4 marks)

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

d (xi xj )  = β N   [Ajl (xi sj xl ) + Ail (si xj xl )] ,

Construct a governing equation for (xi 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 (si (t)) and (ri (t)) for this modified model (note that the equation for (xi (t)) will remain unchanged). (6 marks)

(Total: 20 marks)