読者です 読者をやめる 読者になる 読者になる

TEPPEI STUDIO

ENJOY RESTRICTION

GraphX Advent Calendar - Day 17 - 媒介中心性

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

GraphX Advent Calendar 2014 - Adventar 17日目です。 年が明けている気もしますが、気にしないでください。

クラスタリングネタの続きです。前回は、クラスタリングの指標としてモジュラリティについて見てみました。今日からは具体的なクラスタリング手法について見ていきましょう。

まずは、媒介中心性を使ったクラスタリングです。今日は、まずは媒介中心性そのものについて見ていきます。

媒介中心性とは

媒介中心性自体は、頂点の評価手法です。媒介中心性とは、「ネットワークの中で『ハブ』として機能している度合い」を定量的に評価するものです。

例えば、以下のようなネットワークがあった場合、

f:id:teppei-studio:20150103133136p:plain

頂点3と頂点4は、明らかにハブとしての役割を担っていますね。

媒介中心性を使ったクラスタリングは、このハブとなっている頂点でグラフを分割して、クラスタリングする手法で、上の例だと、頂点1、2、3と頂点4、5、6をそれぞれクラスタとして分類します。

媒介中心性の計算方法

媒介中心性は、頂点間の最短経路の中で、ある頂点が経路上にいる割合を、全部の最短経路間の合計値を標準化したものとになります。

例えば、以下のようなグラフがあったとします。

f:id:teppei-studio:20150103135016p:plain

この図において、頂点1を通る最短経路を持つ頂点の組み合わせと、その中で頂点1が最短経路上にいる割合を計算してみます。

経路 最短経路数(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 というのが頂点1の「媒介数」になります。これを標準化した値が、媒介中心性の値となります。

数式は、 Simple Network Analysis Tool 簡易ネットワーク分析ツール を見ていただくのが分かりやすいと思います。

GraphX 実装

媒介中心性の計測にもやはり Pregel を利用します。

まずは、各頂点に持たせるデータの形を見てみたいと思います。

Set[(                       // カウンターとなる頂点毎のリストを持つ
    VertexId,            // カウンター頂点のID
    Set[                    // カウンター頂点との最短経路リスト
        Set[VertexId]  // カウンター頂点との最短経路
    ],
    Int                       // カウンター頂点との最短経路距離 
)]

この情報を隣接頂点間でやりとりします。

やりとりの仕方は、スライドで説明します。

だいぶ複雑ですね。

でも、計算量自体はだいぶ抑えられているんじゃないかと思います。

サンプルソースも結構長くなっているので、リンクを紹介するに留めておきます。
graphx-advent-samples/Day17.scala at master · ironpeace/graphx-advent-samples · GitHub

次回予告

次回は、この媒介中心性を使ったクラスタリングを実際に見てみたいと思います。