联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

PAPER CODE NO. EXAMINER: Michele Zito Tel. No. 0151 7954263
COMP324 DEPARTMENT: Computer Science
SECOND SEMESTER EXAMINATIONS 2021/22
Complex Information and Social Networks
TIME ALLOWED : Two and a Half Hours
INSTRUCTIONS TO CANDIDATES
Credit will be given to the best FOUR answers.
Calculators are permitted.
PAPER CODE COMP324 page 1 of 18 Continued
1. Local Clustering v Modularity.
Both the local clustering coefficient and the maximum assortativity measure the clustering
properties of the given networks. This exercise compares the two measures in a 3-regular
network as well as a different network with more arbitrary link placements.
1
6
7
9
8
4
10
3
12
11
2
5
8
5
1
4
10
6
11
2
9
12
3
7
Figure 1: A 3-regular network (left): each vertex has exactly 3 neighbours and (right) a
more general network on 12 nodes, with the same number of edges.
(a) Recall the definition of local clustering coefficient of a node in a network. [2 marks]
(b) Compute the average local clustering for each of the networks in Figure 1. [7 marks]
(c) Recall and explain the concept of network assortativity. [3 marks]
(d) In each of the networks in Figure 1 find a vertex partition that makes the assortativity
as large as possible and compute the relevant assortativity (providing details of your
calculations). [13 marks]
PAPER CODE COMP324 page 2 of 18 Continued
2. Random Walks With a Funny Die.
This question asks you to compare different ways to simulate the rolling of a die. For your
random choices use the following table of randomly generated numbers.
0.24219 0.45802 0.73264 0.29325 0.83386 0.5529
0.00376 0.76403 0.09296 0.70993 0.55958 0.38162
0.31736 0.79533 0.69113 0.08921 0.36986 0.74429
0.30248 0.92208 0.0813 0.76728 0.49213 0.04481
0.77407 0.9877 0.51689 0.54158 0.99821 0.95037
0.11923 0.98462 0.38168 0.56519 0.04203 0.07908
(a) Use the random numbers above to simulate 20 rollings of a fair die. Explain your experi_xfffe_ment and list the sequence of outcomes.
[4 marks]
(b) Now use the network in Figure 2. Simulate 19 steps of a simple random walk on it starting
at vertex 1. Explain your set up and assumptions. List the 20 nodes visited by the walk.
[6 marks]
(c) Simulate 19 steps of a Metropolis random walk on the network in Figure 2, starting at
vertex 1. Explain your set up and assumptions. List the 20 nodes visited by the walk.
[10 marks]
(d) Compare the sequences of numbers generated by answering part 2a and 2c. If you were
given the two sequences without knowledge of the process that generated them would
you say they would both look like sequences of random numbers Explain your answer.
[5 marks]
5
2 4
3
6 1
Figure 2: Random number generator network.
PAPER CODE COMP324 page 3 of 18 Continued
3. Snobbish Networks.
In this question we work with a network of N red and N blue nodes. The probability that there
is a link between two nodes of the same colour is p and the probability that there is a link
between nodes of different colour is q, with p ≥ q. We call G(N, N, p, q) this model.
(a) Particular case. Assume that p = q. Provide an upper bound on the probability that the
diameter of a random G(N, N, p, q) network is larger than 2. [4 marks]
(b) General case. Provide an upper bound on the probability that the diameter of a random
G(N, N, p, q) network is larger than 2.
[3 marks]
(c) Generate an instance of G(6, 6, 1/2, 1/3), using the “random” numbers below.
0.16411 0.40803 0.90279 0.95723 0.60273 0.38576 0.05150 0.34184 0.67644 0.83378
0.22717 0.75799 0.02112 0.10850 0.03525 0.50786 0.54947 0.21834 0.33191 0.07944
0.57379 0.87033 0.87162 0.27401 0.65661 0.35844 0.76784 0.64413 0.24911 0.81222
0.23645 0.67226 0.24308 0.95758 0.22692 0.45162 0.72480 0.80967 0.74363 0.59042
0.649393 0.1480696 0.1416663 0.32943 0.03151 0.060903 0.3476 0.03525 0.520786 0.23466
0.66141 0.49323 0.59766 0.20032 0.82083 0.20621 0.06345 0.91625 0.76151 0.69155
0.02529 0.92519 0.97841 0.60041 0.01251 0.20666 0.42880 0.10303 0.73937 0.36189
[11 marks]
(d) Compute the assortativity coefficient of the network computed in part 3c (with respect to
the red-blue partition).
[7 marks]
PAPER CODE COMP324 page 4 of 18 Continued
4. On Eiron and McCurley’s Model.
(a) Provide a concise, but precise description of Eiron and McCurley’s model (use 200 words
max). [9 marks]
(b) Now consider the following simplified version of that model:
There are just two hosts: one is called “LOCAL” and the other one “REMOTE”. The first
host initially contains just one page, Page “0”, the REMOTE host initially contains the
web-graph in Figure 3.
2
1
3
4
Figure 3: Initial network
HOST SELECTION. New web-pages are added to LOCAL or REMOTE, one at a time,
in discrete time steps. At time t, the new page Pt
is added to LOCAL (REMOTE) with
probability proportional to the number of pages currently in that host. Neither hosts
contain any directory structure, so each will hold just a flat collection of pages.
LINKS. Every time a new page Pt
is added to the structure, c = 3 links are added from
it to three existing pages. Each link is chosen to point to a page P selected using the
standard preferential attachment rule (use a = 1).
Furthermore, if the page Pt
is added to LOCAL, one further link is added from a ran domly selected page in LOCAL to Pt (except in the case when LOCAL is empty).
Table 1: Random numbers.
0.9379 0.3864 0.6257 0.7805 0.099 0.6273 0.1283 0.4745
0.8889 0.6445 0.8922 0.0890 0.7164 0.8109 0.7934 0.8622 0.6064
0.5405 0.1227 0.3606 0.1941 0.4705 0.9315 0.9341 0.0185 0.0528
0.9153 0.7037 0.7514 0.8897 0.6112 0.7264 0.3586 0.0615 0.5056
Please extend the initial five page structure according to the following instructions:
i. Add three more pages to the initial network, using the random numbers in Table 1.
[8 marks]
ii. Add one more page to the network resulting from solving part i. above, but this time
over-ride the host selection rule, and force the page to be added to LOCAL (follow
the general model definition to add the links from/to it). [8 marks]
PAPER CODE COMP324 page 5 of 18 Continued
5. The Structure of the Web.
Every directed network looks like a candy! This question invites you to reflect on the methods
used by Broder et al. to uncover the macroscopic structure of the web.
Figure 4: A small directed network.
(a) Identify the giant strongly directed component in the network in Figure 4. [10 marks]
(b) Identify the sets of nodes in the IN and OUT parts of the network in Figure 4.
[8 marks]
(c) Find the two tendrils and the two tubes in the network in Figure 4. [7 marks]
PAPER CODE COMP324 page 6 of 18 Continued
6. Web Information Retrieval.
(a) Describe five different ways in which people have stored information over the centuries.
Three of these could be taken from the lecture material, two must not have been men tioned in there.
In each case explain the media used to store information, describe the storing process,
and explain pros and cons within the context of searching for information compared to
other options. [6 marks]
(b) Describe the concepts of forward and inverse index. [4 marks]
(c) Describe the forward and inverse index of the network below. Each rectangle in the figure
is a web-page. The numbers are page IDs. The words within each page are the terms
that need to be indexed. [7 marks]
dog, cat
dog
1
cat
2
apple
3
apple
4
dog, cat, apple
6
5
(d) Run three rounds of the HITS ranking process on the network above, providing informa tive details of your simulation at each step, including the values of the hub and authority
scores. [8 marks]
PAPER CODE COMP324 page 7 of 18 Continued