The University of Sydney
School of Computer Science
COMP5313—Large Scale Networks S1 2023
Assignment 1 - Due: Week 6, Friday the 31st of March, 23:59 AEDT
Submit your answer by the deadline as a PDF in Canvas by clearly showing your steps. You
may use computer programs (e.g., Python, NetworkX) for the tasks. If you choose to use
computer programs, please include your code snippets in addition to the answers in the sub-
mitted document. You should follow the concepts and algorithms presented in the lecture
slides, instead of those you found on the Internet.
For all questions, provide an explanation for your answer.
Task 1 - Strong and Weak Ties (1pt)
In the social network depicted in Figure 1 with each edge labeled as either a strong (i.e., s) or
weak (i.e., w) tie, list all the nodes that violate the Strong Triadic Closure Property. Provide
an explanation for your answer.
B C
A D
E
s
w
s w
s
s
w s
Figure 1: A graph with a strong/weak tie labeling
Task 2 - Link Formation (1.5pts)
Consider the social network represented in Figure 2. Suppose that this social network was
obtained by observing a group of people at a particular point in time and recording all their
friendship relations. Now suppose that we come back at some point in the future and observe
it again.
i) According to the theories based on empirical studies of triadic closure in networks, which
new edge is most likely to be present? (i.e., which pair of nodes, who do not currently have
an edge connecting them, are most likely to be linked by an edge when we return to take the
second observation?) Provide an explanation for your answer. (0.5pt)
1
ii) What is the embeddedness of edge (D,E)? Provide an explanation for your answer.
(0.5pt)
iii) What is the neighborhood overlap of edge (A,D)? Provide an explanation for your
answer. (0.5pt)
A
B E D
C
Figure 2: A social network where triadic closure may occur
Task 3 - Relationships (4pts)
i) Determine if the network of Figure 3(a) is balanced or not. Please explain your reasoning.
(2pts)
ii) Determine if the network of Figure 3(b) is balanced or not. Please explain your reasoning.
(2pts)
+
A
B
C
D
E
F
G H
I
+
+
−
−
−
−
−
−
−
−
(a)
−
A
B
C
D
E
F
G H
I
+
+
+
−
−
−
−
−
−
−
(b)
Figure 3: Two social networks
Task 4 - Network Bottlenecks (4.5pts)
The NSW Roads Minister shows you a map of Sydney highways as depicted in Figure 4 with
the following claim: The new WestConnex project will reduce traffic congestion in the Sydney
area.
i) Assume that traffic is uniform between all pairs of nodes. What property seen during the
lectures would you compute to get an idea of the traffic bottleneck in different areas of Sydney?
2
Figure 4: The map representing Sydney highways
Does this property apply to nodes (i.e., vertices) or to links (i.e., edges)? (1pt)
ii) Your task is now to verify whether traffic bottlenecks will be reduced after the edge
⟨Strathfield, Airport⟩, labelled “WestConnex”, is created. How do you proceed? (1pt)
iii) Is the claim true or false? Explain. (1pt)
iv) Consider the graph that results from the introduction of the WestConnex edge as well as
an edge between “Eastern Creek” and “Airport”, give the nested regions (set of regions at
each level) of this graph using the Girvan-Newman partitioning method. Explain. (1.5pts)
Task 5 - Hub and Authority (4pts)
Suppose you wanted to create a new Web page X, and add it to the network in Figure 5, so
that it could achieve a normalised authority score that is as large as possible. One thing you
might try is to create a second page Y as well, so that Y links to X and thus confers authority
on it. In doing this, it is natural to wonder whether it helps or hurts X’s authority to have Y
link to other nodes as well.
Specifically, suppose you add X and Y to the network in Figure 5, and you are only allowed to
add edges from Y to {A, B, C, X}. What is the highest/best rank you can achieve for page X
based on its normalised authority score after two rounds of hub-authority computation, if you
choose as many outgoing edges for Y as NECESSARY? Please explain. (Assume, as usual,
that each page has a hub and an authority score that are both initially 1.)
3
DE
F
A
B
C
Figure 5: A network of Web pages
4