グラフ描画

グラフ理論のグラフはノードの集合とリンクの集合によって表されます。グラフに含まれてるノード同士がリンクによって接続されています。

グラフはそのようなつながりの関係のみを持ちますが、グラフがどのような構造を持っているかを視覚的に表現したい場合には、2 次元や 3 次元空間でノードとリンクを描画する必要があります。直接的に、画面にノードを描画し、ノード間につながるリンクを線でつなぐような表現を ノードリンク図 と呼びます。ノードリンク図を描くためには、ノードをどこに配置するかどうかを決定する必要があります。このような、ノード配置を行う方法を グラフ描画 （Graph Drawing）と呼びます。グラフのどのような特徴を強調するかに応じて、様々なグラフ描画手法が考えられています。グラフ構造の可視化は、世の中に存在する様々なネットワーク構造を持ったデータの理解に役立てることができます。

グラフ描画の一つのアプローチとして、ノード間に働く力をシミュレーションすることでノードの座標を決定する方法があります。このようなアプローチは Force-directed アルゴリズム と呼ばれます。 Force-directed アルゴリズムのもっとも基本的な方法の一つは、ノード間をつなぐリンクをバネと見立ててその運動をシミュレーションすることです。このような方法は バネモデル とも呼ばれます。バネモデルを用いたグラフ描画としては Eades の方法が有名です。しかし、本講義では Verlet 法により容易に実装できるようにバネモデルをアレンジしています。

バネモデルのシミュレーションの前に、グラフのプログラム上での表現を考えましょう。ノードについては、ノードの個数分の座標と速度を配列として保持しておく必要があります。これは複数の物体の運動と同様になります。リンクについては、どのノードとどのノードがつながっているか、一方のノードの添字 source ともう一方のノードの添字 target をそれぞれ整数型の配列で表すことができます。

次にバネモデルのシミュレーションについて考えます。まずはじめに、ノードの初期座標を適当に与えておく必要があります。これはrandom関数を用いてランダムに決めることが可能です。次に、全てのリンクに対してフックの法則に従う力の計算を行いますが、それだけでは座標がうまく収束しません。そのため、空気抵抗の影響を与えることでノードの座標が静止状態になるまで繰り返しを行います。また、いずれのノードも固定されていないため、ノードの位置が表示可能な画面の領域から遠く離れていく場合も考えられます。これを回避するために、速度の更新の際に、全てのノードの重心が画面中央にくるように全ての座標の平行移動を行います。

完全グラフ $K_3$ のバネモデルによって可視化するプログラムは以下のようになります。

See the Pen コンピューティング2 5-16 by Yosuke Onoue (@likr) on CodePen.

ノードとリンクの情報を修正して別のグラフを可視化してみます。

See the Pen コンピューティング2 5-17 by Yosuke Onoue (@likr) on CodePen.

うまくいけば以下のような配置になります。

一方で、ノードの初期位置によっては以下のように重なりが生じたりします。

ネットワーク可視化へのクーロン力の導入

前回、バネの力だけではネットワークのノードに重なりが生じて、ノード配置がうまくいかない場合がありました。クーロン力を用いてノード間の反発力を計算することでノードの重なりを回避してみましょう。ノードが全て同じ符号の電荷を持っているとします。 i 番目のノードには、j 番目のノードから、電荷に比例して距離の 2 乗に反比例する加速度が働きます。

See the Pen コンピューティング2 5-18 by Yosuke Onoue (@likr) on CodePen.

ノード間の反発力を導入することでノードを均等に配置できるようになりました。

グラフの生成

ランダムに生成したグラフを Force-directed アルゴリズムで可視化してみます。以下のプログラムでは、10 頂点のグラフにおいて、全ての頂点ペアが 0.5 の確率でリンクを持つようにランダムにグラフを生成しています。

See the Pen コンピューティング2 5-19 by Yosuke Onoue (@likr) on CodePen.

閉路を持たないグラフを木と呼びます。以下は 100 ノードの木をランダムに生成し、Force-directed アルゴリズムによって可視化するプログラムです。

See the Pen コンピューティング2 5-20 by Yosuke Onoue (@likr) on CodePen.

ここで、以下の 2 つの問題に気づきます。

ノード数が多いとノード座標が収束しにくい
グラフが非連結の場合に、それぞれの連結成分が離れていく

次にこれらの解決方法を考えていきます。

アニーリング（焼きなまし）

空気抵抗力を受けることでノードの座標は収束していきます。そのため、空気抵抗係数を大きくすればノードは速く停止します。しかし、最初から空気抵抗係数が大きければノードが綺麗に配置される前に停止してしまいます。そこで、最初は空気抵抗係数を小さくして、徐々に大きくしていく方法をとります。このような方法を アニーリング と呼びます。

空気抵抗係数を徐々に大きくしていくには様々な方法が考えられます。ここでは、係数 $0 \leq \alpha \leq 1$ に対して空気抵抗係数を $k = 1 - \alpha$ とします。そして、 $\alpha = 1$ からはじまり、 $\alpha \leftarrow e \alpha \quad (0 < e < 1)$ と更新していくことで空気抵抗係数を大きくしていきます。

See the Pen コンピューティング2 5-21 by Yosuke Onoue (@likr) on CodePen.