# 機能設計書 75-三角形カウント

## 概要

本ドキュメントは、Apache Spark GraphXにおける三角形カウント（TriangleCount）アルゴリズムの設計を記述する。

### 本機能の処理概要

三角形カウントは、グラフ中の各頂点を通過する三角形の数を数えるアルゴリズムである。三角形は3つの頂点が互いにエッジで接続された構造で、グラフのクラスタリング係数の計算やコミュニティ構造の分析に使用される。

**業務上の目的・背景**：ソーシャルネットワークの密度分析、コミュニティの結束度測定、不正検出（不正ネットワークは三角形が多い傾向がある）、ネットワークの構造的特性評価などに利用される。

**機能の利用シーン**：SNSの友人推薦（共通の友人が多い＝三角形が多い）、金融取引ネットワークの異常パターン検出、学術的なネットワーク分析。

**主要な処理内容**：
1. グラフの正規化（セルフエッジ除去、正準方向化、重複エッジ除去）
2. 各頂点の近傍集合（VertexSet）を収集
3. 各エッジで両端頂点の近傍集合の交差を計算
4. 交差サイズを各頂点に送信して集約
5. 二重カウントを補正（2で割る）

**関連システム・外部連携**：GraphXのグラフ構造データ管理（No.71）に依存。Pregelは使用せず、aggregateMessagesを直接使用する。

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

## 関連画面

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

## 機能種別

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

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| graph | Graph[VD, ED] | Yes | 三角形カウントの対象グラフ | - |

### 入力データソース

Graph[VD, ED] - GraphXのグラフ構造。頂点属性・エッジ属性は結果に影響しない。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| Graph[Int, ED] | Graph | 頂点属性に通過する三角形の数を持つグラフ |

### 出力先

メモリ上のGraph RDD

## 処理フロー

### 処理シーケンス

```
1. グラフ正規化 (run)
   ├─ mapEdges(e => true) でエッジ属性を軽量化
   ├─ removeSelfEdges() でセルフエッジを除去
   └─ convertToCanonicalEdges() でエッジを正準方向に変換（srcId < dstId）

2. 近傍集合構築 (runPreCanonicalized)
   ├─ collectNeighborIds(EdgeDirection.Either) で各頂点の近傍IDを収集
   └─ VertexSet に変換（セルフ参照を除外）

3. 交差計算
   ├─ setGraph = graph.outerJoinVertices(nbrSets)
   └─ edgeFunc: 小さい方の集合を走査し、大きい方に含まれるIDをカウント
       ├─ ctx.sendToSrc(counter)
       └─ ctx.sendToDst(counter)

4. 集約と補正
   ├─ aggregateMessages(edgeFunc, _ + _) で合計
   ├─ require(dblCount % 2 == 0) で偶数チェック
   └─ dblCount / 2 で二重カウントを補正
```

### フローチャート

