WEEK - 4
Note: If a != b and either a or b have no in-neighbors, then SimRank(a, b) = 0.
1) In a network where each edge represents a potential collaboration between two nodes,
and the goal is to maximize the number of such collaborations, which type of network is
most suitable?
a) Tree
b) Cycle
c) Bipartite graph
d) Random network
Answer: Option C, as Bipartite Network is most suitable to capture the collaboration between
pair of nodes.
2) In the PageRank algorithm, the node with the highest in-degree is always the most
prestigious node. True or False?
Answer: False, as a node X can have high in-degree, but if the incoming nodes have low
pagerank, then the pagerank of X will still be low.
For Questions 3 to 5:
3) If pe(x, y) represents the probability of formation of an edge between nodes x and y, then
employing the property of Triadic closure, what can be hypothesised about the relation
pe(A, C) vs pe(C, B) from the network in Fig 1?
a) pe(A, C) < pe(C, B)
b) pe(A, C) = pe(C, B)
c) pe(A, C) = 2 * pe(C, B)
d) pe(A, C) > pe(C, B)
Answer: pe(C, B) = 0, as vertices C and B do not have any common neighbour and hence,
cannot form a triadic closure.
Since E is a common neighbour b/w A and C, this can facilitate formation of a triadic
closure. Hence, pe(A, C) > 0 (Note that probabilities of formation of triadic closure can be
measured in different ways, by clustering coefficient, transitivity etc., so we cant find the exact
probability unless explicitly stated in the question the probability we need to use, but we can still
say that if there is a common neighbour, then there is some probability for edge formation).
Hence, Option D is correct.
4) What is the SimRank value between C and B in the network in Fig 1?
𝑐 𝑐 𝑐
Answer: s(C, B) = 1*1
* 𝑠(𝐸, 𝐴) = 1*1
* 𝑠(𝐸, 𝐴) = 1
* 0 (As A has no in-neighbours) = 0
5) What is the SimRank value between C and F in the network in Fig 1? (Assume the
constant c = 1)
Answer: c2 = 1 (Try it yourself!)
6)
Consider the network in Fig 2 of N = 5 nodes and the iterative pagerank formula.
Determine the first iteration of ranks, assuming α = 0.7, R0 = [1/5, 1/5, 1/5, 1/5, 1/5] and
E = [1/5, 1/5, 1/5, 1/5, 1/5]
Answer:
1/5 1
R1 (a) = (1 − 0. 7) ( 2
) + 0. 7 * 5
= 0. 17
1/5 1/5 1
R1 (b) = (1 − 0. 7) ( 3
+ 2
) + 0. 7 * 5
(Try it yourself): Find the first iteration pageranks for C, D, E.
7) If in the above example, we modify the E vector from a uniform distribution to focus on
one or more relevant pages, the resultant pageranks can be termed as
a) Time-homogenous pagerank
b) Time-heterogenous pagerank
c) Personalised pagerank
d) Generic pagerank
Answer: Option C, as discussed in the Lectures.
8) Which of the following are properties of PathSim?
a) Symmetric: s(x,y) = s(y,x)
b) Normalised: s(x,y) ∈ [0,1]
c) Self-maximised: s(x,x) = 1
Answer: Options A, B, C are correct, as discussed in the Lectures.
9) What are time-heterogenous random walks?
a) Random walks where the transition probabilities remain constant over time
b) Random walks where the transition probabilities can change over time.
c) Random walks where the transition probabilities decrease consistently over time
d) Random walks where the transition probabilities increase consistently over time
Answer: Option B, as discussed in the Lectures.
For Questions 10 and 11:
Consider a restaurant review network containing objects of two types – restaurant (R)
and user (U). There exists a review (V) relationship between U and R. Consider the adjacency
matrix as shown in Table 1, where each cell shows the number of reviews given by a user to a
restaurant.
10)What is the value of PathSim between Mint and Symposium?
2 × (2*2 + 4*4 + 0*0 + 0*0)
Answer: PathSim (Mint, Symposium) = (2*2 + 4*4 + 0*0 + 0*0) + (2*2 + 4*4 + 0*0 + 0*0)
=1
11)What is the peer restaurant for Sky Route?
Answer: Peer restaurant is the restaurant which has highest PathSim with Sky Route (apart
from Sky Route itself)
Try it Yourself!!