Seminar 11
Definition 1 (Markov Transition Matrix)
Given the graph 𝐺 = (𝑉, 𝐸) and teleport probability 𝛼, let 𝑁 = |𝑉 | and 𝐴 be the 𝑁 × 𝑁 link
matrix with elements
∀𝑢, 𝑣 ∈ 𝑉 : 𝐴 𝑢𝑣 =
{︃
1 (𝑢, 𝑣) ∈ 𝐸
0 otherwise
The transition probability matrix 𝑃 is then calculated in the following way:
1. If a row of 𝐴 has all 0s, then substitute all of them with 1s.
2. Divide each 1 by the number of 1s in that row.
3. Multiply each entry by 1 − 𝛼.
4. Add 𝛼
𝑁 to each entry.
Algorithm 1 (PageRank)
1: function PageRank(𝑃)
2: 𝑖 ← 0
3:
−→𝑥 𝑖 = (1, 0, . . . , 0)
4:
−→𝑥 𝑖+1 = (0, 0, . . . , 0)
5: repeat
6:
−→𝑥 𝑖+1 = −→𝑥 𝑖 · 𝑃
7: 𝑖 = 𝑖 + 1
8: until 𝑥𝑖 = 𝑥𝑖−1
9: end function
Definition 2 (Hubs and authorities)
Given the link matrix 𝐴, let ℎ(𝑣) denote the hub score and 𝑎(𝑣) the authority score. First,
set the ℎ(𝑣) a 𝑎(𝑣) vectors to 1 𝑁
for all vertices 𝑣 ∈ 𝑉 . The scores are calculated as
ℎ(𝑣) = 𝐴 · 𝑎(𝑣)
𝑎(𝑣) = 𝐴 𝑇
· ℎ(𝑣)
which is equivalent to
ℎ(𝑣) = 𝐴 · 𝐴 𝑇
· ℎ(𝑣)
𝑎(𝑣) = 𝐴 𝑇
· 𝐴 · 𝑎(𝑣)
Exercise 1
Assume the web graph 𝐺 = (𝑉 = {𝑎, 𝑏, 𝑐}, 𝐸 = {(𝑎, 𝑏), (𝑎, 𝑐), (𝑏, 𝑐), (𝑐, 𝑏)}). Count PageRank,
hub and authority scores for each of the web pages. Rank the pages by the individual scores
and observe the connections. You can assume that in each step of the random walk we
teleport to a random page with probability 0.1 and uniform distribution. Normalize the hub
and authority scores so that the maximum is 1.
1