(Sample – Page 1)
CITY UNIVERSITY OF HONG KONG
Copyright By PowCoder代写 加微信 powcoder
Course Code & Title: EE6605
Complex Networks: Modeling, Dynamics and Control
Session: Semester A 2020/21
This is an open-book Test on Wednesday December 16, 2020
Complete the exam individually. No communication with others.
Answer all 7 questions
* Student Name: ______________________
* Student ID: _________________________
You have 2 hours (18:30-20:30), plus 15 minutes to save your answers as pdf file and upload the pdf file to Canvas. Deadline for receiving your answer pdf file is 20:45
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,
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.”
In all questions below, to avoid triviality, let . For “True or False” questions, if your answer is True, give a brief explanation (unless it indicates no need to do so). If your answer is False, show a counterexample (by written description, no need to draw figures).
Question 1 [20 Marks] (Graph Theory)
Q-1.1 [3 Marks] “True or False”? (For this part (a), (b), (c), no need to explain)
(a) [1 mark] Any 1-dimentional lattice of size is isomorphic to a bipartite network.
(b) [1 mark] Any 2-dimentional lattice of size is isomorphic to a bipartite network.
(c) [1 mark] Any 3-dimentional lattice of size is isomorphic to a bipartite network.
Q-1.2 [3 Marks] “True or False”?
Let be a directed graph and be its underlying graph. Moreover, let be a directed spanning tree of and be the underlying graph of . Then, is a spanning tree of .
Q-1.3 [4 Marks] “True or False”?
(a) [2 marks] The underlying graph of a directed Eulerian graph contains a spanning tree.
(b) [2 marks] The underlying graph of a directed Hamiltonian graph contains a spanning tree.
Q-1.4 [5 Marks] “True or False”?
It is not possible for a simple undirected graph of size to have all its nodes with different degrees.
(a) [1 mark] True or False? Answer:
(b) [4 marks] Explain why you think so. Answer:
Q-1.5 [5 Marks]
(a) [3 marks] Let be the adjacency matrix of a given graph , and let be a matrix in which all diagonal elements are 0 but all other elements are 1. Let (i.e., “B subtracts A” component-wise) be the adjacency matrix of a new graph . What type of graph is comparing to ? (No need to explain.)
(b) [2 marks] Find the Node Connectivity and Edge Connectivity of the graph shown in Figure Q1.4 (no need to show calculation steps):
Figure Q1.4
Answer: NC(G) = ____ EC(G) = ____
Question 2 [20 Marks] (Graph Applications)
Q-2.1 [10 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.)
(a) [7 marks] Show a spanning tree with the shortest total path length (type your answer like: Connecting edges (A,E), (E,F), … , etc.)
Answer: [5 marks] Connecting edges: ______________
[2 mark] The total path length of the spanning tree: L = ___
Figure Q2.1
(b) [3 marks] What is the shortest way to go from Node A to Node E?
Answer: A –> ________ –> E
Q-2.2 [10 Marks]
(a) [4 marks] “True or False”?
A connected undirected bipartite graph is called a complete bipartite graph, if every node in one party connects to all nodes in the other party. Now, consider a complete bipartite graph with nodes in one party and nodes in the other party, denoted as , where to avoid triviality. Then, the size (number of edges) of any maximum matching of , denoted as satisfies .
(b) [6 marks] Suppose that in a factory there are workers and jobs. Suppose also that each worker is trained to do several jobs, and each job can be done by several workers. Now, the jobs are to be assigned for the workers to do, such that “every worker will do at most one job” and “every job has at least one worker to do”. This is called the job assignment problem.
(b1) [2 marks] What kind of graph will this problem be formulated to?
(b2) [4 marks] Find 2 conditions under which this job assignment is always possible.
Condition 1 [2 marks]:
Condition 2 [2 marks]:
Question 3 [10 Marks] (Internet Structures and Properties)
Q-3.1 [5 Marks]
In a computer network, nodes are computers and edges are connecting cables (optical fibres). Let be the set of all neighbors of node including itself, and let be the number of nodes in this node set. Denote the edge between Node and Node by . Now, define the Cable Pairing Index by
Figures Q3.1 (a) and (b) are two simple examples to illustrate the definition of the cable pairing index. Calculate in the computer network shown in Figure Q3.1 (c). (No need to show your calculation steps.)
(a) (b) (c) .
Figure Q3.1
= _________
Q-3.2 [5 Marks] Consider the computer network shown in Figure Q3.2, where all nodes are computing centres and all edges are same type of cables (optical fibres). Without computation, compare the node-betweenness of Node 3 and Node 6 to see which is bigger, or equal, or smaller. Explain why you think so.
Figure Q3.2
Question 4 [10 Marks] (Spreading Dynamics and Cascading Effects)
Q-4.1 [4 Marks] Consider a group of 6 people {a, b, c, d, e, f}, with the connection described by Figure Q4.1. Suppose that each person needs to choose either medicine A or medicine B. For each connected pair of adjacent persons (neighbors), if they both choose A then each of them will receive 15 dollars reward from the company, while if they both choose B then each will receive 40 dollars from the other company. If a person has multiple neighbors, he can only receive one (the highest) reward. Assume that initially {a, b, c, d} choose A and {e, f} choose B, so that {a, b, c, d} each receives 15 dollars while {e, f} each receives 40 dollars.
Figure Q4.1
Now, it is very natural for c to change his choice from A to B, because together with e he will receive more, namely, his 15 dollars reward will become 40 dollars. Therefore, changed his choice from A to B.
(a) Then, what will b do (change or remain)? Answer: __
(b) Next, what will a do (change or remain)? Answer: __
(c) Finally, what will d do (change or remain)? Answer: __
(d) What do you conclude from this phenomenon? Answer: __
Q-4.2 [6 Marks] Consider a large population with a homogeneous distribution of friendships, where the average degree of nodes (people) is . Suppose that initially one person was infected with some disease and the infection was spreading over the whole population day by day: on the first day, all neighbours of this infected person were infected; on the second day, all neighbours of each infected person were infected; etc. Assume that there is no recovery, so an infected person will remain to be infected throughout the process.
(a) [3 marks] Roughly, how many people would be infected in days?
Answer: __
(b) [3 marks] What will be the most effective immunization method to resist this spreading?
Answer: __
Question 5 [10 Marks] (Community Structures)
Q-5.1 [5 Marks] For the digraph shown in Figure Q5.1, where the number at each edge indicates the price to pay if you cut that edge (e.g., if you cut edge A-B then you need to pay 6). Let S be the start node to send out data and T be the terminal node to receive data.
Figure Q5.1
(a) [2 marks] Find a minimum-price cut in the sense that you cut the graph into two components while paying a minimum total price (e.g., cut edges (A,B), (F,C), etc.).
Answer: Cut edges ________
Minimum total price = ________
(b) [3 marks] Based on the “equal out-degree” balance criterion, predict as many possible new links as possible. Avoid double connections:
Answer: ______
Q-5.2 [5 Marks]
(a) [2 marks] Consider the network shown in Figure Q5.2. Allow overlapping. Detect a 3-clique community division. What is overlapped?
Figure Q5.2
(b) [3 marks] Consider the same network shown in Figure Q5.2. Divide the network into two communities by a planted 2-partition. Avoid the trivial case with isolated nodes.
Question 6 [15 Marks] (Network Synchronization and Control)
Here and below, all nodes are assumed to be one-dimensional systems and the network is single-input single-output (SISO) connected.
Q-6.1 [5 Marks] For the 2 graphs shown in Figure Q6.1, which one has stronger synchronizability? Show your reasoning.
(a) (b)
Figure Q6.1
Q-6.2 [10 Marks] Consider the two directed networks shown in Figures Q6.2 (a) and (b).
(a) (b)
Figure Q6.2
(a) [4 mark] How many external controllers do they need, respectively, for the networks to be controllable? Why?
(b) [3 marks] After a targeted edge-removal attack, to remove only the inside diagonal edge from each graph, how many external controllers will the two resulting networks need, respectively, to remain to be controllable? Why?
(c) [3 marks] After a random edge-removal attack, to remove only one edge from the outside ring of each graph, how many external controllers will the two resulting networks need, respectively, to remain to be controllable? Why?
Question 7 [15 Marks] (Knowledge Integration)
Consider the directed network shown in Figure Q7, where an edge without arrow means bi-directed: The following 3 questions can be answered independently.
(a) [4 marks] Point out 2 cases to show that this network is not strongly connected.
(1) no path from 14 to 6 ___
(2) no path from 9 to 5_
(b) [5 marks] Suppose that you start from Edge (8,7) to find a maximum matching, and you first pin one external controller at Node 8. Then, you move on to find the whole maximum matching and pin possibly more nodes, so as to make this network to be controllable. How many external controllers do you need? Where to pin them? Briefly explain why.
(c) [6 marks] Now, suppose that the figure represents a computer network. Which edge is the weakest against edge-removal attack, in the sense that the removal of this edge will most seriously affect the overall data traffic on the network?
(1) [3 marks] Give your answer like “Edge (1,4)” (no need to draw any picture).
(2) [3 marks] Explain why you think so.
(1) Edge (6, 14)
(2) Because all nodes on left subgraph can go to node 6, node 14 can go to all other nodes on the right subgraph.
Removing it, serious affect the data traffic from left subgraph to right subgraph.
—– End —–
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com