MATH50007 Network Science 2022
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 2022
Network Science
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)
2022-08-19