```mermaid
flowchart TD
    A[入力グラフ] --> B[セルフエッジ除去]
    B --> C[正準方向化: srcId < dstId]
    C --> D[各頂点の近傍集合を構築]
    D --> E[各エッジで近傍集合の交差計算]
    E --> F[交差サイズを両端頂点に送信]
    F --> G[頂点ごとに合計]
    G --> H[2で割って二重カウント補正]
    H --> I[元グラフにjoinして結果出力]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-75-01 | 正準方向化必須 | 正確な三角形カウントにはセルフエッジなし・正準方向・重複なしが前提 | run使用時は自動適用 |
| BR-75-02 | 小さい集合走査 | 交差計算で小さい方の集合を走査して大きい方を検索。計算効率の最適化 | edgeFunc内 |
| BR-75-03 | 二重カウント補正 | 各三角形は2回カウントされるため最終結果を2で割る | 最終集約後 |
| BR-75-04 | 偶数チェック | 二重カウント結果が偶数でない場合はrequireで検証失敗 | 最終補正時 |

### 計算ロジック

- **交差カウント**: 小さい集合のイテレータを走査し、各要素が大きい集合に含まれ、かつsrcId/dstIdでないものをカウント (TriangleCount.scala 88-104行目)
- **最終カウント**: `dblCount / 2` (113行目)
- **偶数検証**: `require(dblCount % 2 == 0)` (112行目)

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

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

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IllegalArgumentException | 実行時検証 | 二重カウント結果が奇数 | 入力グラフが正準形でない可能性。convertToCanonicalEdgesを事前に実行 |

### リトライ仕様

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

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

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

## パフォーマンス要件

- 正準方向化にはリパーティショニングが必要（コストが高い）。事前に正準化済みの場合はrunPreCanonicalizedを使用
- 近傍集合をVertexSetとしてメモリ保持するため、高次数の頂点ではメモリ使用量が大きくなる
- 交差計算では小さい方の集合を走査する最適化が適用されている

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

特になし。

## 備考

- 入力グラフが既に正準形の場合は`TriangleCount.runPreCanonicalized`を直接呼ぶことで正準化コストを回避可能
- VertexSetはGraphX内部のOpenHashSetベースの効率的な集合実装

---

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

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

### 推奨読解順序

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | TriangleCount.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/TriangleCount.scala` | VertexSet型（OpenHashSetベース）と近傍集合の構築方法 |

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | GraphOps.scala | `graphx/src/main/scala/org/apache/spark/graphx/GraphOps.scala` | triangleCount() メソッド (464-466行目) |
| 2-2 | GraphOps.scala | `graphx/src/main/scala/org/apache/spark/graphx/GraphOps.scala` | convertToCanonicalEdges() メソッド (302-313行目) |

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

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | TriangleCount.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/TriangleCount.scala` | run (54-63行目) と runPreCanonicalized (66-115行目) |

**主要処理フロー**:
- **54-63行目**: run - 正準化後にrunPreCanonicalizedを呼び出し、元グラフにjoin
- **66-80行目**: runPreCanonicalized - collectNeighborIdsで近傍ID収集、VertexSetに変換
- **83-85行目**: setGraph構築 - 近傍集合をグラフの頂点属性として設定
- **88-104行目**: edgeFunc - 小さい集合を走査して交差カウント
- **107行目**: aggregateMessages(edgeFunc, _ + _) で交差カウントを集約
- **109-114行目**: outerJoinVerticesで二重カウントを2で割って結果に結合

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

```
GraphOps.triangleCount()
    |
    +-- TriangleCount.run(graph)
            +-- graph.mapEdges(e => true)
            +-- removeSelfEdges()
            +-- convertToCanonicalEdges()
            +-- runPreCanonicalized(canonicalGraph)
            |       +-- graph.collectNeighborIds(Either)
            |       +-- VertexSet構築
            |       +-- graph.outerJoinVertices(nbrSets) -> setGraph
            |       +-- setGraph.aggregateMessages(edgeFunc, _ + _)
            |       +-- graph.outerJoinVertices(counters) -> dblCount / 2
            +-- graph.outerJoinVertices(counters)
```

### データフロー図

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

Graph[VD, ED] ---> 正準化 --------> 近傍集合構築
                                         |
                                   各エッジで交差計算
                                         |
                                   aggregateMessages
                                   (交差サイズ集約)
                                         |
                                   2で割って補正 -----> Graph[Int, ED]
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| TriangleCount.scala | `graphx/src/main/scala/org/apache/spark/graphx/lib/TriangleCount.scala` | ソース | 三角形カウントアルゴリズム実装 |
| GraphOps.scala | `graphx/src/main/scala/org/apache/spark/graphx/GraphOps.scala` | ソース | triangleCount / convertToCanonicalEdges便利メソッド |
| Graph.scala | `graphx/src/main/scala/org/apache/spark/graphx/Graph.scala` | ソース | aggregateMessages / outerJoinVertices |
