グラフをk個の類似した部分グラフに分割する

Question

グラフが接続されており、エッジに重みがあります。エッジ間の重みが小さくなると、隣接する頂点がより近くなります。私はグラフをk個の小さな部分グラフに分割して、すべての部分グラフのノードが非常に似ているようにしたい。

つまり、グラフをクラスタリングする必要があります。誰かがグラフに適したクラスタリングアルゴリズムを提案し、時間の複雑さが少ない（O（n^2）より小さい）ことはできますか？

Answer 1

クラスタリングは一般的に解決できる難しい問題です。exacltyブルートフォースのみです。したがって、効率的なアルゴリズムの場合、ヒューリスティックなアプローチに依存する必要があります。頂点クラスタリングタスクとして問題を解決できる場合は、k-meansのようなものを試すことができますが、大きなデータセットでは遅くなる可能性があります。

具体的には、MCLアルゴリズムを使用することをお勧めします。 MCLは多くの場合効率的と思われます。無作為化されたフローシミュレーションを使用して、加重/非加重グラフのクラスタを検出します。クラスタ間のリンクはより小さくなる傾向がありますが、となる傾向があるという基本的な考え方は、クラスタ内でフローが集まることです。