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: repeat
5:
−→𝑥 𝑖+1 ← −→𝑥 𝑖 · 𝑃
6: 𝑖 ← 𝑖 + 1
7: until 𝑥𝑖 = 𝑥𝑖−1
8: 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 11/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.
By Definition 1, rewrite the graph as a link matrix
⎛
⎝
0 1 1
0 0 1
0 1 0
⎞
⎠ .
1
Trying to apply the step 1 the algorithm, does not contain a row with all 0s, so we
proceed to step 2. First row contains two 1s so we divide both of them by 2. Second and
third lines only contain one 1, so dividing them by 1 makes no change
⎛
⎝
0 1 1
0 0 1
0 1 0
⎞
⎠
: 2
: 1
: 1
=
⎛
⎝
0 1
2
1
2
0 0 1
0 1 0
⎞
⎠ .
Now apply step 3. Since 𝛼 = 0.1, multiply all entries by 0.9
⎛
⎝
0 1
2
1
2
0 0 1
0 1 0
⎞
⎠ · 0.9 =
⎛
⎝
0 9
20
9
20
0 0 9
10
0 9
10 0
⎞
⎠
and by step 4 add 𝛼
𝑁 = 0.1
3 = 1
30
⎛
⎝
0 9
20
9
20
0 0 9
10
0 9
10 0
⎞
⎠ + 1
30 =
⎛
⎝
1
30
29
60
29
60
1
30
1
30
14
15
1
30
14
15
1
30
⎞
⎠ = 𝑃.
Using the Algorithm 1 for PageRank, we select −→𝑥 0 = (1, 0, 0) and the transition
probability matrix 𝑃 from the previous calculation.
−→𝑥 1 = −→𝑥 0 · 𝑃 (1)
−→𝑥 1 = (1, 0, 0) ·
⎛
⎝
1
30
29
60
29
60
1
30
1
30
14
15
1
30
14
15
1
30
⎞
⎠ (2)
−→𝑥 1 =
(︂
1
30
,
29
60
,
29
60
)︂
(3)
−→𝑥 2 = −→𝑥 1 · 𝑃 (4)
−→𝑥 2 =
(︂
1
30
,
29
60
,
29
60
)︂
·
⎛
⎝
1
30
29
60
29
60
1
30
1
30
14
15
1
30
14
15
1
30
⎞
⎠ (5)
−→𝑥 2 =
(︂
1
30
,
29
60
,
29
60
)︂
(6)
Since 𝑥𝑖 = 𝑥𝑖−1, we claim the entries of 𝑥2 as PageRanks of the individual web pages.
By Definition 2, we set the hub score ℎ(𝑣) and the authority score 𝑎(𝑣) to 1s
𝑎(𝑣) =
⎛
⎝
1
1
1
⎞
⎠ , ℎ(𝑣) =
⎛
⎝
1
1
1
⎞
⎠ .
2
Substituting into the second equation in the definition, we get the hub score
ℎ(𝑣) = 𝐴 · 𝐴 𝑇
· ℎ(𝑣)
ℎ(𝑣) =
⎛
⎝
0 1 1
0 0 1
0 1 0
⎞
⎠ ·
⎛
⎝
0 0 0
1 0 1
1 1 0
⎞
⎠ ·
⎛
⎝
1
1
1
⎞
⎠
ℎ(𝑣) =
⎛
⎝
2 1 1
1 1 0
1 0 1
⎞
⎠ ·
⎛
⎝
1
1
1
⎞
⎠
ℎ(𝑣) =
⎛
⎝
4
2
2
⎞
⎠
and the authority score
𝑎(𝑣) = 𝐴 𝑇
· 𝐴 · 𝑎(𝑣)
𝑎(𝑣) =
⎛
⎝
0 0 0
1 0 1
1 1 0
⎞
⎠ ·
⎛
⎝
0 1 1
0 0 1
0 1 0
⎞
⎠ ·
⎛
⎝
1
1
1
⎞
⎠
𝑎(𝑣) =
⎛
⎝
0 0 0
0 2 1
0 1 2
⎞
⎠ ·
⎛
⎝
1
1
1
⎞
⎠
𝑎(𝑣) =
⎛
⎝
0
3
3
⎞
⎠ .
Finally, we normalize them to obtain
ℎ(𝑣) =
⎛
⎝
4
2
2
⎞
⎠
⎛
⎝
1
0.5
0.5
⎞
⎠ and 𝑎(𝑣) =
⎛
⎝
0
3
3
⎞
⎠
⎛
⎝
0
1
1
⎞
⎠ .
3