タイトル : Googleのページランクのこと
更新日 : 2022-08-04
カテゴリ : AI、IA、数理
タグ :
Googleのページランク
2005年ぐらいに一度勉強したけど、ページ更新です。
今回は以下を参考にしました。
なぜ線形代数を学ぶ? Googleのページランクに使われている固有値・固有ベクトルの考え方 補足資料 http://yokoemon.web.fc2.com/TA/2009Sec/20091220.pdf
ページランクを求めてみよう
矢印はリンクを表します。以下はページ1からページ2にリンクしていることを表します。
次に以下の表を作ります。
ページ1 | ページ2 | ページ3 | |
---|---|---|---|
ページ1 | 0 | 1 | 1 |
ページ2 | 1 | 0 | 0 |
ページ3 | 1 | 1★ | 0 |
例えば上記の★は以下の位置のリンクに相当します。
作成した表から出来る行列の行と列を入れ換えて、列毎に合計したら1になるような行列を作り、その固有値をべき乗法で求めます。
べき乗法のメソッドは http://penguinitis.g1.xrea.com/computer/programming/Python/eigenvalue.html から持ってきました。
test.py
import numpy as np
# 行列の固有値の計算
# http://penguinitis.g1.xrea.com/computer/programming/Python/eigenvalue.html から
# べき乗法のメソッドを持ってくる
def eig_power(A, eps=1e-5, maxiter=100):
x = np.ones((A.shape[0], 1))
x = x/np.linalg.norm(x)
v0 = np.zeros((A.shape[0], 1))
v = x
i = 0
while np.linalg.norm(v - v0) > eps:
v0 = v
v = A.dot(x)
l1 = v.T.dot(x)[0, 0]
x = v/np.linalg.norm(v)
i += 1
if i == maxiter:
break
x[np.abs(x) < eps] = 0.
return l1, x
# 対象となる行列
a = np.array([[0.0, 1.0, 0.5], [0.5, 0.0, 0.5], [0.5, 0.0, 0.0]])
# べき乗法で固有値計算
(l1, ev) = eig_power(a)
page_rank = ev/ev.sum()
print(f'ページランクは {page_rank.tolist()} です')
$ python test.py
ページランクは [[0.44444529215494794], [0.3333333333333333], [0.22222137451171872]] です
$
計算結果を分数で表すと 4/9、3/9、2/9 になります。これは以下のような関係を意味します。
各ページのリンク関係を行列にし、固有値を解いて、ページの価値(=>ページランク)を求めるなんてすごいです。