# 機能設計書 72-PageRankアルゴリズム

## 概要

本ドキュメントは、Apache Spark GraphXにおけるPageRankアルゴリズムの設計を記述する。グラフ上の各頂点の重要度スコアを算出するPageRank計算の仕様を定義する。

### 本機能の処理概要

PageRankは、グラフ上の各頂点の重要度を数値化するアルゴリズムである。GraphXでは固定回数反復版と収束判定版の2つの実装が提供されており、通常のPageRank、パーソナライズドPageRank、並列パーソナライズドPageRankの3種類のバリエーションをサポートする。

**業務上の目的・背景**：Webページの重要度ランキング、ソーシャルネットワークにおけるインフルエンサー特定、学術論文の被引用分析、通信ネットワークにおけるハブ特定など、グラフ構造上のノードの相対的重要度を定量化する必要がある場面で使用される。

**機能の利用シーン**：Webクローラーが収集したリンクグラフに対するページランク計算、SNSの影響力分析、推薦システムにおけるアイテム重要度計算、知識グラフにおけるエンティティ重要度の算出。

**主要な処理内容**：
1. グラフの初期化（出次数に基づくエッジ重み正規化、初期PageRank値の設定）
2. 反復計算（各頂点のランク値を隣接頂点からの寄与で更新）
3. 収束判定（動的版）またはイテレーション回数制御（静的版）
4. シンクノード補正（出辺のない頂点に対するランク合計の正規化）
5. パーソナライズドPageRankではソース頂点へのバイアスを適用

**関連システム・外部連携**：GraphXのグラフ構造データ管理（No.71）とPregelフレームワーク（No.79）に依存する。収束判定版はPregelを使用して実装されている。

**権限による制御**：特に権限による制御は行われない。

## 関連画面

本機能に直接関連するUI画面はない。

## 機能種別

計算処理 / グラフアルゴリズム

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| graph | Graph[VD, ED] | Yes | PageRankを計算する対象グラフ | - |
| numIter | Int | Yes(静的版) | イテレーション回数 | > 0 |
| tol | Double | Yes(動的版) | 収束許容誤差 | >= 0 |
| resetProb | Double | No | ランダムリセット確率（デフォルト: 0.15） | [0, 1] |
| srcId | Option[VertexId] | No | パーソナライズドPageRankのソース頂点 | - |
| sources | Array[VertexId] | Yes(並列版) | 並列パーソナライズドPageRankのソース頂点配列 | 非空 |
| normalized | Boolean | No | ランク合計を正規化するか（デフォルト: true） | - |

### 入力データソース

Graph[VD, ED] - GraphXのグラフ構造。頂点属性VDとエッジ属性EDは計算に使用されず、結果のグラフではDouble型に置き換えられる。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Graph[Double, Double] | Graph | 頂点属性にPageRankスコア、エッジ属性に正規化エッジ重みを持つグラフ |
| Graph[Vector, Double] | Graph | 並列版: 頂点属性にソースごとのPageRankベクトル |

### 出力先

メモリ上のGraph RDD

## 処理フロー

### 処理シーケンス

```
1. 初期化
   ├─ 出次数を計算 (graph.outDegrees)
   ├─ エッジ重みを正規化 (1.0 / outDegree)
   └─ 初期PageRank値を設定 (通常: 1.0, パーソナライズド: ソース頂点のみ1.0)

2a. 静的版 (runWithOptions)
   ├─ numIter回繰り返し:
   │   ├─ aggregateMessages でランク寄与を送信・集約
   │   ├─ outerJoinVertices で新ランク値を計算
   │   │   └─ rPrb(src, id) + (1 - resetProb) * msgSum
   │   └─ 前回のグラフをunpersist
   └─ normalizeRankSum でシンクノード補正

2b. 動的版 (runUntilConvergenceWithOptions)
   ├─ Pregel を使用した反復
   │   ├─ vertexProgram: oldPR + (1 - resetProb) * msgSum
   │   ├─ sendMessage: delta > tol の場合のみメッセージ送信
   │   └─ messageCombiner: 合計
   └─ normalizeRankSum でシンクノード補正

3. シンクノード補正
   ├─ ランク合計を計算
   ├─ パーソナライズド: 全頂点のランクをランク合計で割る
   └─ 通常: numVertices / rankSum の補正係数を乗算
```

