TEPPEI STUDIO

ENJOY RESTRICTION

GraphX Advent Calendar - Day 11 - 連結グラフの分類

f:id:teppei-studio:20100306105411j:plain

GraphX Advent Calendar 2014 - Adventar 11日目です。今日はページランクアルゴリズム!と予告していたのですが、ちょっと時間がかかりそうなので、連結グラフの分類について、まずは取り掛かりたいと思います。

連結グラフ( Connected Graph )

連結グラフ(れんけつグラフ, connected graph)は、 グラフ上の任意の2頂点間に道が存在するグラフのことです。 連結でないグラフを非連結グラフ (disconnected graph) と呼びます。 極大で連結な部分グラフは、連結成分 (connected component) といいます。

Graph.connectedComponents

GraphX には、 connectedComponents という関数が用意されています。

例えば、

1 2
2 3
3 1
4 5
5 6
6 7

というグラフがあった時に、

1 2
2 3
3 1

というグラフと、

4 5
5 6
6 4

というグラフに色分けしてくれます。

具体的には、

(1,1)
(2,1)
(3,1)
(4,4)
(5,4)
(6,4)

という風になります。

これは、IDが1〜3の頂点には、1がラベリングされており、4〜6の頂点には、4がラベリングされています。ラベリングの値は、Connected Component の頂点において、一番小さな ID の値がラベリングされています。

ソースコードは、こんな感じになります。

val cc:Graph[Long, Int] = graph.connectedComponents

連結グラフ分類の利用用途

連結グラフ分類は、クラスタリングの一種で、最も分かりやすく分類するクラスタリングです。

クラスタリングとしての利用用途以外に、連結グラフを前提にする処理を行う為の前処理としても使えます。

例えば、「ID2の頂点に n ステップ以内につながっている頂点を抽出する」というような処理を実装する場合、ID2の頂点が含まれる連結グラフに処理対象を絞り込むことができれば、抽出の計算処理を削減することができる可能性があります。

ソースコードは以下のような感じです。

// ID2の頂点に設定されたラベリングを取得
val cc_label_of_vid_2:Long = cc.vertices.filter{case (id, label) => id == 2}.first._2

// そのラベルが設定された頂点を取得する
val vertices_connected_with_vid_2:RDD[(Long, Long)]
  = cc.vertices.filter{case (id, label) => label == cc_label_of_vid_2}

// その頂点の頂点IDだけと取得
val vids_connected_with_vid_2:RDD[Long] = vertices_connected_with_vid_2.map(v => v._1)

// RDDからArrayに変換
val vids_list:Array[Long] = vids_connected_with_vid_2.collect

// 元のグラフから、頂点2が含まれる連結グラフの頂点を抽出する
val graph_include_vid_2
  = graph.subgraph(vpred = (vid, attr) => vids_list.contains(vid))

次回予告

明日こそ、ページランクアルゴリズム!(たぶん)

今日のソースコードはこちらを御参照ください。
graphx-advent-samples/Day11.scala at master · ironpeace/graphx-advent-samples · GitHub