力学モデルを用いたグラフデータの視覚化手法の改良

研究内容

グラフデータの視覚化結果の読みやすさは、 グラフデータを構成するノードの配置結果に大きく依存します。 読みやすいノードの配置を実現するために、 まず以下の３条件を掲げてみました。

[条件1] 近隣ノードが一定以上の距離を保つ。
[条件2] アークの長さの総和をできるだけ短くする。
[条件3] アークが端点以外の場所で別のノードと重ならないようにする。

この条件を満たさない配置結果と、条件を満たす配置結果を、 まったく同じ接続関係をもつグラフデータのイラストで比較してみましょう。 言うまでもなく、条件を満たす配置結果のほうが、 スッキリと読みやすい視覚化結果に仕上がっています。

条件を満たさない配置結果。	条件を満たす配置結果。

以上の条件のいくつかを、ある程度満たすような配置結果を、 比較的高速に算出する手法として、 力学モデルを用いた手法が以前から知られています。 この手法では、以下の図でも示す通り、

• 近隣ノード間が一定以上の距離を保つように、 近隣ノードに対して斥力を発生する、分子間力に類似した力学モデル。
• ノードを接続するアークが適切な長さを保つように、 アークを安定距離に保つ、バネモデルに類似した力学モデル。

この手法を実装した結果として、私たちは以下の問題点を重視しました。

• 対話的といえるほど高速ではない。
• 配置結果が初期配置に大きく依存する。
• ノードとアークの交差（条件3参照）を高速に回避する手法が無い。

[改良１] すべてのノードを初期段階から配置するのではなく、 １個ずつインクリメンタルに配置するアルゴリズム。

このアルゴリズムによって、力学モデルの計算を 「いま追加したばかりのノード」の周辺だけに局所化することに成功し、 私たちの測定結果において従来手法よりも4〜5倍程度の高速な処理を実現しました。
また、多くの接続をもつ重要なノードを先に配置し、 その周辺部に残りのノードを後から配置するように配置順を決定して、 配置結果のクオリティの改善を実現しました。

下の実行例からもわかる通り、 本手法は従来手法よりも読みやすい配置結果を実現し、 しかも処理時間の低減にも成功しています。

従来手法による配置結果。	本手法による配置結果。	処理時間の比較。

[改良２] アークの曲線化によって、 ノードとアークの重なりを避けるアルゴリズム。

本手法では、まず最低１個のノードが非常に近い距離にあるアークを検出し、 これを細かい線分列に分割します。 続いて、線分列の端点に対して、以下の３種類の力学モデルを仮想します。

• 近隣ノードからの距離を一定以上に保つための分子間力モデル。
• 線分列が描くカーブの曲率半径を一定に保つためのバネモデル。
• 線分列の長さを一定に保つためのバネモデル。

以下に、本手法によってアークを曲線化（折れ線化） した実行結果の例を示します。 ノードとアークの重なりを回避することに成功しているのがわかります。

アーク曲線化前。	アーク曲線化後。

また私たちは、上記の改良手法を階層型グラフにも適用しました。 私たちの実装では最初に、階層型グラフの最上位階層を構成するグラフを配置します。 続いて以下の手順によって、配置処理を上位階層から下位階層に向けて反復します。

1. 上位階層のノードに属する下位階層のグラフを配置します。
2. 配置された下位階層の占有面積を、上位階層のノードに伝達します。
3. 占有面積を伝達された上位階層ノードとその周辺を、局所的に再配置します。

本手法を用いたウェブサイトの表示例を以下に示します。 ウェブページをノード、ウェブページ間のリンクをアーク、 とする階層型グラフを構築し、 それを本手法によって画面配置して表示した例を以下に示します。 ただし上記の [改良２] は、まだ階層型グラフには適用されていません。