Link analysis (Chapter 21)
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 21/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