タイトル : Googleのページランクのこと
更新日 : 2022-08-04
カテゴリ : AI、IA、数理
タグ :

Googleのページランク

2005年ぐらいに一度勉強したけど、ページ更新です。

今回は以下を参考にしました。

なぜ線形代数を学ぶ? Googleのページランクに使われている固有値・固有ベクトルの考え方 補足資料 http://yokoemon.web.fc2.com/TA/2009Sec/20091220.pdf

ページランクを求めてみよう

以下の3つのページのページランクを求めます。 画像1

矢印はリンクを表します。以下はページ1からページ2にリンクしていることを表します。 画像2

次に以下の表を作ります。

ページ1 ページ2 ページ3
ページ1 0 1 1
ページ2 1 0 0
ページ3 1 1★ 0

例えば上記の★は以下の位置のリンクに相当します。

画像3

作成した表から出来る行列の行と列を入れ換えて、列毎に合計したら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 になります。これは以下のような関係を意味します。

画像4

各ページのリンク関係を行列にし、固有値を解いて、ページの価値(=>ページランク)を求めるなんてすごいです。