Last name: First name:

Check the boxes for the exercises you want to submit (at most two):
Exercise 1 □ Exercise 2 □ Exercise 3 □

Social Network Analysis – Midterm 2

submission within 60 minutes

Guidelines
• The test must be finished within 60 minutes and has a maximum grade of 7.5.

• The first part of the test is made of 10 T/F questions (below on this page). Please put a
cross on the box you think is correct. Each correct answer gives 0.25 points.

• The second part is made of 3 exercises. You have to choose 2 of them, and you have to com-
municate your decision with the boxes on top of this page (exercises with unchecked boxes
will not be considered). Answers should be fully motivated, and only those contained in
these sheets will be corrected. Each exercise gives a maximum of 2.5 points.

• You can only use: these sheets, a separate sheet for your draft (not to be handed in), a pen,
and your own calculator. No book, no notes, no laptops or other electronic devices.

T/F statements
(1) A strong community is always also a weak community. T F

(2) The resource allocation index gives less weight to less-connected neighbors. T F

(3) A dendrogram is used to visualize hierarchical clustering methods. T F

(4) Attribute-based similarity indices can be always computed. T F

(5) Topical locality is the tendency of pages with different contents to have many T F
hyperlinks between them.

(6) The PageRank cannot be used as a centrality measure for nodes in directed T F
networks.

(7) The network bisection problem is a specific case of network partitioning where T F
the goal is obtaining two clusters of equal size.

(8) A meme is a transmissible unit of information. T F

(9) A high modularity implies that the network is likely to be randomly generated. T F

(10) Similarity-based approaches to link prediction are based on the calculation of one T F
or more similarity indices for each unconnected node pair.
Cosine similarity between two documents Common neighbors
P
→
− → − wd ,t · wd ,t CN(x, y) = |Γ(x) ∩ Γ(y)|
cos( d1 , d2 ) = qP t 1 qP2
2 2
t wd1 ,t · t wd2 ,t
Jaccard index
PageRank |Γ(x) ∩ Γ(y)|
JI(x, y) =
α X Rt−1 (j) |Γ(x) ∪ Γ(y)|
Rt (i) = + (1 − α)
N kout (j)
j∈pred(i) Preferential attachment
Modularity PA(x, y) = |Γ(x)| × |Γ(y)|
kC2
 
1X Adamic-Adar index
Q= LC −
L C 4L X 1
AA(x, y) =
log |Γ(z)|
Shannon entropy z∈Γ(x)∩Γ(y)
X
H(X) = − P (x) log P (x) Resource allocation index
x X 1
RA(x, y) =
Conditional entropy |Γ(z)|
z∈Γ(x)∩Γ(y)
X P (y)
H(X|Y ) = P (x, y) log Shortest-path length index
x,y
P (x, y)
SL(x, y) = −ℓ(x, y)
Normalized Mutual Information
Katz index
2H(X) − 2H(X|Y )
NMI(X, Y ) = ∞
H(X) + H(Y )
X
KI(x, y) = β l · |paths⟨l⟩
x,y |
l=1

Hitting time index

HT(x, y) = −Hx,y

Commute time index

CT(x, y) = −(Hx,y + Hy,x )

Number of common values

σjNC (x, y) = axj ∩ ayj

Jaccard (attribute-based) index

axj ∩ ayj
σjJI (x, y) =
axj ∪ ayj

Overlap coefficient
axj ∩ ayj
σjOC (x, y) =
min axj , ayj

Cosine similarity
axj ∩ ayj
σjCS (x, y) = q q
aj x
ayj
Exercise 1. We want to compute the PageRank for the following graph.

1. Compute the in- and out- degree for each node.

2. Suppose that α = 0 and that
1 1
R0 (1) = = R0 (2), R0 (3) = , R0 (4) = 0.
4 2
Compute the first three iterations of PageRank for every node in the graph. Has the algorithm converged?
What is the node with the highest PageRank?
3. Let kin (i) denote the in-degree of node i. For each node, compute the following alternative centrality measure:

kin (i)
C(i) = P4 , i = 1, 2, 3, 4.
j=1 kin (j)

4. Can we use C to approximate Rt for a large t?

fully motivate your answers

SOLUTION
1. We have
Node 1 2 3 4
kin 1 3 0 1
kout 1 1 2 1

2. The first step of the algorithm yields:

