Open yamamoto-yuta opened 10 months ago
# 必要に合わせてコメントアウトを外して記載してください # 記事の説明文(無い場合は本文先頭200文字を使用) #ogp_description: # サムネイル画像のテーマ -> 'default' or 'upload' thumbnail_theme: default # サムネイル画像の背景画像(1280x670px推奨, なくてもOK) #thumbnail_image_url: # 予約投稿の日時(無い場合は現在時刻を使用) #posted_at: YYYY-MM-DD hh:mm
※ この記事は、私が2020/03/03に書いたメモを転記したものです。
その確率がPageRank
重要なページはたくさん引用されるので，↑の確率が高くなる．
例えば，各ページのリンク関係が↓みたいな場合，
$P$ は↓になる
$$ P = \left( \begin{array}{ccc} 0 & 0 & 1/2 & 1/2 & 0 \ 1/2 & 0 & 0 & 1/2 & 0 \ 1/2 & 0 & 0 & 0 & 1/2 \ 1/4 & 1/4 & 1/4 & 0 & 1/4 \ 1/2 & 1/2 & 0 & 0 & 0 \end{array} \right) $$
$t$ 回遷移した時にページ $i$ を開いている確率を $x_{t_i}$ として，各ページでの確率をベクトル $\vec{x_t}$ を用いて次のようにまとめる．
$$ \vec{xt} = \left( \begin{array}{ccc} x{t1} & x{t2} & \cdots & x{t_i} & \cdots \end{array} \right) $$
したがって，t+1回目の遷移は次のように表せる．
$$ \vec{x_{t+1}} = \vec{x_t} P $$
このようにして何回も遷移を繰り返していくと$\vec{x_t}$は一定に収束する．つまり，
$$ \vec{x_t} = \vec{x_t} P $$
となる．
行列 $P$ の固有値 $\lambda$ ，固有ベクト $\vec{x}$ は次のような関係にある．
$$ \vec{x} P = \lambda \vec{x} $$
したがって，固有値 $\lambda = 1$ に対応する固有ベクトルがPageRankとなる（※ PageRankは確率なので後で正規化する必要あり）．
↑で説明した計算方法は最もシンプルなものであり，実際にはもう少し改良がなされている．以下にその改良をいくつか挙げる．
↓のようなネットワークグラフだと②と④で閉ループが形成されていて，まともにPageRankが計算できない．そのため，一定確率でリンクされていないページへジャンプするようになっている．
実際のネットサーフィンでは同じカテゴリのページ間の方が，違うカテゴリのページ間より遷移する可能性が高いと考えられる（例：サッカーのページを開いている人が次に開くページは，同じスポーツカテゴリである野球のページの方が，全く異なるカテゴリである手芸のページより可能性が高い）．
※ この記事は、私が2020/03/03に書いたメモを転記したものです。
PageRankとは？
直感的な理解
その確率がPageRank
重要なページはたくさん引用されるので，↑の確率が高くなる．
計算方法
1. 各ページのリンク関係から遷移確率行列Pを作成
例えば，各ページのリンク関係が↓みたいな場合，
$P$ は↓になる
$$ P = \left( \begin{array}{ccc} 0 & 0 & 1/2 & 1/2 & 0 \ 1/2 & 0 & 0 & 1/2 & 0 \ 1/2 & 0 & 0 & 0 & 1/2 \ 1/4 & 1/4 & 1/4 & 0 & 1/4 \ 1/2 & 1/2 & 0 & 0 & 0 \end{array} \right) $$
2. 遷移確率行列の固有値と固有ベクトルを計算する
2.1. なぜ固有値と固有ベクトルを計算するのか？
$t$ 回遷移した時にページ $i$ を開いている確率を $x_{t_i}$ として，各ページでの確率をベクトル $\vec{x_t}$ を用いて次のようにまとめる．
$$ \vec{xt} = \left( \begin{array}{ccc} x{t1} & x{t2} & \cdots & x{t_i} & \cdots \end{array} \right) $$
したがって，t+1回目の遷移は次のように表せる．
$$ \vec{x_{t+1}} = \vec{x_t} P $$
このようにして何回も遷移を繰り返していくと$\vec{x_t}$は一定に収束する．つまり，
$$ \vec{x_t} = \vec{x_t} P $$
となる．
2.2. 固有値と固有ベクトルを計算する
行列 $P$ の固有値 $\lambda$ ，固有ベクト $\vec{x}$ は次のような関係にある．
$$ \vec{x} P = \lambda \vec{x} $$
したがって，固有値 $\lambda = 1$ に対応する固有ベクトルがPageRankとなる（※ PageRankは確率なので後で正規化する必要あり）．
補足
↑で説明した計算方法は最もシンプルなものであり，実際にはもう少し改良がなされている．以下にその改良をいくつか挙げる．
改良１ ランダムジャンプ
↓のようなネットワークグラフだと②と④で閉ループが形成されていて，まともにPageRankが計算できない．そのため，一定確率でリンクされていないページへジャンプするようになっている．
改良２ カテゴリの概念
実際のネットサーフィンでは同じカテゴリのページ間の方が，違うカテゴリのページ間より遷移する可能性が高いと考えられる（例：サッカーのページを開いている人が次に開くページは，同じスポーツカテゴリである野球のページの方が，全く異なるカテゴリである手芸のページより可能性が高い）．
参考文献