javascript - 強制指向グラフレイアウトのパフォーマンスと複雑さ?

Question

数千のノードとエッジのグラフがあり、強制指向の JavaScript レイアウト アルゴリズム (cose と cola) を使用した Cytoscape.js のパフォーマンスが不足していることに気付きました。

他のライブラリやアルゴリズムを探すために時間を費やすべきなのか、それともそれらのアルゴリズムの複雑さが一般的に高すぎるのか疑問に思います。単純なアルゴリズムでは、すべてのノードを他のすべてのノードと比較する必要があるため、二次的な複雑さが必要になると思いますが、接続性の低いデータを巧妙にフィルタリングすることで、適切な近似を想像することができました (数学的に完全な結果は必要ありません) 、ユーザーにとって直感的なものです）。

私の目標は、典型的なユーザー マシンで 10 秒以内にグラフをレイアウトすることです。

私が見つけた出版物（「強制指向の複雑さ」のためのGoogle Scholar）：

• 無向グラフの高速適応レイアウト アルゴリズム (1995 年)は、 O(|V|^3) を推定します。
• The Galois Complexity of Graph Drawing: Why Numerical Solutions Are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawingsは、正確に計算するのは難しいと言います (?、私はグラフ理論家ではありません)。
• 大きなグラフの強制指向レイアウトへの多次元アプローチは、 「サブ二次時間と空間で 2 次元、3 次元、およびそれ以上の次元で描画を生成する」ため、その JavaScript 実装を見つけようとします。

Answer 1

隣接するノード間の引力とすべてのノード間の反発力を使用するレイアウト アルゴリズムの場合、遠く離れたノードから生じる反発力に対してBarnes-Hutスタイルの近似を使用できます。B--H は一般的な学校の課題であり、多くのチュートリアル資料があるはずなので、ここでは簡単なスケッチのみを示します。基本的な考え方は、各ステップで、入力ノードの再帰的な四分木分解を実行し、各サブディビジョンのノード数をカウントすることです。次に、特定のノードにかかる力を概算するために、ツリーを再帰的にトラバースします。そのノードから遠く離れたサブディビジョンに到達した場合、あたかもサブディビジョン内のすべてのノードが中心にあるかのように斥力を計算します (または、うまくいくと思われるものは何でも平均を事前計算します)。