読者です 読者をやめる 読者になる 読者になる

クラスの依存関係グラフ 4

手慰み 計算機 ノート

Java および Scala のクラスの依存関係のグラフについて調べている。

今回はクラスタリング係数を見てみる。

クラスタリング係数とは、あるノードにリンクしたノード群が互いにリンクしている割合を表します。C で表します。ノードごとに値を持ち [0, 1] の範囲を取ります。あるノードで C=0 であれば、そのノードにリンクしているノード同士は互いにリンクしていなく、C=1 であれば、そのノードにリンクしているノード同士はすべてリンクしています。

f:id:fjkz:20161127005456p:plain

現実のグラフは全体としては非常に疎であるが、知り合いが共通しているような部分的に密となるようなクラスタを作っていることが知られています。Twitter とかで、○○クラスタに属している人と言いますが、あのクラスタです。このとき、クラスタリング係数は値を持つことになります。

Apache Spark が依存する 214 個の JAR パッケージに含まれるクラスの依存関係のグラフを対象とします。

クラスタリング係数の分布は以下の

平均値は C = 0.53 C = 0.46 でした。クラスの依存関係グラフはクラスタリング性を持っていると言えるでしょう。*1

次数とクラスタリング係数の関係の散布図を描いてみました。

入力次数とクラスタリング係数の関係です。k_in は入力次数です。

f:id:fjkz:20161127030859p:plain

出力次数とクラスタリング係数の関係です。k_out は出力次数です。

f:id:fjkz:20161127030905p:plain

入力次数の方はっきりと、k^-1 に比例するように分布しています。出力次数の方もそういう傾向が見えないこともないですが、あまり出力次数とクラスタリング係数に強い関係はなさそうです。

この結果の何が興味深いのかというと、ネットワークの模型のひとつである Hierarchical Network モデルでは C(k) ∝ k^-1 の関係が成り立ちということが知られています(Hierarchical Network モデルについてはいつかまとめる)。ソフトウェアモジュールの成り立ちを考えると、ソフトウェアモジュールの依存関係は Hierarchical Network モデルでうまく説明できそうだと予想できます。入力次数とクラスタリング係数の関係が Hierarchical Network モデルと一致しているという事実は、この仮説を支えていると言えるでしょう。

*1:graph_tool で計算したが、なんか結果が胡散臭い。別の小さな系について、gephi で計算したものと、graph_tool で計算したもので違う値となった。傾向は同じなので、議論には差し支えないと思う。gephi だと遅すぎて今回のようなエッヂが100万を超えるようなのものの計算ができない……どうしたものか。速くて、Python で使えて、安定しているツールはないのだろうか。

→ igraph で計算しなおした。C = 0.46 は igraph の値。igraph も nan になる結果が混じってたり、ちょっと怪しいけれど