力学モデル (グラフ描画アルゴリズム)

力学モデル（りきがくモデル）によるグラフ描画（力指向アルゴリズム）は、グラフを美しく描画するためのアルゴリズムの一つである。このアルゴリズムは、グラフのノードを2次元空間や3次元空間に配置して、辺の長さをほぼ等しい長さにし、グラフの辺ができるだけ交差しないようにすることを目的にしている。

このアルゴリズムでは、グラフの頂点と辺に仮想的な力を割り当て、力学的エネルギーの低い安定状態を探すことで、この目的を達成している。もっとも直截的なモデルでは、それぞれの辺をフックの法則にしたがうばねとみなし、それぞれの頂点をクーロンの法則にしたがう電荷をもつ粒子とみなす。そして、その力学系の挙動をシミュレートし、弾性力や静電気力が粒子を近づけたり遠ざけたりするようすを計算する。粒子が安定な配置になり、位置が変化しなくなるまで、力の計算と粒子の移動を繰り返す。その時点で、グラフのレイアウトが完了し、描画される。この平衡状態は、すべての力が釣り合った状態に相当する。

長所

以下が重要な長所である。

質の良い結果が得られる。少なくとも頂点が50-100ぐらいまでの中程度の大きさなら、辺の長さが均一, 頂点の散らばり具合が均一、対称性があるという点について、たいていとても満足のいく結果となる。対称性はグラフの美しさの上でもっとも重要な点であり、他のアルゴリズムでは達成することが難しいものである。
柔軟性がある。このアルゴリズムは、追加の美学的基準に対応するように簡単に適用/拡張できる。実際に拡張された例としては、有向グラフへの対応、 3Dのグラフ描画、クラスタ化したグラフ描画、制約付きのグラフ描画、動的なグラフ描画などがある。
直感的である。バネ、といった身近なものの物理的なアナロジーに基づいているので、結果を予測したり、理解するのが簡単である。これは他のアルゴリズムにはない特徴である。
シンプルである。典型的なアルゴリズムはシンプルであり、ちょっとした行数のコードで実装できる。他の種類のアルゴリズムである、orthogonalアルゴリズムのような方法ではより複雑になる。
操作しやすい。力学的なアルゴリズムでは、操作しやすい特徴がある。グラフ描画の過程を、複雑に絡み合ったグラフがシンプルな配置に整理されていく様子を見ることで理解することができる。いくつかの対話的なグラフ描画ツールでは、ユーザがノードを引っ張ることができ、それが平衡状態にもどる様子を見ることができる。これらは、動的なグラフ描画システムや、オンラインアルゴリズムを用いる場合に有用である。
強い理論的な基盤がある。この項目で実装例として紹介しているような、シンプルだがアドホックなアルゴリズムは文章や実用においてよく現れていたが、それと同時に、より合理的なアプローチが注目されるようになった。統計学では1930年代から似たような問題をmultidimensional scaling (MDS) で解いていたし、物理学には多体問題に関連した研究については長い歴史を持っている。このことから、このような問題に対しては極めて成熟したアプローチをもっている。一例として、metric MDS に対する stress majorization法は、以上で説明したグラフ描画に応用できる。この方法で一様収束することが証明されている^[1]。一様収束は、配置が必ず最終的に極小に到達し、停止することを保証するので重要である。減衰による方法（以下の擬似コードでの実装例のような場合）は、アルゴリズムは停止するが、真の極小に到達したことを保証するものではない。

短所

しかし、以下のような短所もある。

時間がかかる。典型的なアルゴリズムでは、入力グラフのノード数 V に対して O(V³)程度の時間が必要だと考えられている。これは、必要な繰り返しの数が O(V) と見積もることができ、またそれぞれの繰り返しで、すべてのノードの組み合わせが巡回され、相互作用力を計算する必要があると考えられるからである。この問題は多体問題の難しさに関連している。しかし、相互作用力は近接作用なので、ただ隣の頂点のみが考慮されるようにグラフを分割することができる。大きいサイズのグラフのレイアウトのための一般的なテクニックには、high-dimensional embedding^[2]や multi-layer drawing など、多体問題で使われているものが使える。例えば、FADE法^[3]を用いたBarnes–Hut simulationでは、繰り返しあたりの計算量が O(V log V) まで高速化できる。大雑把に考えて、数秒で描画できるノード数は最大で1,000ノード(標準的な、繰り返しあたり V² になる方法)、 100,000ノード(高速化した、V log Vになる方法) と見積もられる^[3]。

