python - Graphviz: 2 つの新しいリンクされたノードを挿入し、エッジの交差を最小限に抑える方法は?

Question

次のグラフがあります。

ご覧のとおり、2 つの自然クラスターがあります。これらのクラスターを 2 つのグラフに分ける方法を見つけたいと思います。

もちろん、重要なステップは正しい分割を計算することです。2 つのノード n1 と n2 を挿入し、それらを e(n1, n2) にリンクして移動し、エッジ交差の数を最小限に抑えます (もちろん、すべてのノード/エッジを正確に固定します)。

誰でもここで助けを提供できますか? Graphviz には、それを可能にするものは何もないと思います。

Answer 1

ここでは、2 つの異なるタスクが混在していると思います。1 つはグラフの分析で、もう 1 つはグラフの視覚化です。

Graphviz は、名前が示すように、グラフを視覚化するためのツールです。視覚化には多くの形式がありますが、通常は、接続されているノードを互いに近づけて視覚的なエッジの長さを短くすることで、「見栄えを良くする」ことを試みます。ばねモデルまたは重力モデルを利用して、すべてのノードの最適な位置を計算できます。その他のオプションには、円形またはシェル レイアウトが含まれます。

特定のビジュアライゼーションは、グラフ分析の基礎とすべきではありません。平均最短経路長やクラスタリング係数などのグラフ プロパティは、視覚化とは無関係です。

「エッジ交差の数を最小限に抑えたい」と言います。エッジ交差の数は、グラフではなく、ビジュアライゼーションのプロパティです! グラフが変更されていなくても、graphviz にレイアウトを計算させるたびに変更される可能性があります。グラフを表現できるのは 2 次元だけだと誰が言いますか? 次元を 1 つだけ追加すると、エッジが交差しなくなります。

グラフ分析に集中することをお勧めします。あなたがNetworkXを知っているかどうかはわかりません。グラフを分析するための数十のアルゴリズムがあります。クラスタリングとクリークのセクションに興味があるかもしれませ ん。