King’s College 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.
Degree Programmes
Module Code Module Title
Examination Period
MSci, MSc, MEng 7CCSMNTH
Summer 2018 (Period 2)
Time Allowed 3 hours
Rubric ANSWER FOUR OF FIVE QUESTIONS.
IF MORE QUESTIONS ARE ANSWERED, THE FIRST FOUR (IN ORDER OF APPEARANCE) WILL BE MARKED.
ANSWER EACH QUESTION ON A NEW PAGE OF YOU ANSWER BOOK AND WRITE ITS NUMBER IN THE SPACE PROVIDED
Calculators Calculators may be used. The following models are permitted: Casio fx83 / Casio fx85
PLEASE DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
King’s College London ©2016
Question One
(a) In the network of Figure 1:
i. Find a minimal spanning tree, using Kruskal’s algorithm.
[5 marks]
ii. Does this network have a unique minimal spanning tree? If not, how many minimal spanning trees does it have? Justify your
iii. StartingfromnodeA,findtheshortestpathforreachingall nodes, using Dijkstra’s algorithm.
[5 marks]
iv. Assuming the number on each edge of the graph represent data transmission capacity of the corresponding link, find the
maximum flow from node A to node E.
[5 marks]
7CCSMNTH Network Theory
answer.
[5 marks]
Figure 1
2
SEE NEXT PAGE
Question One – Continued
(b) Calculate the clustering coefficient of each node (Ci) in the graph of Figure 2.
7CCSMNTH Network Theory
[5 marks]
a
A
be d
Figure 2
3
SEE NEXT PAGE
f
c
[Total 25 marks]
Question Two
(a) 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 queuing system.
[5 marks]
ii. Draw the Markov chain and show the transition probabilities between different states.
[5 marks]
iii. Determine the probability that there is one job at server three
[5 marks]
(b) In a computer network a link has a transmission rate of C bit/s. Messages arrive at this link in a Poisson fashion with rate λ messages per second. Assume that the messages have exponentially distributed length with a mean of 1/μ bits, and that the messages are queued in a First Come First Served (FCFS) fashion if the link is busy.
Determine the minimum required C for given λ and μ such that the average system time (service time + waiting time) is less than a given time T0.
[10 marks]
[Total 25 Marks]
7CCSMNTH Network Theory
(the server with service rate μ3).
Figure 3. Closed queuing system for question 2(a)
4
SEE NEXT PAGE
Question Three
Consider two cities, A and B, which are joined by two routes, I and II, with one way roads only. There are 100 travellers who must travel from city A to city B.
Route I links city A to city B through city C. This route begins with a road linking city A to city C, which has a cost-of-travel for each traveller equal to 0.5 + x/200, where x is the number of travellers on this road. Route I ends with a highway from city C to city B, which has a cost-of-travel for each traveller equal to 1 regardless of the number of travellers who will use it.
Route II links city A to city B through city D. This route begins with a highway linking city A to city D which has a cost-of-travel for each traveller equal to 1 regardless of the number of travellers who will use it. Route II ends with a road linking city D to city B which has a cost-of- travel for each traveller equal to 0.5 + y/200, where y is the number of travellers on this road.
i. Draw the network described above and label the edges with the cost-of-travel needed to move along the edge. [5 marks]
ii. Travellers simultaneously choose which route to use. Find Nash equilibrium values of x and y. [5 marks]
iii. A change has been introduced to the road infrastructure by the government, who built a new (one-way) road from city C to city D. The cost-of-travel on this new road is 0. Find the Nash equilibrium for the game played on this new road network.
[5 marks]
iv. How does the total cost-of-travel change, as a result of the new road from C to D? Justify your answer. [5 marks]
v. After a while, the government decides to introduce an additional charge of 0.125 per user, to the users of road from city A to C, and reduce the charge for users of road from A to D by 0.125 per user. Find the new Nash equilibrium. [5 marks]
[Total 25 marks]
7CCSMNTH Network Theory
5
SEE NEXT PAGE
Question Four
(a) Consider problem (P1) below,
(P1): 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. Show all the steps with
details.
(b) Consider the general form optimisation problem (P2),
(P2): Minimise f(x)
Subjectto gi(x)≤0 fori=1,…,m
hi(x) = 0 for i = 1, …, n
i. Write the Lagrangian dual problem of (P2).
[10 marks]
[5 marks]
ii. Let x* be a feasible solution that solves P2 locally. Show the Karush– Kuhn–Tucker optimality conditions for (P2).
[5 marks]
iii. Use the logarithmic barrier method to approximate (P2) with an unconstrained problem.
[5 marks]
6
SEE NEXT PAGE
7CCSMNTH Network Theory
[Total 25 marks]
Question Five
(a) Consider the decision-based model of diffusion in the network of Figure 4. Suppose that initially everyone is following behaviour B and then a new behaviour A is introduces. The decision threshold for nodes is q=1/2, i.e. any node will switch to A if at least half of its neighbours are following A.
i. Find a set of three nodes in the network with the property that if they act as the three initial adaptors of A, then behaviour A will spread to all nodes. [5 marks]
ii. Is the set of three nodes you found in i. the only three initial nodes that have this property? If the set is not unique, mention one other set of three nodes.
Figure 4
7
SEE NEXT PAGE
7CCSMNTH Network Theory
[5 marks]
(b) The threshold q in the general form of the decision-based model of diffusion, is derived from a coordination game that each node plays with each of its neighbours. If nodes v and w are each trying to decide whether to choose behaviours A and B, then:
– if v and w both adopt behaviour A, they each get a payoff a > 0; – if they both adopt B, they each get a payoff b > 0;
– if they adopt opposite behaviours, they each get a payoff 0.
i. Write the coordination game between v and w, and show how q, the decision threshold, can be formulated.
[5 marks]
ii. Let’s now consider a slightly more general version of the model, in which the payoff for choosing opposite behaviour is not 0, but some small positive number x, which is less than both a and b. In this variant of the model, is it possible to write down a formula for a threshold q, in terms of the three quantities a, b, and x, so that each node v will adopt behaviour A if at least a q fraction of its neighbours are adopting A, and it will adopt B otherwise? Justify your answer.
[10 marks]
8
SEE NEXT PAGE
7CCSMNTH Network Theory
[Total 25 marks]