Press "Enter" to skip to content

gonum graph を用いて Ego Graph を求める

Ego Graph は Neighborhood Graph とも呼ばれるもので、グラフGの中からノードを1つ選び、そのノードから距離 k までの範囲に含まれるノードの集合で構成されるグラフのことになります。

たとえば

このグラフでノード0に関して、1ホップまでの範囲内にあるグラフは

となります。

今回はこの計算をGo言語の gonum graph パッケージを用いて実装しようと思います。

Sink Tree と Ego Graph

Ego Graph の実装は Dijkstra 法を活用します。Dijkstra 方は最短経路問題を解く手法として有名ですが、その背景には Sink Tree と呼ばれる木構造があり、 Ego Graph はその Sink Tree の部分グラフとして扱うことができるためです。

Sink Tree

まず、最短経路問題には 「ノードIからノードKまでの最短経路上にノードJが存在する場合、ノードJからノードKまでの最短経路もまた同じ経路をたどる」 という性質があります。これは 最適化原理 に基づくものになります。ここから得られる結論として 「ある宛先へと向かうすべての送信元からの最適経路は、宛先を根とするツリー構造になる」 ということが言えます。これが Sink Tree になります。

たとえばこの図の場合

  • ノードHからノードBまでの最短経路上にノードDが存在する場合、ノードDからノードBまでの最短経路もまた同じ経路をたどる

といったことが言え、その結果それぞれのノードからBへの最短経路(逆に言えばノードBからそれぞれのノードへの最短経路)を重ね合わせると、(b)のようにツリー構造が出来上がります。

Ego Graph の求め方

Ego Graph は Sink Tree の部分グラフ になります。そのため Sink Tree が求まったあとに Ego Graph の範囲に収まる部分だけを取り出せば良いことがわかります。

ただし、実際には Sink Tree を完成させてから Ego Graph 部分を取り出す必要はありません。最短経路問題を解く Dijkstra 法は Sink Tree を少しずつ伸ばしていく形で計算を進めていくため、 計算途中で Sink Tree のサイズが求める Ego Graph よりも大きくなれば計算を終了してしまえば良い ことになります。

Ego Graph の実装

今回は gonum graph の Dijkstra 法の実装をベースに Ego Graph を出力するプログラムを作成します。

gonum graph に実装されている Dijkstra 法は優先度付きキューを用いた実装になっています。その疑似コードは Wikipedia にも説明があります(それぞれの文字の定義は Wikipedia の法を参照してください)。

Ego Graph を求める際にはこの擬似コードにおいて

  1. QからQ(u)が最小である頂点uを取り出す。ここで取り出した頂点の値が Ego Graph の範囲と定めている値よりも大きい場合、while ループを抜ける
  2. Dijkstra法の実行途中の状態が得られ、 prev(v) の情報をもとに Ego Graph を作成する

ということを行います。

コード

具体的に gonum graph における Dijkstra 法のコードを見てみます。

さきほどの「QからQ(u)が最小である頂点uを取り出す」操作はちょうど42行目の優先度付きキューからの取り出し操作が該当します。 したがってここで取り出した値が Ego Graph の範囲よりも大きい場合に for ループを抜け出します。

また、これらの計算処理のあとにグラフを出力するための処理も加えます。

その結果、今回はこのような関数を作りました。

このコードは path パッケージ内に記述する必要があり、今回は dijkstra.go の中に書き加えました。

結果を確認してみる

次のグラフで確認してみます。


(視覚化は Python の NetworkX を使っています)

次のプログラムを実行してノード11を中心に、距離100までの範囲における Ego Graph を確認してみます。

確かに距離100以下の Ego Graph が得られていることが確認できます。

Be First to Comment

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です