A

B

C

The Laplacian spectra for each graph, although not necessarily in the same order, are

1 :      [0.0, 1.19, 3.0, 3.47, 5.0, 5.34]

2 :      [0.0, 1.0, 2.0, 3.0, 3.0, 5.0]

3 :      [0.0, 3.0, 3.0, 5.0, 5.0, 6.0]

i. Match the spectra to the graph and provide an explanation for your choice based on the connectivity of the graphs. For example, A–1 etc.

 ii. Identify the Fiedler gaps of each spectra and rank the graphs from slowest to fastest ac- cording to how quickly a diffusion process on the graph will reach steady state.  (You can just order the numbers 1 through 3 correctly.)

(c)  Consider the ordinary differential equation

dc

Determine the location of all equilibrium points and classify their stability.

2.   (a)  Suppose five different probes record measurements of a process to obtain five different time series. The correlation matrix whose (ij) entry is the correlation coefficient between time series i and time series j is given by

The correlation matrix can be converted to an adjacency matrix by applying a threshold ε such that Aij  = 1 if Cij  > ε. Note, we set Aii  = 0.

Determine thresholds such that

i. the resulting graph has degree sequence [1, 1, 1, 1, 0] and

ii. the resulting graph has degree sequence [3, 3, 2, 1, 1].

 (b)  Consider the graph drawn below

Calculate the (local) clustering coefficient of each vertex and construct a new graph with the same vertex set but where edges connect vertices with the same value of clustering coefficient. (Either draw the graph with clearly labelled vertices, or describe how vertices are connected.)

3. The six connected four-vertex

A

graphs are

C

D

E

F

(a) Determine how many occurrences of each are induced subgraphs in the graph G shown below.

Induced subgraph         Total number

A

B

C

D

E

F

(b) For the graph G above which two edges should be selected for a double edge swap, and how

should they be re-wired, such that the resulting graph has K4 as an induced subgraph? Describe the resulting graph.

(c) How many triangles are there in Kn ?

4.  Consider a modified majority rule process on an infinite 5-regular graph where vertex states are either 0 or 1.  When determining the next state of a vertex, only the states of its neighbours are considered, and not its own state.

(a) If qt is the mean-field measuring the probability of a vertex state being 1 at time t then complete

the following state transition table:

Current State

Neigbours’

State

Next

State

Probability of

transition

(b) By using the above table write down a difference equation for qt+1  as a function of qt .

(c)  Consider the first-order difference equation

qt+1  = qt(3) + 3qt(2) - 3.

Determine the fixed points and their stability.