お手軽PageRankの求め方

大学3年生のときのレポートで何回かPageRankを求める課題があったので覚書です。

PageRankそのものについての話はしません!さっそく例題のPageRankを求めていきます。

2020/12/16追記

はてなブログで「$$で囲むとLATEXレンダリングされる仕様」がなくなったみたいです>< 例題や解で使用しているLATEXの行列はお手元でレンダリングいただきますよう、お願いいたします。

使うもの

・グーグルスプレッドシート

固有値と固有ベクトル - 高精度計算サイト

例題

ノードが8つである仮想のwebページでPageRankを求めなさい。仮想のリンクは以下の行列で表されているとします。

$$ \begin{bmatrix} 0&0&0&1&0&1&0&1\\ 0&0&0&0&1&1&0&0\\ 1&0&0&1&0&0&0&1\\ 0&0&0&0&1&1&1&0\\ 0&0&1&0&0&1&0&0\\ 0&1&1&0&0&0&1&0\\ 1&0&0&0&1&0&0&0\\ 0&0&1&1&1&0&0&0 \end{bmatrix} $$

f:id:akanekotyui:20210117162038p:plain
Pageのリンクを行列で表した

$$ \begin{bmatrix} 0.1082473558\\ 0.06185563189\\ 0.1701033583\\ 0.1237112638\\ 0.1546390797\\ 0.1855668957\\ 0.1030929669\\ 0.09278344784 \end{bmatrix} $$

f:id:akanekotyui:20210117162122p:plain
(解)PageRank

解き方

【遷移確率行列Mを求める→Mの固有値固有ベクトルを求める→正規化する】

遷移確率行列Mを求める

遷移確率行列は【Aを転置する→各列要素をそれぞれ1ノルムで正規化する】で求められます。

まず与えられた行列(Aとする)をグーグルスプレッドシートにいれます。 入力方法ですがちまちま入力するのはめんどくさいしそのままコピペしても列が別れてくれないので、temp.txtなんかに貼り付けてファイル>インポートします。(スプレッドシートの名前がtempになってしまったので、いい名前をつけてあげてください) 空白文字でも区切り文字を自動的に認識してくれるので良いですね。

転置は関数のTRANSPORTを使うと良いです(A10のセルを参照)。

f:id:akanekotyui:20180520222539p:plain
行列A(A1:H8), 転置A(オレンジ部分)

次に各列要素をそれぞれ1ノルムで正規化します。簡単にいうと列にいくつ1があるか数えてその数で列を割るということです。

関数SUMで足し算をして(A18のセル関数 =SUM(A10:A17))列をSUMで割りました。

f:id:akanekotyui:20180520222642p:plain
転置A(オレンジ部分), 正規化した後の行列M(水色部分)

これで遷移確率行列Mの完成です。dead end (零の列)がないか確認してください。dead endがあるとPageRankは0になってしまいます。

行列Mの固有値固有ベクトルを求める

グーグルスプレッドシートの行列M部分をコピーして超便利な計算サイト 固有値と固有ベクトル - 高精度計算サイト に貼り付けます。

f:id:akanekotyui:20180520215450p:plain 計算すると(10秒くらいかかる) f:id:akanekotyui:20180520215612p:plain 無事固有値1が出て嬉しい。 固有ベクトルをコピーします。

固有値1?となった方は「ランダムサーファー PageRank」で検索するといろいろ出てきます。

名古屋大学の内藤先生の講義資料が体系的でわかりやすいです。おすすめです。 https://www.math.nagoya-u.ac.jp/~naito/lecture/high_school_2011/summer.pdf

正規化する

グーグルスプレッドシートにもどってきて先ほどの固有ベクトルの大きさを1にします。

f:id:akanekotyui:20180520220907p:plain
固有ベクトル(ピンク部分), 正規化した後(選択部分)
C37のセルは=SUM(C29:C36)で1になってます。 選択部分が解になります!ここまで長かった...

まとめ

エクセルで固有値固有ベクトルを求めるやり方もweb上には多数あるので、グーグルスプレッドシートだけでもできるんじゃないかなあと思います。

MATLABを使うとより良いと思うのですが、MATLABよくわからないです!(大学1年生の時に習った)