PageRankの数学（固有値問題としてのウェブ検索）

Q: PageRankの数学（固有値問題としてのウェブ検索）とは何ですか？

N 個のページから成るウェブを考える。ページ j から出ているリンクの数を L(j) とし、ページ j から i へのリンクが存在するとき遷移確率を \frac{1}{L(j)} とする「遷移行列（列確率行列）」M を定義する。ダンピングファクター d（通常 d \approx 0.85）を用いたPageRankは、次の連立方程式（固有値問題）の解として定義される。\mathbf{r} = d \, M \mathbf{r} + \frac{1-d}{N}\mathbf{1} ここで \mathbf{r} = (r_1, \ldots, r_N)^\top は各ページのランクを成分に持つベクトルであり、\sum_i r_i = 1 を満たす確率分布である。ダンピング項がない単純な形では、この式は「M\mathbf{r} = \mathbf{r}」、すなわち \mathbf{r} が行列 M の固有値 1 に対応する固有ベクトルであることを意味する。

Q: PageRankの数学（固有値問題としてのウェブ検索）は社会やプログラミングでどのように使われていますか？

検索エンジンにおけるPageRankのべき乗法（Power Iteration）実装: 小さなウェブリンクグラフから遷移確率行列を構築し、ダンピングファクターを考慮したべき乗法でPageRankベクトルが収束するまで反復計算する、Googleの検索エンジンの基礎アルゴリズムを模したTypeScript実装。

リンク構造を確率行列とみなし、繰り返し掛け算するだけでページの重要度が浮かび上がる仕組み

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: PageRankは、ウェブページ間のリンク構造を「遷移確率行列」とみなし、ランダムにリンクをたどり続けるユーザーが各ページに滞在する確率をページの重要度スコアとする
2: 遷移行列を初期のランクベクトルに繰り返し掛け続ける「べき乗法（power iteration）」を行うと、ベクトルは行列の最大固有値（=1）に対応する固有ベクトル（定常分布）へ収束していく
3: リンクを多く集めたページほど、また重要なページからリンクされたページほど高いランクを得る、という再帰的な定義が固有値問題として厳密に解ける

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

PageRankは、ウェブページ間のリンク構造を「遷移確率行列」とみなし、ランダムにリンクをたどり続けるユーザーが各ページに滞在する確率をページの重要度スコアとする

身につく武器・思考力

遷移行列を初期のランクベクトルに繰り返し掛け続ける「べき乗法（power iteration）」を行うと、ベクトルは行列の最大固有値（=1）に対応する固有ベクトル（定常分布）へ収束していく

実社会・ITでの活躍現場

•検索エンジンにおけるPageRankのべき乗法（Power Iteration）実装
•ITシステム・アルゴリズム実装における論理設計
•データ分析やシミュレーションにおける数理モデリング

Layer 1 — 直感・シミュレーター

5つのウェブページ（ノード）とそれらを結ぶリンク（矢印）から成る小さなネットワークが表示されている。各ページのランクは最初すべて均等（0.2）から始まる。「1ステップ反復」ボタンを押すたびに遷移行列がランクベクトルに掛けられ、下の棒グラフが変化していく。「収束するまで実行」ボタンで、ランクが安定するまで自動的に反復計算が繰り返される様子を観察しよう。

べき乗法でランクベクトルが遷移行列に繰り返し掛けられ、定常分布へ収束していく様子を観察しよう。反復回数: 0

PageRankベクトル

\mathbf{r}^{(t)}

0.2000

↑ 遷移行列 M をランクベクトルに繰り返し掛ける「べき乗法」により、ベクトルは M の最大固有値（=1）に対応する固有ベクトル（定常分布）へ収束します。多くのページからリンクされ、かつリンク元も重要なページ（C）のランクが高くなる様子が確認できます。

直感チェック！ミニクイズ

べき乗法によってPageRankベクトルを繰り返し計算していくと、最終的にベクトルはどうなるか？

Layer 2 — 定義・受験・証明

定義

$N$ 個のページから成るウェブを考える。ページ $j$ から出ているリンクの数を $L(j)$ とし、ページ $j$ から $i$ へのリンクが存在するとき遷移確率を $\frac{1}{L(j)}$ とする「遷移行列（列確率行列）」 $M$ を定義する。ダンピングファクター $d$ （通常 $d \approx 0.85$ ）を用いたPageRankは、次の連立方程式（固有値問題）の解として定義される。

\mathbf{r} = d \, M \mathbf{r} + \frac{1-d}{N}\mathbf{1}

ここで $\mathbf{r} = (r_1, \ldots, r_N)^\top$ は各ページのランクを成分に持つベクトルであり、 $\sum_i r_i = 1$ を満たす確率分布である。ダンピング項がない単純な形では、この式は「 $M\mathbf{r} = \mathbf{r}$ 」、すなわち $\mathbf{r}$ が行列 $M$ の固有値 $1$ に対応する固有ベクトルであることを意味する。

