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

SEMESTER 1, 2021 EXAMINATIONS

MATH3002 Network Science


1. The circular ladder L(n) on 2n vertices is the cubic graph consisting of two disjoint n-cycles {v0 , v1 , . . . , vn-1 } and {w0 , w1 , . . . , wn-1 } connected by the edges {viwi } for 0 ≤ i < n.         The picture shows the circular ladder L(5).

0

1

4

4

v2          v3

2

(a)  [2 marks] How many vertices and edges does L(5) have?

(b)  [2 marks] How many edges does L(n) have? (Give a formula in terms of n.)

(c)  [2 marks] Find a Hamilton cycle in L(5). (Either draw it on the graph or list the vertices in order.)

(d)  [2 marks] For which values of n is L(n) bipartite? (Explain briefly.)

(e)  [2 marks] Is L(5) isomorphic to the Petersen graph? (Explain your answer.)

2.   (a)  [2 marks] Explain whether or not there is a graph with degree sequence (4 , 4, 3, 2, 1). (Either give the graph as a list of edges, or show that no such graph exists.)

(b)  [3 marks]  Show that there is no bipartite graph with the degree sequence:

9, 6, 6, 6, 6, 6, 6, 3, 3, 3, 3, 3 .                                                -    ↘                                    -

6 times                5 times

(c)  [3 marks] How many spanning trees does the following graph have?

(d)  [2 marks] The tree T pictured below has the Laplacian spectrum (to 4 decimal places)

0.0000, 0.2232, 0.4919, 1.0000, 1.0000, 1.4712, 3.0000, 3.4838, 5.3298

Using this, or otherwise, determine the  Wiener index of T.

3.  Consider the following edge-weighted graph.

(a)  [3 marks] Use Dijkstra’s algorithm to find the shortest path tree with root vertex 0 (the

top-left vertex) in the edge-weighted graph drawn below.  (Either draw the tree on the graph, or list the edges in the tree.)

 


(b)  [2 marks] List the distance from 0 to each other vertex.  (Just write down 12 numbers

on one line, being the distance from 0 to 0, the distance from 0 to 1, the distance from 0 to 2, and so on, until the final value is the distance from 0 to b.)

(c)  [2 marks] Find a minimum spanning tree of the graph from the previous part of the question (which is reproduced below). State the weight of the minimum spanning tree, and either draw the tree on the graph, or list the edges in the minimum spanning tree.

(d)  [3 marks]  (*) If G is an edge-weighted graph where no two edges have the same weight, then show that G has a unique minimum spanning tree.

4.  Consider the following graph

Rounded to 3 decimal places, the Fiedler vector of this graph is

[」0.452, 」0.421, 」0.033, 0.225, 0.339, 0.332, 0.222, 0.196, 0.177, 」0.133, 」0.452].

(a)  [2 marks] Identify the partition of the vertices into weak nodal domains according to

Fiedler’s theory.

(b)  [3 marks] What is the isoperimetric ratio of the partition you found in the previous

part of this question?

(c)  [2 marks] What is the algebraic connectivity of this graph?

(d)  [3 marks]  (*) Let G be a graph on n vertices with a vertex of degree n 」1. Show that the Laplacian matrix of G has an eigenvector with eigenvalue n.

5.   (a)  [3 marks] Write down the adjacency matrix and the Laplacian matrix for the path P3 on 3 vertices.

(b)  [2 marks] Find an eigenvector for A(P3 ) with eigenvalue 0.

(c)  [2 marks] Determine the other eigenvalues of A(P3 ).

(d)  [3 marks]  (*) Show that the length of the shortest odd cycle of a graph is determined by its spectrum.

6. An example of a Windmill graph consists of n sails connected by a common vertex but no shared edges. For instance, a Windmill graph with n = 4 sails is shown below.

(a)  [3 marks]  Calculate the average clustering coefficient of the above Windmill graph with

n = 4 sails.

(b)  [3 marks]  Calculate the transitivity of the above Windmill graph with n = 4 sails.

(c)  [4 marks] Derive formulae for both the average clustering coefficient and transitivity of a general Windmill graph with n sails, and determine their limiting values as the number of sails n tends to infinity.

7.  Consider the graph shown below which is an incomplete realization of a BA preferential attachment algorithm.

Suppose a newcomer vertex has two edges to attach to existing vertices.

(a)  [3 marks] What is the preferential attachment probability of a degree 2 vertex, a degree

3 vertex, and a degree 4 vertex?

(b)  [5 marks] A newcomer vertex with three edges to assign to existing vertices is added

to the graph.  What is the probability that the resulting graph has K4  as an induced subgraph?

(c)  [2 marks] What is the closeness centrality of vertex 0?

8.  Consider an SIS epidemic process taking place on an infinite 7-regular graph where vertices have state 0 if they are susceptible and state  1 if they are infected.   Denote by pi   the probability of infection and by pr  the probability of recovery, and let qt  be the mean field variable denoting the density of 1’s in the graph at time t.

(a)  [4 marks] What is the state transition probability that a susceptible vertex at time t

remains susceptible at time t + 1? (Carefully explain your working.)

(b)  [2 marks] What is the state transition probability that an infected vertex at time t

remains infected at time t + 1? (Carefully explain your working.)

(c)  [4 marks] Derive a difference equation for the evolution of the mean eld qt , i.e., what is f (qt ) if qt+1  = f (qt )? (Briefly explain your reasoning.)

9.  Consider the graph shown below

(a)  [4 marks] What is the modularity of the following partition of vertices: {{0, 1}, {2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11}}?

(b)  [4 marks] Which of the two communities in Part (a) should be merged, if any, to produce

the maximum increase in modularity, and what is the new modularity score?

(c)  [2 marks] Which vertices have a zero value of betweenness centrality?  (Briefly explain your answer.)

10. A survey of a social club revealed the following friendship ties:

Ada         Sandy

Ada         Jessica

Jessica     Vincent

Vincent   Ada

Keith       Ada

Keith       Jessica

Sandy      Tracy

Tracy       Keith     

(a)  [2 marks] What is the network density of this friendship network?

(b)  [4 marks] What is the Modularity Matrix entry B(Keith,Vincent) ?

(c)  [4 marks] A disagreement over the admissions policy of the club leads to the breaking of existing friendship ties and the formation of new friendship ties.  A second survey discovers that Sandy is no longer friends with Tracy but is now friends with Jessica. Jessica is no longer friends with Vincent but Vincent and Tracy have become friends. Has this change of friendships resulted in an increase or decrease of the degree assortativity of the friendship network?  Explain your choice, but note that calculating a value of degree assortativity is not required.