極小値の問題。すぐに分かることだが、力学モデルによって計算される力学的エネルギーが小さくなる配置というのは、力学系のエネルギーの合計が極小になる配置であって、最小になる配置でない。つまり、得られた極小値は、理想的な最小値より大きな値になる場合があり、そのような場合では質の低い結果に陥ることがある。多くのアルゴリズム、特に、頂点がダウンヒル法によってしか動くことのできない場合では, 最終的な結果は、多くのケースではランダムに生成されている初期状態に依存することになる。悪い極小の問題は描画すべきグラフの頂点が増加するとともに、より重大になってくる。この問題を解決するには、いろいろなアルゴリズムを組み合わせて使うことが必要である。例えば、Kamada-Kawai アルゴリズム^[4]によって高速に合理的な初期配置を計算し、Fruchterman-Reingold アルゴリズム^[5]により隣接ノードの配置を改善することができる。

実装例（擬似コード）

それぞれのノードに対し、位置 (x, y) および速度(dx, dy), 質量を定義する。バネ定数を設定できる場合も多い。この例では、フックの法則とクーロンの法則を用いている。

  すべてのノードの速度を(0, 0)にする。
  ノードの位置を、(乱数, 乱数) にする。 ''// 2 つのノードがまったく同じ位置におかれないようにする。
  do {
      運動エネルギーの合計 := 0 ''// すべての粒子について、運動エネルギーの合計を計算する。
      for-each すべてのノード as ノード1 {
          力 := (0, 0) ''// この粒子について作用するすべての力の合成を計算する。
          ''
          for-each すべてのノード as ノード2 {
              力 := 力 + 定数 / 距離（ノード1, ノード2) ^ 2 '' // クーロン力
          }
          ''
          for-each このノードにつながっているノード as ノード2 {
              力 := 力 + バネ定数 * (距離 (ノード1, ノード2) - バネの自然長) '' // フックの法則による力
          }
          ''
          // 内部摩擦が無ければ粒子は停止しないので、振動の減衰を計算する。
          ノード１の速度 := (ノード1の速度 +　微小時間 * 力 / ノード1の質量) * 減衰定数
          ノード１の位置 := ノード1の位置 + 微小時間 * ノード1の速度
          運動エネルギーの合計 := 運動エネルギーの合計 + ノード1の質量 * ノード1の速度 ^ 2
      }
  } loop until 運動エネルギーの合計が十分小さい '' // シミュレーションの停止。

出典

^ de Leeuw, J. (1988)
^ Harel, D., Koren Y. (2002)
^ ^a ^b Quigley A., Eades P. (2001)
^ Kamada, T., Kawai, S. (1989)
^ Fruchterman, T. M. J., & Reingold, E. M. (1991)

参考文献

di Battista, Giuseppe; Peter Eades, Roberto Tamassia, Ioannis G. Tollis (1999), Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, ISBN 978-0133016154
Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), “Graph Drawing by Force-Directed Placement”, Software – Practice & Experience (Wiley) 21 (11): 1129–1164, doi:10.1002/spe.4380211102
Harel, David; Koren, Yehuda (2002). "Graph Drawing by High-Dimensional Embedding". Proceedings of the 9th International Symposium on Graph Drawing. pp. 207–219. ISBN 3-540-00158-1。
Kamada, Tomihisa; Kawai, Satoru (1989), “An algorithm for drawing general undirected graphs”, Information Processing Letters (Elsevier) 31 (1): 7–15, doi:10.1016/0020-0190(89)90102-6
Kaufmann, Michael; Wagner, Dorothea, eds. (2001), Drawing graphs: methods and models, Lecture Notes in Computer Science 2025, Springer, doi:10.1007/3-540-44969-8, ISBN 978-3540420620
de Leeuw, Jan (1988), “Convergence of the majorization method for multidimensional scaling”, Journal of Classification (Springer) 5 (2): 163–180, doi:10.1007/BF01897162
Quigley, Aaron; Eades, Peter (2001). "FADE: Graph Drawing, Clustering, and Visual Abstraction" (PDF). Proceedings of the 8th International Symposium on Graph Drawing. pp. 197–210. ISBN 3-540-41554-8。

外部リンク

[1] Leeuw, J. (1988)

[2] Harel, D., Koren Y. (2002)

[quigley+eades-3] Quigley A., Eades P. (2001)

[4] Kamada, T., Kawai, S. (1989)

[5] Fruchterman, T. M. J., & Reingold, E. M. (1991)

[1]

[2]

[3]

[4]

[5]

長所

短所

実装例（擬似コード）

出典

参考文献

関連項目

外部リンク