力指向のグラフレイアウトのパフォーマンスと複雑さ？

Question

私は数千のノードとエッジのグラフを持っており、力向きのJavaScriptレイアウトアルゴリズム（coseとcola）でCytoscape.jsのパフォーマンスが不足していることがわかりました。

他のライブラリやアルゴリズムを探す時間がかかるか、それらのアルゴリズムの複雑さが一般的に高すぎるかどうかは疑問です。素朴なアルゴリズムでは、すべてのノードを他のすべてのノードと比較する必要があるので、2次の複雑さが必要ですが、接続性の低いデータを賢明にフィルタリングすると、良い近似が想像できます（私は数学的に完全な結果は必要ありませんユーザーにとって直感的なもの）。

私の目標は、典型的なユーザーマシンで10秒未満でグラフをレイアウトすることです。私が見つけた

出版物（のためのGoogleニュース "力は複雑さを監督"）：

• A fast adaptive layout algorithm for undirected graphs (1995)見積りのO（| V |^3）
• The Galois Complexity of Graph Drawing: Why Numerical Solutions Are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawingsは、（それが正確に計算することは困難だと言う、私はしています？グラフ理論家ではない）
• A Multi-dimensional Approach to Force-Directed Layouts of Large Graphs "サブ二次の時間と空間で2次元、3次元、および高次元の図を生成する"ので、私はその1つのJavaScript実装を見つけようとします。

Answer 1

隣接するノード間の引力とすべてのノード間の反発力を使用するレイアウトアルゴリズムでは、遠方のノードに起因する反発力のためにBarnes--Hutスタイル近似を使用できます。 B - Hは一般的な学校の割り当てであり、その上にチュートリアルの資料がたくさんあるはずなので、ここでは簡単なスケッチだけです。基本的な考え方は、各ステップで、入力ノードの再帰的なクアッドツリー解剖を行い、各サブディビジョンのノードの数を数えることです。次に、特定のノードの力を近似するには、ツリーを再帰的にトラバースします。そのノードから離れた細分に到達した場合、細分のすべてのノードが中心にあるかのように反発力を計算します（または、動作していると思われるものを平均して事前計算します）。