Java および Scala のクラスの依存関係のグラフについて調べている。
今回はクラスタリング係数を見てみる。
クラスタリング係数とは、あるノードにリンクしたノード群が互いにリンクしている割合を表します。C で表します。ノードごとに値を持ち [0, 1] の範囲を取ります。あるノードで C=0 であれば、そのノードにリンクしているノード同士は互いにリンクしていなく、C=1 であれば、そのノードにリンクしているノード同士はすべてリンクしています。
現実のグラフは全体としては非常に疎であるが、知り合いが共通しているような部分的に密となるようなクラスタを作っていることが知られています。Twitter とかで、○○クラスタに属している人と言いますが、あのクラスタです。このとき、クラスタリング係数は値を持つことになります。
Apache Spark が依存する 214 個の JAR パッケージに含まれるクラスの依存関係のグラフを対象とします。
クラスタリング係数の分布は以下の
平均値は C = 0.53 C = 0.46 でした。クラスの依存関係グラフはクラスタリング性を持っていると言えるでしょう。*1
次数とクラスタリング係数の関係の散布図を描いてみました。
入力次数とクラスタリング係数の関係です。k_in は入力次数です。
出力次数とクラスタリング係数の関係です。k_out は出力次数です。
入力次数の方はっきりと、k^-1 に比例するように分布しています。出力次数の方もそういう傾向が見えないこともないですが、あまり出力次数とクラスタリング係数に強い関係はなさそうです。
この結果の何が興味深いのかというと、ネットワークの模型のひとつである Hierarchical Network モデルでは C(k) ∝ k^-1 の関係が成り立ちということが知られています(Hierarchical Network モデルについてはいつかまとめる）。ソフトウェアモジュールの成り立ちを考えると、ソフトウェアモジュールの依存関係は Hierarchical Network モデルでうまく説明できそうだと予想できます。入力次数とクラスタリング係数の関係が Hierarchical Network モデルと一致しているという事実は、この仮説を支えていると言えるでしょう。
