# 機能設計書 77-ラベル伝播

## 概要

本ドキュメントは、Apache Spark GraphXにおけるラベル伝播（Label Propagation）アルゴリズムの設計を記述する。

### 本機能の処理概要

ラベル伝播は、グラフ上のコミュニティ検出を行うアルゴリズムである。各ノードは自身のIDをコミュニティラベルとして初期化し、各スーパーステップで全近傍にラベルを送信し、受信した中で最も頻出するラベル（最頻ラベル）を自身の新しいラベルとして採用する。固定回数のスーパーステップで実行される静的実装。

**業務上の目的・背景**：ソーシャルネットワークやWebページクラスタなど、大規模グラフ上でコミュニティ（密結合な部分構造）を検出する必要がある場面で使用される。計算コストが非常に低く、大規模グラフに適用可能。

**機能の利用シーン**：SNSのコミュニティ検出、顧客セグメンテーション、トピッククラスタリング、不正ユーザーグループの検出。

**主要な処理内容**：
1. 各頂点を自身のIDでラベル初期化
2. 各スーパーステップで全近傍にラベルを送信
3. 受信ラベルの出現回数を集計し、最頻ラベルを採用
4. maxSteps回のスーパーステップで終了

**関連システム・外部連携**：GraphXのグラフ構造データ管理（No.71）とPregelフレームワーク（No.79）に依存。

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

## 関連画面

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

## 機能種別

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

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| graph | Graph[VD, ED] | Yes | コミュニティ検出の対象グラフ | - |
| maxSteps | Int | Yes | スーパーステップ数 | > 0 |

### 入力データソース

Graph[VD, ED] - GraphXのグラフ構造。頂点属性VDは破棄される。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Graph[VertexId, ED] | Graph | 頂点属性にコミュニティラベル（頂点ID）を持つグラフ |

### 出力先

メモリ上のGraph RDD

## 処理フロー

### 処理シーケンス

```
1. 初期化
   └─ mapVertices で各頂点を自身のIDで初期化

2. Pregel反復 (maxSteps回)
   ├─ initialMessage: Map[VertexId, Long]() (空マップ)
   ├─ sendMessage: 各エッジで両方向にラベルを送信
   │   ├─ srcId に Map(dstAttr -> 1L)
   │   └─ dstId に Map(srcAttr -> 1L)
   ├─ mergeMessage: 同一ラベルのカウントを合計
   └─ vertexProgram: 最頻ラベルを採用 (message.maxBy(_._2)._1)

3. 結果
   └─ Graph[VertexId, ED] を返却
```

### フローチャート

```mermaid
flowchart TD
    A[入力グラフ] --> B[各頂点を自身のIDで初期化]
    B --> C[Pregel反復開始: maxSteps回]
    C --> D[各エッジで両方向にラベル送信]
    D --> E[ラベルカウント統合]
    E --> F[最頻ラベルを採用]
    F --> G{maxSteps完了?}
    G -->|No| D
    G -->|Yes| H[結果グラフ出力]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-77-01 | 最頻ラベル採用 | 受信ラベルの中で最も頻出するものを新ラベルとして採用 | vertexProgram |
| BR-77-02 | 双方向送信 | 各エッジで両方向にラベルを送信（無向グラフとして扱う） | sendMessage |
| BR-77-03 | 固定反復 | maxStepsで指定した回数だけ反復。収束判定なし | 静的実装 |
| BR-77-04 | 初期メッセージ空の場合 | メッセージが空の場合は現在のラベルを維持 | vertexProgram |

### 計算ロジック

- **sendMessage**: `Iterator((e.srcId, Map(e.dstAttr -> 1L)), (e.dstId, Map(e.srcAttr -> 1L)))` (LabelPropagation.scala 51行目)
- **mergeMessage**: 各ラベルのカウントを合計 (53-63行目)
- **vertexProgram**: `if (message.isEmpty) attr else message.maxBy(_._2)._1` (64-65行目)

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IllegalArgumentException | 入力検証 | maxSteps <= 0 | 正の整数を指定 |

### リトライ仕様

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

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

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

## パフォーマンス要件

- 計算コストが非常に低い（各スーパーステップはO(E)）
- 収束保証なし。trivial solution（全ノードが同一コミュニティ）に陥る可能性がある

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

特になし。

## 備考

- 収束保証がないため、maxStepsの選択が結果品質に影響する
- 結果の非決定性：同じ頻度のラベルが複数ある場合、maxByの結果が不定
- 計算コストの低さから大規模グラフに向いているが、結果の安定性には注意が必要

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | LabelPropagation.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala` | メッセージ型 Map[VertexId, Long] はラベルID -> カウントのマップ |

#### Step 2: アルゴリズム実装を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | LabelPropagation.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala` | run メソッド (46-72行目) |

**主要処理フロー**:
- **47行目**: maxSteps > 0 のバリデーション
- **49行目**: 各頂点を自身のvidで初期化
- **50-52行目**: sendMessage - 両方向にラベルと投票数(1L)を送信
- **53-63行目**: mergeMessage - mutable.Mapを使用して同一ラベルのカウントを合算
- **64-65行目**: vertexProgram - メッセージが空なら現ラベル維持、そうでなければ最頻ラベル
- **67-71行目**: Pregel呼び出し（maxIterations = maxSteps）

**読解のコツ**: mergeMessage内のmutable.Mapの使用（56行目）は、Scala 2.13でbreakOutが削除されたことへの対応。2.12/2.13の両互換を保つための実装パターン。

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

```
LabelPropagation.run(graph, maxSteps)
    |
    +-- graph.mapVertices { (vid, _) => vid }
    +-- Pregel(lpaGraph, Map(), maxIterations = maxSteps)
            +-- vprog: maxBy(カウント)で最頻ラベル
            +-- sendMsg: 両方向にラベル送信
            +-- mergeMsg: カウント合算
```

### データフロー図

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

Graph[VD, ED] ---> 各頂点をvidで初期化 ---> Pregel反復
                                              |
                                      近傍ラベル集計
                                      (最頻ラベル採用)
                                              |
                                              v
                                      Graph[VertexId, ED]
                                      (コミュニティラベル)
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| LabelPropagation.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/LabelPropagation.scala` | ソース | ラベル伝播アルゴリズム実装 |
| Pregel.scala | `graphx/src/main/scala/org/apache/spark/graphx/Pregel.scala` | ソース | 反復計算基盤 |
| Graph.scala | `graphx/src/main/scala/org/apache/spark/graphx/Graph.scala` | ソース | グラフ抽象クラス |
