力指向グラフ描画

力指向型グラフ描画アルゴリズムは、グラフを美しく描画するためのアルゴリズムの一種です。その目的は、グラフのノードを2次元または3次元空間に配置し、すべてのエッジの長さがほぼ等しくなり、交差するエッジが可能な限り少なくなるようにすることです。そのためには、エッジとノードの相対位置に基づいて、エッジとノードの集合間に力を割り当て、これらの力を使用してエッジとノードの動きをシミュレートするか、またはそれらのエネルギーを最小化します。^{[ 2 ]}

グラフ描画は難しい問題になり得るが、力指向アルゴリズムは物理シミュレーションであるため、通常は平面性などのグラフ理論に関する特別な知識を必要としない。

力指向型グラフ描画アルゴリズムは、グラフ描画のエッジ集合とノード集合の間に力を割り当てます。通常、フックの法則に基づくバネのような引力を用いて、グラフのエッジの端点のペア同士を引き付け、同時にクーロンの法則に基づく帯電粒子のような反発力を用いて、すべてのノードのペアを分離します。この力系の平衡状態では、エッジは（バネの力によって）均一な長さになり、エッジで接続されていないノードは（電気的な反発力によって）より遠くに引き離される傾向があります。エッジの引力と頂点の反発力は、バネや粒子の物理的な挙動に基づかない関数を用いて定義することもできます。例えば、力指向型システムの中には、引力が線形ではなく対数的なバネを用いるものもあります。

別のモデルでは、節点のペアごとにバネのような力を考慮する。${\displaystyle (i,j)}$理想的な長さ$\displaystyle \delta _{ij}}$各バネの力は、別途反発力を用いることなく、ノードiとj間のグラフ理論上の距離に比例する。ノード間のユークリッド距離と理想距離の差（通常は二乗差）を最小化することは、多次元尺度構成法におけるメトリック問題と同等である。

力指向グラフでは、機械的なバネや電気的な反発力以外の力も考慮に入れることができます。重力に類似した力を用いて頂点を描画空間の固定点に引き寄せることができます。これは、反発力によって互いに離れてしまう可能性のある、連結されていないグラフの異なる連結成分をまとめたり、中心性の高いノードを描画の中心位置に描画したりするために使用できます。^{[ 3 ]}また、単一の成分内の頂点間隔にも影響を与える可能性があります。磁場に類似した力を有向グラフに用いることもできます。最終的な描画で重なりやほぼ重なりが生じないように、エッジだけでなくノードにも反発力を加えることができます。円弧やスプライン曲線などの曲線エッジを持つ描画では、例えば角度分解能を向上させるために、これらの曲線の制御点にも力を加えることができます。^{[ 4 ]}

グラフのノードとエッジにかかる力が定義されると、これらの力源の下でのグラフ全体の挙動を、あたかも物理システムであるかのようにシミュレーションすることができます。このようなシミュレーションでは、ノードに力が加えられ、ノード同士が引き寄せられたり、離れたりするようになります。この操作は、システムが機械的平衡状態に達するまで繰り返し行われます。つまり、ノードの相対位置が、繰り返しごとに変化しなくなるまで繰り返されます。この平衡状態におけるノードの位置を用いて、グラフの図が生成されます。

理想的な長さがグラフ理論的な距離に比例するバネから定義される力の場合、応力優位化は、これらの差を最小化し、したがってグラフの良いレイアウトを見つけるための非常に扱いやすい（つまり単調収束する）^{[ 5 ]数学的に洗練された方法を提供します。}

物理シミュレーションに代わる、あるいは物理シミュレーションと併用して、エネルギー最小値をより直接的に探索するメカニズムを用いることも可能である。このようなメカニズムは、一般的なグローバル最適化手法の例であり、シミュレーテッドアニーリングや遺伝的アルゴリズムなどが挙げられる。

力指向型アルゴリズムの最も重要な利点は以下のとおりです。

質の高い結果

少なくとも中規模グラフ（頂点数50～500個程度）の場合、得られる結果は通常、以下の基準に基づいて非常に良好な品質を示します。すなわち、辺の長さが均一であること、頂点の分布が均一であること、そして対称性を示すことです。この最後の基準は最も重要な基準の一つであり、他のアルゴリズムでは達成が困難です。

柔軟性

力指向アルゴリズムは、追加の美的基準を満たすように容易に適応および拡張できます。これにより、力指向アルゴリズムは最も汎用性の高いグラフ描画アルゴリズムのクラスとなります。既存の拡張の例としては、有向グラフ、3D グラフ描画、^{[ 6 ]}クラスタグラフ描画、制約付きグラフ描画、動的グラフ描画などがあります。

直感的

これらのアルゴリズムはバネなどの身近な物体の物理的な類似性に基づいているため、その挙動は比較的容易に予測・理解できる。これは他のタイプのグラフ描画アルゴリズムには当てはまらない。

シンプルさ

典型的な力指向型アルゴリズムは単純で、数行のコードで実装できる。直交配置のためのアルゴリズムなど、他の種類のグラフ描画アルゴリズムは、通常、はるかに複雑である。

インタラクティブ性

この種のアルゴリズムのもう一つの利点は、対話的な側面です。グラフの中間段階を描画することで、ユーザーはグラフがどのように進化していくかを追跡し、絡み合った状態から整った形状へと展開していく様子を見ることができます。一部の対話型グラフ描画ツールでは、ユーザーは1つまたは複数のノードを平衡状態から引き離し、それらが元の位置に戻る様子を観察できます。このため、動的かつオンラインのグラフ描画システムにおいて、これらのアルゴリズムは好ましい選択肢となります。

強固な理論的基盤

