大学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} $$
解
$$ \begin{bmatrix} 0.1082473558\\ 0.06185563189\\ 0.1701033583\\ 0.1237112638\\ 0.1546390797\\ 0.1855668957\\ 0.1030929669\\ 0.09278344784 \end{bmatrix} $$
解き方
【遷移確率行列Mを求める→Mの固有値固有ベクトルを求める→正規化する】
遷移確率行列Mを求める
遷移確率行列は【Aを転置する→各列要素をそれぞれ1ノルムで正規化する】で求められます。
まず与えられた行列(Aとする)をグーグルスプレッドシートにいれます。 入力方法ですがちまちま入力するのはめんどくさいしそのままコピペしても列が別れてくれないので、temp.txtなんかに貼り付けてファイル>インポートします。(スプレッドシートの名前がtempになってしまったので、いい名前をつけてあげてください) 空白文字でも区切り文字を自動的に認識してくれるので良いですね。
転置は関数のTRANSPORTを使うと良いです(A10のセルを参照)。
次に各列要素をそれぞれ1ノルムで正規化します。簡単にいうと列にいくつ1があるか数えてその数で列を割るということです。
関数SUMで足し算をして(A18のセル関数 =SUM(A10:A17))列をSUMで割りました。
これで遷移確率行列Mの完成です。dead end (零の列)がないか確認してください。dead endがあるとPageRankは0になってしまいます。
行列Mの固有値固有ベクトルを求める
グーグルスプレッドシートの行列M部分をコピーして超便利な計算サイト 固有値と固有ベクトル - 高精度計算サイト に貼り付けます。
計算すると(10秒くらいかかる) 無事固有値1が出て嬉しい。 固有ベクトルをコピーします。
固有値1?となった方は「ランダムサーファー PageRank」で検索するといろいろ出てきます。
名古屋大学の内藤先生の講義資料が体系的でわかりやすいです。おすすめです。 https://www.math.nagoya-u.ac.jp/~naito/lecture/high_school_2011/summer.pdf
正規化する
グーグルスプレッドシートにもどってきて先ほどの固有ベクトルの大きさを1にします。 C37のセルは=SUM(C29:C36)で1になってます。 選択部分が解になります!ここまで長かった...
まとめ
エクセルで固有値固有ベクトルを求めるやり方もweb上には多数あるので、グーグルスプレッドシートだけでもできるんじゃないかなあと思います。