### フローチャート

```mermaid
flowchart TD
    A[入力グラフ] --> B[出次数計算]
    B --> C[エッジ重み正規化: 1/outDegree]
    C --> D[初期ランク値設定]
    D --> E{実行モード}
    E -->|静的版| F[固定回数反復]
    E -->|動的版| G[Pregel収束反復]
    F --> H[aggregateMessages + outerJoinVertices]
    H --> I{残り反復あり?}
    I -->|Yes| H
    I -->|No| J[normalizeRankSum]
    G --> J
    J --> K[結果グラフ出力]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-72-01 | PageRank公式 | PR[i] = alpha + (1 - alpha) * sum(PR[j] / outDeg[j]) for j in inNbrs[i] | 全頂点 |
| BR-72-02 | シンクノード補正 | 出辺のない頂点によるランクロスを補正。通常版: numVertices/rankSum倍。パーソナライズド版: 1/rankSum倍 | SPARK-18847 |
| BR-72-03 | 収束条件 | 動的版ではdelta(=newPR - oldPR) > tol の頂点のみメッセージ送信 | 動的版 |
| BR-72-04 | パーソナライズド | ソース頂点のみresetProbでリセット、他の頂点は0にリセット | srcId指定時 |

### 計算ロジック

- **静的版ランク更新**: `rPrb(src, id) + (1.0 - resetProb) * msgSumOpt.getOrElse(0.0)` (PageRank.scala 121行目)
- **rPrb(通常)**: `resetProb` (定数)
- **rPrb(パーソナライズド)**: `resetProb * delta(src, id)` (srcとidが一致する場合1.0、それ以外0.0)
- **normalizeRankSum(通常)**: `rank * (numVertices / rankSum)` (PageRank.scala 509-510行目)
- **normalizeRankSum(パーソナライズド)**: `rank / rankSum` (PageRank.scala 506行目)

## データベース操作仕様

GraphXはデータベースを直接操作しない。

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IllegalArgumentException | 入力検証 | numIter <= 0 | 正の整数を指定 |
| IllegalArgumentException | 入力検証 | resetProb < 0 または > 1 | [0, 1]の範囲を指定 |
| IllegalArgumentException | 入力検証 | tol < 0（動的版） | 0以上を指定 |
| IllegalArgumentException | 入力検証 | sources配列が空（並列版） | 非空の配列を指定 |
| IllegalArgumentException | 入力検証 | graphとpreRankGraphの頂点数不一致 | 同一頂点数のグラフを使用 |

### リトライ仕様

RDDの耐障害性メカニズムに従う。

## トランザクション仕様

トランザクション機構は存在しない。

## パフォーマンス要件

- 各イテレーションでcache()による中間結果の永続化
- 前イテレーションのグラフは明示的にunpersistして解放
- 動的版ではアクティブな頂点のみメッセージを送信するため、収束に近づくと計算量が減少
- 並列パーソナライズドPageRankはsourcesをbroadcast変数として配布

## セキュリティ考慮事項

特になし。SparkContextの認証・認可メカニズムに従う。

## 備考

- SPARK-18847: シンクノード（出辺なし頂点）がある場合のランク合計補正が実装されている
- 前回のPageRank結果を初期値として再利用するrunWithOptionsWithPreviousPageRankメソッドがある

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

PageRankの入出力となるグラフのデータ型を確認する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | Graph.scala | `graphx/src/main/scala/org/apache/spark/graphx/Graph.scala` | Graph[VD, ED]型、特にaggregateMessagesとouterJoinVerticesメソッド |

**読解のコツ**: PageRankの結果はGraph[Double, Double]で、頂点属性がPageRankスコア、エッジ属性が正規化重み（1/outDegree）。

#### Step 2: エントリーポイントを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | GraphOps.scala | `graphx/src/main/scala/org/apache/spark/graphx/GraphOps.scala` | pageRank, staticPageRank等の便利メソッドがPageRank objectに委譲される様子 |

**主要処理フロー**:
1. **379-381行目**: pageRank(tol) -> PageRank.runUntilConvergence
2. **423-425行目**: staticPageRank(numIter) -> PageRank.run

#### Step 3: PageRank実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | PageRank.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/PageRank.scala` | 3つの実装（静的版、動的版、並列パーソナライズド版）の詳細 |