公式・数理モデル

\mathbf{r} = d \, M \mathbf{r} + \frac{1-d}{N}\mathbf{1}, \qquad \mathbf{r}^{(t+1)} = M\, \mathbf{r}^{(t)} \;\xrightarrow{t\to\infty}\; \mathbf{r}^{*}

証明・導出

べき乗法（power iteration）が固有ベクトルへ収束することの証明： $M$ を対角化可能な $N\times N$ 行列とし、固有値を大きさの順に $|\lambda_1| > |\lambda_2| \ge \cdots \ge |\lambda_N|$ 、対応する固有ベクトルを $\mathbf v_1, \ldots, \mathbf v_N$ とする（ペロン・フロベニウスの定理より、列和が1の非負行列 $M$ の最大固有値は $\lambda_1 = 1$ である）。初期ベクトル $\mathbf{r}^{(0)}$ を固有ベクトルの線形結合として $\mathbf{r}^{(0)} = c_1 \mathbf v_1 + c_2 \mathbf v_2 + \cdots + c_N \mathbf v_N$ と表すと（ $c_1 \ne 0$ と仮定）、

\mathbf{r}^{(t)} = M^t \mathbf{r}^{(0)} = c_1 \lambda_1^t \mathbf v_1 + c_2 \lambda_2^t \mathbf v_2 + \cdots + c_N \lambda_N^t \mathbf v_N

両辺を $\lambda_1^t = 1^t = 1$ で割ると、

\mathbf{r}^{(t)} = c_1 \mathbf v_1 + c_2 \left(\frac{\lambda_2}{\lambda_1}\right)^t \mathbf v_2 + \cdots

$|\lambda_2/\lambda_1| < 1$ であるため、 $t \to \infty$ のとき第2項以降はすべて $0$ に収束し、 $\mathbf{r}^{(t)} \to c_1 \mathbf v_1$ となる。すなわちべき乗法の反復は最大固有値に対応する固有ベクトル（定常分布）へ指数関数的に収束する。ダンピングファクター $d<1$ を導入すると $M$ が既約かつ非周期的になり、収束がさらに保証される。

押さえておきたいポイント

PageRankの本質は「重要なページからリンクされたページは重要」という再帰的な定義を、固有値問題として厳密に解く点にある
ダンピングファクター $d$ （Googleの原論文では0.85）は、ランダムサーファーが一定確率でリンクをたどらず全く別のページへ「テレポート」する挙動をモデル化し、行き止まりページ（out-linkが無いページ）での収束の不安定性を解消する
収束速度は固有値の比 $|\lambda_2/\lambda_1|$ に依存し、この比が小さいほど少ない反復回数で収束する
同様の「べき乗法による固有ベクトル収束」の考え方は、推薦システムの行列分解や画像圧縮の特異値分解（SVD）にも応用されている

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

検索エンジンにおけるPageRankのべき乗法（Power Iteration）実装

小さなウェブリンクグラフから遷移確率行列を構築し、ダンピングファクターを考慮したべき乗法でPageRankベクトルが収束するまで反復計算する、Googleの検索エンジンの基礎アルゴリズムを模したTypeScript実装。

1// リンクグラフ: キーがページ、値がリンク先ページの配列
2const links: Record<string, string[]> = {
3  A: ["B", "C"],
4  B: ["C"],
5  C: ["A"],
6  D: ["C"],
7};
8
9const pages = Object.keys(links);
10const N = pages.length;
11const damping = 0.85;
12
13// 遷移行列 M を構築（列 j から行 i への確率 = 1 / L(j)）
14function buildTransitionMatrix(): number[][] {
15  const M: number[][] = Array.from({ length: N }, () => new Array(N).fill(0));
16  pages.forEach((page, j) => {
17    const outLinks = links[page];
18    if (outLinks.length === 0) return;
19    outLinks.forEach((target) => {
20      const i = pages.indexOf(target);
21      M[i][j] = 1 / outLinks.length;
22    });
23  });
24  return M;
25}
26
27// べき乗法によるPageRank計算
28function computePageRank(iterations = 50): number[] {
29  const M = buildTransitionMatrix();
30  let rank = new Array(N).fill(1 / N); // 初期値: 均等な確率分布
31
32  for (let t = 0; t < iterations; t++) {
33    const next = new Array(N).fill((1 - damping) / N);
34    for (let i = 0; i < N; i++) {
35      for (let j = 0; j < N; j++) {
36        next[i] += damping * M[i][j] * rank[j];
37      }
38    }
39    rank = next;
40  }
41  return rank;
42}
43
44const ranks = computePageRank();
45pages.forEach((page, i) => console.log(`${page}: ${ranks[i].toFixed(4)}`));
46// 出力例: C が最も多くリンクを集め、最上位のランクに収束する