King’s College London
UNIVERSITY OF LONDON
This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
MSc EXAMINATION
7CCSMNTH Network Theory
Period 2 (May/June 2017)
TIME ALLOWED: THREE HOURS ANSWER FOUR QUESTIONS
IF MORE QUESTIONS ARE ANSWERED, THE FIRST FOUR WILL BE CONSIDERED.
ANSWER EACH QUESTION IN A SEPARATE ANSWER BOOK AND WRITE ITS NUMBER ON THE COVER.
CALCULATORS MAY BE USED. THE FOLLOWING MODELS ARE PERMITTED:
Casio fx83
Casio fx85.
DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
TURN OVER WHEN INSTRUCTED 2017 © King’s College London
1.
Question one
a) In the network of Figure 1:
i. Find a minimal spanning tree, using the Prim’s algorithm.
[5 marks]
ii. Does this network have a unique minimal spanning tree?
If not, how many minimal spanning tree does it have?
[5 marks]
iii. Starting from node A, find the shortest path for reaching all nodes, using Dijkstra.
[5 marks]
Figure 1: Graph for question 1.a
b) Show that there’s no simple graph with six vertices of which the degrees of five vertices are 5, 5, 3, 2 and 1.
[5 marks] c) Find the fewest vertices needed to construct a complete
7CCSMNTH
graph with at least 1000 edges.
[5 marks]
[Total 25 marks] See Next Page
2
2. Question two
a) Consider three different server organisations (Figure 2), explained below, all having total arrival rate λ and total service rate kμ.
1. FDM: Under Frequency Division Multiplexing (FDM), traffic is split into k separate channels.
2. M/M/k: Under M/M/k, the traffic is lumped together but the service capacity is split.
3. M/M/1: Under M/M/1, nothing is split.
i. Which of these three server organisations can serve their customers faster? Why?
[5 marks]
ii. What is the average waiting time in each of the three queuing systems?
[5 marks]
7CCSMNTH
(1) (2) (3) Figure 2. Three server organisations
See Next Page
3
Continue Question 2
b)Consider a closed system with multiple queues and probabilistic routing between the queues, as seen in Figure 3.
i. Write down all the possible states that represent this queueing system.
[5 marks]
ii. Draw the Markov chain and show the transition probabilities
between different states.
[5 marks]
iii. Determine the probability that there are 2 jobs at server
three (the server with service rate μ3).
[5 marks]
Figure 3. Closed queuing system of question 2.b
[Total 25 Marks]
7CCSMNTH
See next page
4
3. Question three
a) Consider problem (P1) to be, (P1): Minimise f(x)
7CCSMNTH
for i = 1, …, m
for i = 1, …, n
i.
ii.
Write the Lagrangian dual problem of (P1).
Subject to gi(x) ≤ 0 hi(x) = 0
Reformulate (P1) to an unconstrained problem using the Logarithmic Barrier method.
[5 marks] b) Consider the network diagram shown in Figure 4. Assume the links’ weights represent cost of transmitting one unit of flow over that link, denoted by cij. Assume source node S has 10 units of flow to transmit to the destination node T, and all the links have the capacity of one unit of flow. Formulate the problem that minimises the transmission cost from S to T in this network (the Minimum Cost Flow
problem).
[5 marks]
Figure 4. Network diagram of question 3.b and 3.c
See next page
[5 marks]
5
c) Assume that the network diagram in Figure 4 shows the network topology between different departments at KCL. The Ethernet links between every two departments have different capacities that can be seen in the figure (in Mbps).
i. What is the maximum data rate we can transmit from department S to department T?
[5 marks]
ii. How should we route this data from S to T?
[5 marks]
[Total 25 Marks]
7CCSMNTH
Continue question 3
See next page
6
4. Question Four
a) Consider the social network in Figure 5, and assume nodes 14 and 10 have decided to follow a different behaviour from the rest of their network. Other nodes in the network will adopt this behaviour if at least 50% of their connections have already adopted that behaviour (that is a threshold of q=1/2).
i. Explain how this behaviour cascades through the social network. [5 marks]
ii. What is the maximum value of q at which this behaviour can become epidemic in the network?
[5 marks]
7CCSMNTH
Figure 5. Social network in question 4.a
See next page
7
b) In the Erdos-Renyi random graph of G(n,p),
i. Explain how the clustering coefficient of C is calculated.
[5 marks]
ii. If degrees of nodes in the graph are d = {d1, … dn}, what is
the probability that a newly added node connects to the
node i with the degree di? [5 marks]
iii. Based on the probability computed in part ii, explain what
does “preferential attachment” mean in the evolution of networks?
[5 marks]
[Total 25 marks]
See next page
8
5. Question five
a) Consider problem (P2)
(P2): Minimise (x1 − 12)2 +(x2 +6)2 Subjectto x12+3×1+x22−4.5×2≤6.5
(x1 −9)2 +x2 ≤64
Determine whether or not the point x = (x1, x2) = (2, 1) is a
candidate to be an optimal solution to this problem.
[5 marks] b) Consider an optimisation problem in the form of (P3),
(P3): Minimise f(x1,x2) Subject to (x1,x2) ∈ R
Where f(x1,x2) = –ln(1 – x1 – x2) – ln x1 – ln x2. Assuming x0 = (x01, x02) = (0.85, 0.05), use Newton’s algorithm to solve this problem. Write only the first two iterations of the algorithm.
[10 marks] Subject to gi(x) ≤ 0 for i = 1, …, m
c) Consider optimisation problem (P4) to be, (P4): Minimise f(x)
hi(x) = 0 for i = 1, …, n
Let x* be a feasible solution that solves P4 locally. Show the Karush–Kuhn–Tucker optimality conditions for (P4).
[5 marks]
d) Consider the following constrained optimisation problem (P5): (P5): Minimise x12 + x22
Subjectto 1–x1 –x2 ≤0
Use the logarithmic barrier method to approximate this problem
with an unconstrained problem.
[5 marks]
[Total 25 marks]
Final Page
7CCSMNTH
9