**主要処理フロー**:
- **83-87行目**: run メソッド - runWithOptionsに委譲
- **102-123行目**: runUpdate - 1イテレーション分のランク更新。aggregateMessagesでランク寄与を集約し、outerJoinVerticesで更新
- **167-214行目**: runWithOptions(静的版) - 初期化、反復、正規化の一連の処理
- **427-500行目**: runUntilConvergenceWithOptions(動的版) - Pregelを使用した収束判定付き実装
- **326-390行目**: runParallelPersonalizedPageRank(並列版) - Breezeベクトルを使用
- **502-512行目**: normalizeRankSum - シンクノード補正

#### Step 4: Pregel（動的版の基盤）を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | Pregel.scala | `graphx/src/main/scala/org/apache/spark/graphx/Pregel.scala` | 動的版PageRankが使用するPregelの反復メカニズム |

### プログラム呼び出し階層図

```
GraphOps.pageRank(tol)
    |
    +-- PageRank.runUntilConvergence(graph, tol, resetProb)
            +-- runUntilConvergenceWithOptions(graph, tol, resetProb, None)
                    +-- graph.outerJoinVertices(graph.outDegrees) [初期化]
                    +-- Pregel(pagerankGraph, initialMessage, ...)
                    |       +-- vertexProgram / personalizedVertexProgram
                    |       +-- sendMessage [delta > tol のみ]
                    |       +-- messageCombiner [合計]
                    +-- normalizeRankSum(rankGraph, personalized)

GraphOps.staticPageRank(numIter)
    |
    +-- PageRank.run(graph, numIter, resetProb)
            +-- runWithOptions(graph, numIter, resetProb, None)
                    +-- graph.outerJoinVertices(graph.outDegrees) [初期化]
                    +-- while (iteration < numIter):
                    |       +-- runUpdate(rankGraph, ...)
                    |               +-- rankGraph.aggregateMessages [ランク寄与集約]
                    |               +-- rankGraph.outerJoinVertices [ランク更新]
                    +-- normalizeRankSum(rankGraph, personalized)
```

### データフロー図

```
[入力]                   [処理]                           [出力]

Graph[VD, ED] -------> 出次数計算 --------> エッジ重み正規化
                           |                     |
                           v                     v
                    初期ランク値設定 ----> 反復ランク更新
                                              |
                                    aggregateMessages
                                    (ランク寄与集約)
                                              |
                                    outerJoinVertices
                                    (新ランク計算)
                                              |
                                    normalizeRankSum -----> Graph[Double, Double]
                                    (シンクノード補正)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| PageRank.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/PageRank.scala` | ソース | PageRankアルゴリズム実装 |
| Graph.scala | `graphx/src/main/scala/org/apache/spark/graphx/Graph.scala` | ソース | グラフ抽象クラス |
| GraphOps.scala | `graphx/src/main/scala/org/apache/spark/graphx/GraphOps.scala` | ソース | PageRank便利メソッド |
| Pregel.scala | `graphx/src/main/scala/org/apache/spark/graphx/Pregel.scala` | ソース | 動的版の基盤フレームワーク |
| GraphImpl.scala | `graphx/src/main/scala/org/apache/spark/graphx/impl/GraphImpl.scala` | ソース | aggregateMessages実装 |
