GraphX Advent Calendar - Day 17 - 媒介中心性
GraphX Advent Calendar 2014 - Adventar 17日目です。 年が明けている気もしますが、気にしないでください。
クラスタリングネタの続きです。前回は、クラスタリングの指標としてモジュラリティについて見てみました。今日からは具体的なクラスタリング手法について見ていきましょう。
まずは、媒介中心性を使ったクラスタリングです。今日は、まずは媒介中心性そのものについて見ていきます。
媒介中心性とは
媒介中心性自体は、頂点の評価手法です。媒介中心性とは、「ネットワークの中で『ハブ』として機能している度合い」を定量的に評価するものです。
例えば、以下のようなネットワークがあった場合、
頂点３と頂点４は、明らかにハブとしての役割を担っていますね。
媒介中心性を使ったクラスタリングは、このハブとなっている頂点でグラフを分割して、クラスタリングする手法で、上の例だと、頂点１、２、３と頂点４、５、６をそれぞれクラスタとして分類します。
媒介中心性の計算方法
媒介中心性は、頂点間の最短経路の中で、ある頂点が経路上にいる割合を、全部の最短経路間の合計値を標準化したものとになります。
例えば、以下のようなグラフがあったとします。
この図において、頂点１を通る最短経路を持つ頂点の組み合わせと、その中で頂点１が最短経路上にいる割合を計算してみます。
| 経路 | 最短経路数(A) | 最短経路のうち頂点1を通る経路数(B) | B / A (C) |
|---|---|---|---|
| 0 ←→ 2 | 1 | 1 | 1 |
| 0 ←→ 4 | 1 | 1 | 1 |
| 0 ←→ 3 | 2 | 2 | 1 |
| 3 ←→ 4 | 2 | 1 | 0.5 |
上記の表のうちの、「C」の値を合計した 3.5 というのが頂点１の「媒介数」になります。これを標準化した値が、媒介中心性の値となります。
数式は、 Simple Network Analｙsis Tool 簡易ネットワーク分析ツール を見ていただくのが分かりやすいと思います。
GraphX 実装
媒介中心性の計測にもやはり Pregel を利用します。
まずは、各頂点に持たせるデータの形を見てみたいと思います。
Set[( // カウンターとなる頂点毎のリストを持つ VertexId, // カウンター頂点のID Set[ // カウンター頂点との最短経路リスト Set[VertexId] // カウンター頂点との最短経路 ], Int // カウンター頂点との最短経路距離 )]
この情報を隣接頂点間でやりとりします。
やりとりの仕方は、スライドで説明します。
だいぶ複雑ですね。
でも、計算量自体はだいぶ抑えられているんじゃないかと思います。
サンプルソースも結構長くなっているので、リンクを紹介するに留めておきます。
graphx-advent-samples/Day17.scala at master · ironpeace/graphx-advent-samples · GitHub
次回予告
次回は、この媒介中心性を使ったクラスタリングを実際に見てみたいと思います。
