単純な無向グラフで密度ベースでクラスタリングを行っている場合、ノードまたはエッジの重みをどのように知ることができますか。そして、ここでの時間の複雑さは何ですか!
ここから私を案内してもらえますか：
エッジ (u,v) の重み E ∈ は、ノード u と v の共通の隣接ノードの数です。u≠v の場合の M^2 は、ノード u と v の共通の隣接ノードの数を表します。行列の乗算は N^3 のオーダーです。ただし、 M(u,v) =1 である M^2 の要素のみが必要です。そのため、エッジの重みを見つける複雑さを O(N*E) に減らすことができます。
ノードの重みは、ノードに接続されているエッジの重みの合計です。すべてのノードの重みが計算され、最も重みの高いノードが決定されます。ノードの重みを見つける複雑さは N^2 です。クラスターとして最も重みの高いノードから始めて、それを大きくします。
あなたがそれを理解したら、私を導きます...