1
R1 (1) = R0 (2) =
4
1 1 1 1
R1 (2) = R0 (1) + R0 (3) + R0 (4) = + + 0 =
2 4 4 2
R1 (3) = 0
1 1
R1 (4) = R0 (3) = .
2 4
We iterate for the second step and we see that:
1
R2 (1) = R1 (2) =
2
1
R2 (2) = R1 (1) + 0 + R0 (4) =
2
R2 (3) = 0
R3 (4) = 0.

It is now clear that R∞ (3) = R∞ (4) = 0, while R∞ (1) = R∞ (2) = 12 .

The algorithm has thus converged with nodes 1 and 2 having the highest PageRank.
3. The measure C gives:

Node 1 2 3 4
C(i) 1/5 3/5 0 1/5

4. No, the measure C only accounts for the in-degree of each node. From the theory we know that this is not
enough to approximate the PageRank. In particular, we see that the values of C are quite different from R∞ .
Exercise 2. Consider the following graph, where observed links are colored in black. We are interested in computing
topological similarity indices between nodes and in quantifying link likelihood scores to identify missing links.

1. Compute the JI and the RA similarity indices between the following unconnected node pairs (colored in grey
in the graph):
(a) D and G;
(b) G and F ;
(c) F and H.
2. Consider each index as a separate link likelihood score. Additionally, compute two other scores based on the
following aggregation functions:
(a) Sum of the topological similarity indices;
(b) Maximum of the topological similarity indices.
3. For each of the four scores, identify as missing link the top 1.

fully motivate your answers

SOLUTION
1. Recall that
|Γ(x) ∩ Γ(y)| X 1
JI(x, y) = , RA(x, y) = .
|Γ(x) ∪ Γ(y)| |Γ(z)|
z∈Γ(x)∩Γ(y)

Hence, we start by computing the neighbours of F , M , N and E:

Γ(D) = {A, C},
Γ(G) = {A, E, H, I},
Γ(F ) = {E},
Γ(H) = {G, I}.
Applying the previous definitions, we obtain:
1
JI(D, G) =
5
1 (1)
JI(G, F ) =
4
JI(F, H) = 0.
Similarly, we obtain that
1 1
RA(D, G) = =
|Γ(A)| 4
1 1 (2)
RA(G, F ) = =
|Γ(E)| 2
RA(F, H) = 0.
2. Denote by s the scores:
sJI sRA ssum smax
(D, G) 1/5 1/4 9/20 1/4
(G, F ) 1/4 1/2 3/4 1/2
(F, H) 0 0 0 0
3. We observe that (G, F ) is the top missing link for every score.
Exercise 3. Suppose that the following division of a network into communities is the result of a certain step of the
Newman’s greedy algorithm. Decide which two communities should be merged in the next step of the algorithm,
having the following information at your disposal:
• the degree distribution (see table below);
• the number of links (L = 23);
• the modularity for the partition obtained merging the green and the orange community (0.1437).

i 1 2 3 4 5 6 7 8 9 10 11 12 13
ki 3 2 5 4 4 2 3 3 3 5 6 3 3

1
5

4
3

9 11

10

12 13

fully motivate your answers

P with C. For S = {A, B, C}, we

Let’s denote the green community with A, the orange with B, and the purple one
have to compute the number LS of internal links and the community degree kS = i∈S ki .
We obtain the numbers of internal links counting the number of green, orange, and purple links, respectively; then,
we get the community degrees summing up the degrees of the nodes in each community. We have:
• LA = 4 and kA = 14.
• LB = 4 and kB = 12.
• LC = 6 and kC = 20.
Now we have to compute the modularity of the partitions that we can get by merging either A and B (QAB ), B and
C (QBC ), or A and C (QAC ). To do so, we need some new quantities:
• LAB = 9 and kAB = 26.
• LBC = 13 and kBC = 32.
• LAC = 15 and kAC = 34.
As an example, we get LAB summing up LA , LB , and the number of links between nodes of A and B, while
kAB = kA + kB .
We use the new quantities to compute the three modularities we need:

k2 k2
 
1
QAB = LAB − AB + LC − C
L 4L 4L
 
1 676 400
= 9− +6− = 0.1437.
23 92 92

2 2
 
1 kBC kA
QBC = LBC − + LA −
L 4L 4L
 
1 1024 196
= 13 − +4− = 0.1626.
23 92 92
 2 2
 
1 kAC kB
QAC = LAC − + LB −
L 4L 4L
 
1 1156 144
= 15 − +4− = 0.2117.
23 92 92

Since QAC > QBC > QAB , we can conclude that the two communities to be merged are A and C. We could expect
this conclusion given the relatively large number of links between communities A and C.
NB: QAB = 0.1437 was included in the text of the exercise, so its computation was not actually required.