非連結なグラフのクラスタリング

Newman法によるクラスタリングでは、グラフが連結していることを仮定しているようだ。非連結の場合にはすべてのクラスタがひとつにまとまる前にノード対がなくなってしまうから。では、非連結なグラフにはどのように対応すればいいのか？あらかじめ、島ごとに分離し、そのなかの一番大きなもののみを解析対象とするのもいいかもしれないけれども、ちょっと面倒。

そこでアイデア。あらかじめ与えられたグラフに仮想的なノードをひとつだけ追加して、元々のグラフの全ノードにエッジを張り、ΔQ = -∞ を与えておく。すると、ΔQ が小さいためクラスタリングの最中にこのエッジが選択されることはなく、クラスタリングの順序にも（多分）影響を与えず、非連結なグラフの場合には、ここで追加したエッジだけが最終段階に残り、いいかげんな順序でクラスタリングが進みます。最終的にはひとつのデンドログラムが得られるでしょう。

ご意見、歓迎します。