关键词 > MTH750U/MTH750P
MTH750U / MTH750P: Graphs and Networks – Mock-half-exam 2018-19
发布时间：2022-03-06
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Main Examination period 2018-19
MTH750U / MTH750P: Graphs and Networks – Mock-half-exam
Question 1. [35 marks] Consider the graph G with N = 6 nodes described by the adjacency matrix:
|
╱． 1(0) 0(1)
． 0 0 |
0 0 0 1 0 0 |
1 0 1 0 0 0 |
0 0 0 0 0 1 |
0(0) 、． 0 ．(．) 0 ．(．)
|
|
(a) Compute the in-degree and the out-degree of all the nodes of the graph, and show them in a table. (b) Compute the number of strongly-connected components of the graph. |
(c) What is the minimal set of out-going edges you need to add to node 1 in G so that the resulting graph is strongly connected? Call the resulting graph H.
(d) Compute the distance between all pairs of nodes in the graph H, and write the corresponding distance matrix D = (dij} where dij is the distance from node i to node j.
(e) Compute the closeness centrality of all the nodes of H.
(f) Compute the normalised closeness centrality of all the nodes in H.
Question 2. [25 marks] The US air transportation network is a classical network data set recording the existence of air routes among the N = 500 largest airports in the USA. That graph contains K = 2980 edges.
(a) Let us consider now the Erd
s-Renyi random graph ensemble GN(E)’K(R), where
N = 500 and K = 2980. What is the probability of obtaining a graph
identical to the US air transportation network when sampling from G
? [10]
(b) Consider now the random graph ensemble G
p . How shall we set the value of p in order to maximise the probability of sampling a graph with K = 2980
edges?
(c) What is the probability of finding a node with degree k = 10 in a graph sampled from the random graph ensemble GN(E)’p(R) where N = 500 and p = 0 ●020?
