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

PAPER CODE NO. EXAMINER : Michele Zito
COMP324 DEPARTMENT : Computer Science Tel. No. 0151 7954263
SECOND SEMESTER EXAMINATIONS 2018/19
Complex Information and Social Networks
TIME ALLOWED : Two and a Half Hours
INSTRUCTIONS TO CANDIDATES
Answer FOUR questions.
If you attempt to answer more questions than the required number of questions, the marks
awarded for the excess questions answered will be discarded (starting with your lowest mark).
PAPER CODE COMP324 page 1 of 7 Continued
1. Random Walks.
Table 1: Random numbers relevant to Question 1. If you need more numbers use the
ones in Table 2 in Question 4.
0.569 0.383 0.494 0.752 0.607 0.502
0.116 0.954 0.091 0.071 0.439 0.546
(a) Provide a pseudo-code description of the simple random walk process. [9 marks]
(b) If we run the walk process described in part (a) on the graph in Figure 1 for a long
time, approximately how often would node 1 be visited How often would node 6 be
visited [2 marks]
(c) Run twelve steps of the simple random walk process on the graph in Figure 1, starting
from node 1. Use the random numbers in Table 1 to guide your vertex choices.
[10 marks]
(d) Plot the vertex occurrence frequencies for the walk performed in part (c). [4 marks]
1
7 2 5
4
3
6
8
Figure 1: The small network relevant to Question 1.
PAPER CODE COMP324 page 2 of 7 Continued
Figure 2: The women event co-attendance network from Davies, Gardner and Gardner
(1941), restricted to links between women attending at least three common
events.
2. Dense structures in social networks.
(a) Define the notion of k-core of a network. [5 marks]
(b) Provide a pseudo-code description of an algorithm that can be used to find the k-core
of a given network. [9 marks]
(c) Which vertices are in the 5-core of the network in Figure 2 [8 marks]
(d) Which vertices are removed by a core finding algorithm, if we want to find the 6-core
of the network in Figure 2 [4 marks]
PAPER CODE COMP324 page 3 of 7 Continued
3. Numerosity.
Figure 3: Two configurations of points.
(a) Describe the notion of convex hull of a set of points. [8 marks]
(b) Provide a lower bound and an upper bound for the area of the convex hull, for each of
the two configurations in Figure 3, in terms of the area of sets of squares, assuming
that the area of each square in Figure 3 is 1 cm2
.
[8 marks]
(c) Define the occupancy of a point in each configuration as 25cm2
, i.e. the area of a 5×5
square having the point at its centre.
Figure 4: Single point “squared” occupancy.
Measure the total occupancy of the two sets of points.
[9 marks]
PAPER CODE COMP324 page 4 of 7 Continued
4. Bi-cores in a Kumar network.
Table 2: Random numbers for Question 4.
0.4379 0.3864 0.6257 0.7805 0.2099 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
(a) Describe Kumar’s copy model. [8 marks]
(b) Use the random numbers in Table 2 to update the network in Figure 5 by adding
three additional nodes connected according to Kumar’s copy model, with c = 2 and
α = 0.4.
2
1
3
4
Figure 5: Initial network
[10 marks]
(c) List all copies of the graph in Figure 6 that are present in the solution to part (b).
Figure 6: A (2, 2)-core.
[7 marks]
NOTE. If you did not answer to part (b) you can get up to 6 marks for this part by
finding all copies of the network in Figure 6 in the network in Figure 5.
PAPER CODE COMP324 page 5 of 7 Continued
5. The Configuration Model.
2
1
3
4
5
6
7 8
9
10
11
12
Figure 7: A small network
(a) Describe a process that can be used to generate a network on n nodes in which all
nodes have the same degree d. [9 marks]
(b) Consider the network in Figure 7. Apply the process described in (a) to pair up the two
free balls in node 5. Use the random numbers in Table 1 to guide your choices.
[13 marks]
(c) Explain how to modify the process described in (a) to generate a bipartite network.
[3 marks]
PAPER CODE COMP324 page 6 of 7 Continued
6. Pagerank. Initial formulation and two possible variations.
3
1 2
Figure 8: A small network, relevant to the Pagerank question.
(a) Describe initial formulation of the Pagerank equation, explaining the resulting rela_xfffe_tionship between the ranks of the nodes of the given network.
[3 marks]
(b) Apply the initial formulation Pagerank equation to the graph in Figure 8. Simulate
two steps of the rank updating process, assuming that the initial ranks are all equal to
1
3
. [4 marks]
(c) Describe the way in which the initial formulation of the Pagerank equation can be
modified to fix the problem of rank sinks. [4 marks]
(d) Apply the approach described in part (c) to the graph in Figure 8. Compute two steps
of the rank updating process modified to fix the problem of rank sinks, assuming that
the initial ranks are all equal to 1
3
. [5 marks]
(e) Describe how the initial formulation of the Pagerank process can be modified to in corporate the so called “random surfer” transitions.
[5 marks]
(f) Apply the approach described in part (e) to the graph in Figure 8. Compute two steps
of the rank updating process modified to include random surfing transitions, assuming
that the initial ranks are all equal to 1
3
. [4 marks]
PAPER CODE COMP324 page 7 of 7 End