力指向グラフ描画

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

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

力指向グラフ描画アルゴリズムは、グラフ描画のエッジのセットとノードのセットの間に力を割り当てます。通常、フックの法則に基づくバネのような引力を使用してグラフのエッジのエンドポイントのペアを互いに引き寄せ、同時にクーロンの法則に基づく帯電粒子のような反発力を使用してすべてのノードのペアを分離します。この力のシステムの平衡状態では、エッジは均一な長さになる傾向があり (バネ力のため)、エッジで接続されていないノードはより離れて描画される傾向があります (電気反発のため)。エッジの引力と頂点の反発力は、バネと粒子の物理的動作に基づかない関数を使用して定義される場合があります。たとえば、一部の力指向システムでは、引力が線形ではなく対数であるバネを使用します。

代替モデルでは、各バネの理想的な長さがノードiとj間のグラフ理論の距離に比例し、別個の反発力を使用しない、すべてのノード ペアに対してバネのような力を考慮します。ノード間のユークリッド距離と理想的な距離の差 (通常は差の 2 乗) を最小化することは、メトリック多次元尺度問題と同等になります。 ${\displaystyle (i,j)}$${\displaystyle \delta_{ij}}$

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

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

理想的な長さがグラフ理論の距離に比例するバネから定義された力の場合、応力の主要化は、これらの差を最小限に抑え、グラフの適切なレイアウトを見つけるための非常に良好な（すなわち、単調収束する）^[5]かつ数学的にエレガントな方法を提供します。

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

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

高品質の結果

少なくとも中規模サイズのグラフ (頂点数 50 ～ 500 個まで) の場合、エッジの長さが均一であること、頂点の分布が均一であること、対称性があることなどの基準に基づいて、得られる結果の品質は通常非常に良好です。この最後の基準は最も重要な基準の 1 つであり、他の種類のアルゴリズムでは実現が困難です。

柔軟性

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

直感的

これらのアルゴリズムはバネのような一般的な物体の物理的な類似性に基づいているため、アルゴリズムの動作は比較的簡単に予測および理解できます。これは他の種類のグラフ描画アルゴリズムには当てはまりません。

シンプルさ

一般的な力指向アルゴリズムはシンプルで、数行のコードで実装できます。直交レイアウトなどの他のクラスのグラフ描画アルゴリズムは、通常、はるかに複雑です。

インタラクティブ性

このクラスのアルゴリズムのもう 1 つの利点は、インタラクティブな側面です。グラフの中間段階を描画することで、ユーザーはグラフがどのように進化するかを追跡し、グラフが絡み合った状態から見栄えの良い構成に展開するのを見ることができます。一部のインタラクティブ グラフ描画ツールでは、ユーザーは 1 つ以上のノードを平衡状態から引き出し、元の位置に戻るのを見ることができます。このため、動的およびオンライングラフ描画システムでは、これらのツールが好まれます。

強固な理論的基礎

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

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

長い実行時間

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

悪い局所最小値

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

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

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

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

• di Battista, Giuseppe、Peter Eades、Roberto Tamassia、Ioannis G. Tollis (1999)、『グラフ描画：グラフの視覚化アルゴリズム』、Prentice Hall、ISBN 978-0-13-301615-4
• カウフマン、マイケル、ワグナー、ドロテア、編 (2001)、「グラフの描画: 方法とモデル」、Lecture Notes in Computer Science 2025、vol. 2025、Springer、doi :10.1007/3-540-44969-8、ISBN 978-3-540-42062-0、S2CID  1808286

• Stephen G. Kobourov 著「Force-Directed Drawing Algorithm」の章