CITY UNIVERSITY OF HONG KONG
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
Answering this exam paper implies your acknowledgment of the Pledge for following the Rules on Academic Honesty:
“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,
• I will not plagiarize (copy without citation) from any source;
• 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
• I will use only approved devices (e.g., calculators) and/or approved device models.
• I understand that any act of academic dishonesty can lead to disciplinary action.”
Answering this exam paper implies your acknowledgment of the Pledge for following the Rules on Academic Honesty:
“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,
• I will not plagiarize (copy without citation) from any source;
• 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
• I will use only approved devices (e.g., calculators) and/or approved device models.
• I understand that any act of academic dishonesty can lead to disciplinary action.”
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) = ________________
(a2) [3 marks] Edge-betweenness of Edge B-C (no need to normalize)
Answer: B(B-C) = ________________
A B C D E F G
Figure Q1.1
(1.1b) [5 Marks]
(b1) [2 marks] Average distance of Node A to all other nodes
Answer: L = _______________
(b2) [3 marks] Degree correlation of P(1,1), and of P(1,2).
Answer: P(1,1) = _______________ P(1,2) = _________________
Q-1.2 [10 Marks]
(1.2a) [5 Marks] Consider the following network model:
• Step 1 (Initialization) Start with an undirected large-sized fully-connected network.
• 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.
• 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?
Answer:
(a2) [3 marks] If the initial large-sized fully-connected network is directed, what is your conclusion?
Answer:
(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
Answer: = ______________
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 = _________________
(1.3b) [2 marks] the clustering coefficient of any inner node
Answer: C(in) = ______________
(1.3c) [2 marks] the clustering coefficient of any outer node
Answer: C(out) = ______________
(1.3d) [2 marks] the length of girth of any inner node
Answer: g(in) = ________________
(1.3e) [2 marks] the length of girth of any outer node
Answer: g(out) = _________________
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 – v?, u3 – v?, u4 – v?, u5 – v?, u6 – v?, u7 – v?, u8 -v?
Or: No: Because _______________________
Q-1.5 [10 Marks]
Given a network with nodes.
(1.5a) [5 marks] If the network is undirected, with average degree . How many edges does this network have?
Answer: ____________________
(1.5b) [5 marks] If the network is directed, with average out-degree . How many directed edges does this network have?
Answer: ____________________
Q-1.6 [10 Marks] Consider the 6 graphs shown in Figure Q1.6.
Answer each question (type your answers like: A), C), F), …, etc.)
(1.6a) [2 marks] Eulerian graph(s): Answer: ______________
(1.6b) [2 marks] Semi-Eulerian graph(s): Answer: ______________
(1.6c) [2 marks] Hamiltonian graph(s): Answer: ______________
(1.6d) [2 marks] Semi-Hamiltonian graph(s): Answer: _____________
(1.6e) [2 marks] Neither Eulerian nor Hamiltonian graph(s): Answer: ______
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 ______________ and the total path length L = ___
(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: The path is 1–>3–>6–> … –>8)
Answer: The path is _____________ and the total path length L = ___
Figure Q2.1
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 numerical comparison of all possible choices. (For this question, no need to compute the total basic time T, which is not useful.)
Figure Q2.2
Answer:
—– End —–