Googleのページランクの計算式｜線形代数
Googleのページランクの計算式は、線形代数Googleのページランクの計算式は、線形代数を用いて以下のように表されます。
基本のページランク方程式
ページランクは、ウェブ上の各ページをノードとして、リンクをエッジとするグラフを考えたときに、各ノード（ページ）の重要度を表す指標です。ページランクベクトル r\mathbf{r} は以下の方程式を満たします。
\[\mathbf{r} = d\,A\,\mathbf{r} + \frac{1 – d}{N}\mathbf{e}\]ここで：
- rはページランクのベクトル（サイズ N×1）であり、各要素は各ページのランクを表します。
- A は遷移行列（サイズ N×N）であり、各要素 aij はページ jからページ iへのリンクがある場合に、その確率（ページ j から出るリンク数の逆数）、ない場合は 0 をとります。
- dはダンピング係数（一般に0.85程度で設定）であり、ランダムにリンクをクリックし続ける確率を示します。これは、ユーザーがランダムに別ページへジャンプする可能性を考慮したものです。
- Nはページ総数です。
- e はすべての要素が1であるサイズ N×1 のベクトルです。
行列の形で明示的に書くと：
\[\mathbf{r} = \frac{1 – d}{N}\mathbf{e}\]したがって、理論上は次のようにして解くことが可能です。
\[\mathbf{r} = (I – dA)^{-1}\frac{1 – d}{N}\mathbf{e}\]ただし、実際にはページ数 N は非常に大きく、行列の逆行列を求める計算は困難であるため、通常はべき乗法（Power Iteration）を用いて反復的に近似計算を行います。
べき乗法による近似（反復法）
以下の式を用いて反復的に求めます。
\[\mathbf{r}^{(k+1)} = dA\mathbf{r}^{(k)} + \frac{1 – d}{N}\mathbf{e}\]この反復計算を繰り返すことで、安定した rに収束します。この収束したベクトルが各ページのページランクとなります。