Course Code & Title: EE6605
Complex Networks: Modeling, Dynamics and Control
Session: Semester A 2020/21
This is an open-book Test on Thursday October 22
Answer all questions
* Student Name: ______________________ * Student ID: _________________________
You have 60 minutes (8:00-9:00pm), plus 10 minutes to save your answers as pdf file and upload the pdf file to Canvas. Deadline for receiving your answer pdf file is 9:10pm
“I pledge that the answers in this examination are my own and that I will not seek or obtain an unfair advantage in producing these answers. Specifically,
1. I will not plagiarize (copy without citation) from any source;
2. I will not communicate or attempt to communicate with any other person during the examination; neither will I give or attempt to give assistance to another student taking the examination; and
3. I will use only approved devices (e.g., calculators) and/or approved device models.
4. I understand that any act of academic dishonesty can lead to disciplinary action.”
1|6
Question 1 [60 Marks] (Basic Concepts and Network Modelling) Q-1.1 [10 Marks]
For the network shown in Figure Q1.1, compute (1.1a) and (1.1b): (1.1a) [5 Marks]
(a1) [2 marks] Node-betweenness of Node C (no need to normalize) Answer: B(C) = 8
(a2) [3 marks] Edge-betweenness of Edge B-C (no need to normalize)
Answer: B(B-C) = 9
ABCDEFG Figure Q1.1
(1.1b) [5 Marks]
(b1) [2 marks] Average distance of Node A to all other nodes
Answer: L = (1+2+3+4+5+6)/6 = 21/6
(b2) [3 marks] Degree correlation of P(1,1), and of P(1,2).
Answer: P(1,1) = 2×0/2×6 = 0 ___ P(1,2) = 1×2/2×6 = 1/6
Q-1.2 [10 Marks]
(1.2a) [5 Marks] Consider the following network model:
o Step 1 (Initialization) Start with an undirected large-sized fully-connected network.
o Step 2 (Process) Pick up an edge: if removing it does not disconnect the whole network, then remove it; but if removing it will disconnect the network, then do nothing. Continue to pick up another edge from the resultant network and repeat the above
possible edge-removal operation.
o Step 3 (End) After every possible edge has been operated once, and once only, stop.
(a1) [2 marks] What kind of network will you obtain?
2|6
Answer: A tree
(a2) [3 marks] If the initial large-sized fully-connected network is directed, what is your
conclusion?
Answer: A connected directed network (which may not be a directed tree, but its underlying network is a tree).
(1.2b) [5 Marks] Consider Figure Q1.2, where Node 2 sends 2 emails to all its neighbours (i.e., Nodes 1, 3, 4), with the following events:
Node 1 accepts the first email but rejects the second. Node 3 rejects the first email but accepts the second. Node 4 accepts both emails.
Calculate the weight 𝑤24
Answer: 𝑤 =𝛿1𝛿1 +𝛿2𝛿2 =1×1+1×1=2
Figure Q1.2
Q-1.3 [10 Marks]
Consider the graph shown in Figure Q1.3. Find:
Figure Q1.3
(1.3a) [2 marks] the coreness of the network Answer: coreness = 3
(1.3b) [2 marks] the clustering coefficient of any inner node Answer: C(in) = 0
24 24 24
3|6
(1.3c) [2 marks] the clustering coefficient of any outer node Answer: C(out) = 0
(1.3d) [2 marks] the length of girth of any inner node Answer: g(in) = 5
(1.3e) [2 marks] the length of girth of any outer node Answer: g(out) = 5
Q-1.4 [10 Marks]
Are the two graphs in Figure Q1.4 isomorphic? Show your reasoning.
Figure Q1.4
Answer: Yes: u1 – v1, u2 – v2, u3 – v7, u4 – v8, u5 – v5, u6 – v4, u7 – v3, u8 -v6 Or: u1 -v1, u2 –v2, u3 –v3, u4 –v8, u5 –v5, u6 –v6, u7 –v7, u8 -v4
Or: No: Because Q1-5 [10 Marks]
Given a network with 𝑁 = 1,000 nodes.
(1.5a) [5 marks] If the network is undirected, with average degree 〈𝑘〉 = 10. How many edges does this network have?
Answer: 10×1000/2 =5,000
(1.5b) [5 marks] If the network is directed, with average out-degree 〈𝑘〉𝑜𝑢𝑡 = 10. How many directed edges does this network have?
Answer: 10×1000=10,000
4|6
Q-1.6 [10 Marks] Consider the 4 graphs shown in Figure Q1.6.
Answer each question (type your answers like: A), C), …, etc.)
(1.6a) [2 marks] Eulerian graph(s): Answer: A),
(1.6b) [2 marks] Semi-Eulerian graph(s): Answer: A),
(1.6c) [2 marks] Hamiltonian graph(s): Answer: C), D)
(1.6d) [2 marks] Semi-Hamiltonian graph(s): Answer: A), C), D)
(1.6e) [2 marks] Neither Eulerian nor Hamiltonian graph(s): Answer: B)
Figure Q1.6 Question 2 [40 Marks] (Applications)
Q2.1 [20 Marks] Consider the traffic network shown in Figure Q2.1. For this question, no need to draw pictures, and no need to show calculation steps.
(2.1a) [15 marks] Show a spanning tree with the shortest total path length (type your answer like: connecting edges 1–3, 3–6, … )
Answer: Connecting edges 1–4, 1–2, 2–5, 5–6, 6–3, 3–7, 7–8 and the total path length L = 10
5|6
(2.1b) [5 marks] Based on the above answer, find a path from Node 1 to Node 8 with the shortest total path length (type your answer like: connecting edges 1–>3, 3–>6, … )
Answer: The path is 1 –> 2 –> 5 –> 6 –> 3 –> 7 –> 8 and the total path length L = 9
Q2.2 [20 Marks] Solve the Chinese Postman Problem shown in Figure Q2.2 (type your answer like: Add edges 1-4, 4-3, 2-4, … etc.). Show comparisons of all possible choices.
Answer:
Add edges 1-2 and 3-4: extra time 5 + 3 = 8
Add edges 1-3 and 2-4: extra time 2 + 3 = 5
Add edges 1-4 and 2-3: extra time 2 + 4 + 6
—– End —–
Figure Q2.2
6|6