私は有向グラフを持っています（実際にはハイパーグラフですが、今のところそれを無視してもかまいません）。
このグラフからさまざまなサブグラフを選択し、そのようなさまざまなサブセットを「クラスター品質」でランク付けする関数を探しています。
サブセットのメンバー間に多数のリンクが存在する場合、「クラスター品質」は高くなければなりません
サブセットの多くのメンバーからサブセットへ、またはサブセットの外部から多くのリンクが存在する場合、「クラスター品質」は低くなければなりません。
私の質問は：
「クラスター品質」の正しい用語は何ですか。
このコンテキストに存在する関連するアルゴリズム/関数は何ですか？
JVMにはどのような実装がありますか。Scalaが望ましいですが、Javaから呼び出し可能なものなら何でも構いませんか？
背景：アイデアは、ソースコード（クラスとメソッドの名前またはその一部）から単語を抽出し、「優れたクラスター」によって使用される単語を見つけることでアプリケーションを最もよく表す単語を見つけ、コード内の知識の概念を表す可能性があることです。
クラスター分析に関連するアルゴリズム/関数に関しては、いくつかあります。グラフのクラスタリングは、最近活発な研究分野であるグラフ パーティショニングと密接に関連しています。特に、Facebook や Twitter などのオンライン ソーシャル ネットワークの出現により、その基盤となる構造は (ソーシャル) グラフによって自然に表されます。
そうは言っても、私の経験では、クラスタリングの 2 つの尺度が思い浮かびます。1 つはモジュール性です。これは基本的に、サブグラフ (クラスター) を、エッジがランダムに分散されている場合にサブグラフがどのように見えるかを比較します。
もう 1 つはコンダクタンスです。これは、クラスター候補のランダム ウォークが一定の分布に収束する速さを測定します。
もう 1 つのより緩やかな尺度は、グラフ内の三角形 (3 サイクル) の数と存在する可能性のある三角形の数を測定するクラスタリング係数です。
全体として、このトピックに関連するアルゴリズム (および学術論文) は数多くありますが、上記の 3 つはより一般的な使用例です。
JVM での実装に関しては、そのようなアルゴリズムがその一部として付属していることを認識しているライブラリはありませんが、Scala で人気のあるグラフ ライブラリは、Graph for Scala (将来的に Scala Extended Core Library に組み込まれる予定) です。ツイッターで公開されたカソバリー。