Graph チュートリアル

ここでは Jubatus のグラフマイニング機能(Graph)である jubagraph を使用した、Jubatus Client の使い方を説明します。

グラフマイニング機能(Graph)とは、与えられたグラフ構造から中心点や最短距離を抽出する機能であり、ソーシャルコミュニティ分析やネットワーク構造分析に用いられます。

サンプルプログラムの概要

鉄道路線の最短経路 (ホップ数) を推定するプログラム「 train_route 」を用いて説明していきます。

最初に、鉄道の接続を表すグラフを作成します。今回は山手線と中央線の接続を表すグラフを作成します。

グラフ作成後に駅名に対応する駅IDが出力されるので、その中から2つの駅IDを指定することで2駅間の最短経路を検索します。

例えば、山手線品川駅から中央線御茶ノ水駅までの経路は、新宿駅で中央線に乗り換えて御茶ノ水駅まで向かう（外回り）パターンと、東京駅で中央線に乗り換えて御茶ノ水駅に向かう（内回り）パターンの2パターンが考えられる。 このプログラムでは、より通過する駅数が少ない経路、つまり東京駅で乗り換える経路を表示します。

処理の流れ

Jubatus Client の使ったコーディングは、主に以下の流れになります。

  1. jubagraph への接続設定
    jubagraph のホストやポート番号を指定し、接続設定をします。
  2. プリセットクエリーを登録
    最短パスの算出に使用したいクエリーを新たに登録します。
  3. グラフの作成
    山手線、中央線の駅間接続情報を取得し、グラフを作成します。
  4. 駅IDの表示
    3. でグラフを作成時に登録した駅名に対応する駅IDを表示します。
  5. クエリーの準備
    最短経路を計算するためのクエリーを準備します。
  6. 最短経路を計算
    2駅間の最短経路を計算します。
  7. 結果の表示
    6. での計算結果を出力します。

サンプルプログラム

現在、Python 以外の言語のサンプルプログラムはありません。(みなさまのコントリビューションをお待ちしています!)