Webページが下図のような \(n = 6 \) ページからなるリンク構造を持つものとします.例えばページ A からはページ B, D, E へリンクが貼られており,ページ A にはページ B, D, F からリンクが貼られています.
PageRank は \( n \times n\) の行列 \(H\) の固有値を用いて導出できます.ページ \(i\) から出るリンクの個数を \(P_i\) とします.ページ \(i\) からページ \(j\) にリンクがある場合には,行列 \(H\) の \(i\) 行 \(j\) 列を \(1 / P_i\) とし,それ以外を \(0\) とします.行列 \(H\) を転置した行列に対して,絶対値が最大となる固有値に対応する固有ベクトルを選ぶ.選択された固有ベクトルの各要素を要素の和で割ることにより PageRank が導出されます.
実際に Python で PageRank を求めてみよう.まず,リンク構造から行列 \(H\) を作成します.たとえば,ページAからは3つのページ (B, D, E)にリンクが貼られているので,行列の1行目(インデックス0)は2, 4, 5列目(インデックス1,3,4)の要素が1/3となります.
行列の作成
import numpy as np # プログラムの先頭でモジュールを読み込む
H = np.array([
[0, 1/3, 0, 1/3, 1/3, 0],
[1/3, 0, 1/3, 0, 0, 1/3],
[0, 1, 0, 0, 0, 0],
[1/2, 0, 0, 0, 1/2, 0],
[0, 0, 0, 0, 0, 1],
[1/3, 1/3, 0, 0, 1/3, 0]
])
print(H)
[[0. 0.33333333 0. 0.33333333 0.33333333 0. ] [0.33333333 0. 0.33333333 0. 0. 0.33333333] [0. 1. 0. 0. 0. 0. ] [0.5 0. 0. 0. 0.5 0. ] [0. 0. 0. 0. 0. 1. ] [0.33333333 0.33333333 0. 0. 0.33333333 0. ]]
次に行列 \(H\) を転置します.
行列の転置
HT = np.transpose(H)
print(HT)
[[0. 0.33333333 0. 0.5 0. 0.33333333] [0.33333333 0. 1. 0. 0. 0.33333333] [0. 0.33333333 0. 0. 0. 0. ] [0.33333333 0. 0. 0. 0. 0. ] [0.33333333 0. 0. 0.5 0. 0.33333333] [0. 0.33333333 0. 0. 1. 0. ]]
転置した行列の固有値と固有ベクトルを求める.
固有値と固有ベクトルの計算
w, v = np.linalg.eig(HT)
固有値を表示します.固有値の大きい順番で表示されていますが,指数表示ではその確認が難しいかもしれません.
固有値の表示
print(w)
[ 1.00000000e+00 4.34258546e-01 -2.33852425e-16 -9.76310729e-02 -7.67591879e-01 -5.69035594e-01]
Numpy では np.set_printoptions(suppress=True)
という命令を実行することで,上のような指数形式の表示ではなく小数形式で表示する指定も可能です.小数形式で固有値を表示すると,絶対値が最大になる固有値は1番目(インデックス0)の 1.0 であることが容易にわかります.
小数形式で固有値の表示
np.set_printoptions(suppress=True)
print(w)
[ 1. 0.43425855 -0. -0.09763107 -0.76759188 -0.56903559]
全ての固有ベクトルを表示してみます.
固有ベクトルを表示
print(v)
[[ 0.43465076 -0. 0. 0.16889581 -0. -0.61749016] [ 0.50709255 -0.56091376 0. 0.08990133 0.64859068 -0.10087532] [ 0.16903085 -0.43055285 -0.26726124 -0.30694236 -0.28165605 0.0590914 ] [ 0.14488359 0. -0.53452248 -0.57664636 0. 0.36171736] [ 0.4105035 0.43055285 -0. -0.1008082 0.28165605 -0.31486419] [ 0.57953435 0.56091376 0.80178373 0.72559977 -0.64859068 0.61242092]]
このうち,絶対値が最大となる固有値 (1.0) に対応する固有ベクトルだけを表示します.
固有ベクトルを選ぶ
vec = v[:, 0]
print(vec)
[0.43465076 0.50709255 0.16903085 0.14488359 0.4105035 0.57953435]
固有ベクトルの要素の和が 1 になるように,各要素を要素の和で割ることにより,PageRank が計算されました.
PageRankの表示
print(vec / vec.sum())
[0.19354839 0.22580645 0.07526882 0.06451613 0.1827957 0.25806452]