単純なアドホックな力指向アルゴリズムは、文献や実務でよく見られますが（比較的理解しやすいため）、より論理的なアプローチが注目を集め始めています。統計学者は1930 年代から多次元尺度構成法(MDS) で同様の問題を解決しており、物理学者も関連するn 体問題に取り組んできた長い歴史があるため、非常に成熟したアプローチが存在します。例として、メトリック MDS のストレス優位化アプローチは、上記のようにグラフ描画に適用できます。これは単調に収束することが証明されています。^{[ 5 ]}単調収束、つまりアルゴリズムが各反復でレイアウトのストレスまたはコストを減少させる特性は、レイアウトが最終的に局所的最小値に達して停止することを保証するため重要です。減衰スケジュールはアルゴリズムを停止させますが、真の局所的最小値に到達することを保証することはできません。

力指向型アルゴリズムの主な欠点は以下のとおりです。

長時間稼働

一般的な力指向アルゴリズムは、一般的に3乗時間で実行されると考えられています（${\displaystyle O(n^{3})}$）、 どこ${\displaystyle n}$は入力グラフのノード数です。これは、反復回数が線形であると推定されるためです（${\displaystyle O(n)}$）、そして各反復において、すべてのノードのペアを訪問し、それらの相互反発力を計算する必要があります。これは物理学のN体問題に関連しています。しかし、反発力は局所的な性質を持つため、グラフは隣接する頂点のみを考慮するように分割できます。大規模グラフのレイアウトを決定するアルゴリズムで使用される一般的な手法には、高次元埋め込み^{[ 7 ]} 、多層描画、およびN体シミュレーションに関連するその他の方法があります。たとえば、Barnes–Hutシミュレーションに基づく手法FADE ^{[ 8 ]}は、実行時間を線形または時間スケールに改善できます。${\displaystyle n\log(n)}$反復ごとに。大まかな目安として、標準的な設定では数秒で最大1,000個のノードを描画できると予想されます。${\displaystyle n^{2}}$反復手法ごとに、そして100,000で${\displaystyle n\log(n)}$反復手法ごとに。^{[ 8 ]}力指向アルゴリズムは、グラフクラスタリングアプローチと組み合わせると、数百万のノードのグラフを描画できます。^{[ 9 ]}

局所的最小値が低い

力指向アルゴリズムは、最小エネルギーのグラフ、特に総エネルギーが局所的最小値にすぎないグラフを生成することが容易にわかります。見つかった局所的最小値は、多くの場合、大域的最小値よりもかなり悪い場合があり、これは低品質の描画につながります。多くのアルゴリズム、特に頂点の下り坂移動のみを許容するアルゴリズムでは、最終結果は初期レイアウトに大きく影響される可能性があり、初期レイアウトはほとんどの場合ランダムに生成されます。局所的最小値が悪いという問題は、グラフの頂点の数が増えるにつれてより重要になります。この問題を解決するには、異なるアルゴリズムの組み合わせ適用が役立ちます。^{[ 10 ]}例えば、鎌田-河合アルゴリズム^{[ 11 ]}を使用して適切な初期レイアウトを迅速に生成し、次にフルヒターマン-レインゴールドアルゴリズム^{[ 12 ]}を使用して隣接ノードの配置を改善します。大域的最小値を達成するもう1つの手法は、マルチレベルアプローチを使用することです。^{[ 13 ]}

グラフ描画における力指向法は、 Tutte (1963)の研究に遡ります。Tutte は、平面グラフの埋め込みの外面の頂点を凸位置に固定し、各辺にバネのような引力を配置し、システムが平衡状態に落ち着くまで待つことで、多面体グラフをすべての面が凸になるように平面上に描画できることを示しました。 ^{[ 14 ]}この場合の力の性質が単純なため、システムは局所的最小値に陥ることはなく、むしろ一意のグローバル最適構成に収束します。この研究により、凸面を持つ平面グラフの埋め込みは、Tutte 埋め込みと呼ばれることがあります。

隣接する頂点間の引力とすべての頂点間の斥力の組み合わせは、Eades (1984)によって初めて使用されました。^{[ 15 ]}この種の力指向レイアウトに関する追加の先駆的な研究は、Fruchterman & Reingold (1991)によって行われました。^{[ 12 ]}すべての頂点のペア間にバネ力のみを使用し、理想的なバネの長さを頂点のグラフ理論的距離に等しくするというアイデアは、Kamada & Kawai (1989)によるものです。^{[ 11 ]}

• Cytoscapeは、生物学的ネットワークを可視化するためのソフトウェアです。基本パッケージには、組み込み機能の一つとして力指向型レイアウトが含まれています。
• Gephiは、あらゆる種類のネットワークや複雑系、動的グラフや階層型グラフのための、インタラクティブな可視化および探索プラットフォームです。
• Graphvizは、非常に大規模なグラフを処理できる、多段階の力指向型レイアウトアルゴリズム（その他多数）を実装したソフトウェアです。
• Tulipは、力指向型レイアウトアルゴリズム（GEM、LGL、GRIP、FM³）のほとんどを実装したソフトウェアです。
• プレヒューズ

• di Battista, Giuseppe; Peter Eades ; Roberto Tamassia ; Ioannis G. Tollis (1999), Graph Drawing: Algorithms for the Visualization of Graphs , Prentice Hall, ISBN 978-0-13-301615-4
• Kaufmann, Michael; Wagner, Dorothea編 (2001)、グラフ描画：方法とモデル、Lecture Notes in Computer Science 2025、vol.  2025、Springer、doi : 10.1007/3-540-44969-8、ISBN 978-3-540-42062-0S2CID 1808286​ 

• スティーブン・G・コボウロフ著「力指向型描画アルゴリズム」に関する書籍の一章