ソフトウェア部品グラフの次数分布におけるべき乗則の調査

Presentation on theme: "ソフトウェア部品グラフの次数分布におけるべき乗則の調査"— Presentation transcript:

1 ソフトウェア部品グラフの次数分布におけるべき乗則の調査
○市井　誠，松下　誠 ，井上　克郎 大阪大学 大学院情報科学研究科 2006/7/19 FORCE 3rd Workshop

2 ソフトウェア部品グラフ ソフトウェア部品 (部品) ソフトウェア部品グラフ (部品グラフ) A B ソフトウェアの構成単位
クラス，関数，… 互いに利用関係が存在 変数宣言，呼び出し，… ソフトウェア部品グラフ (部品グラフ) ソフトウェア部品を頂点・利用関係を有向辺としたグラフ ソフトウェアの静的な構造を反映 class A { public void exec () { … } class B { … A.exec(); } A B 背景としてソフトウェア部品グラフについて。 まずソフトウェア部品とは，クラスや関数といったソフトウェアの構成単位のことを指す． 部品間には，変数宣言や，呼び出しなどの利用関係が存在する 例えばJavaのクラスを部品とすると，これらのクラスA,Bはそれぞれ部品になる． 　クラスAにはexec()というメソッドがあり，Bには，そのメソッドに対する呼び出しが存在する． 　このとき，BからAへの利用関係が存在する． ソフトウェア部品グラフは，ソフトウェア部品を頂点，利用関係を有効辺としたグラフのことを言う． 先ほどの部品と利用関係は，このような2頂点からなるグラフとして表される． 実際にはソフトウェア全体などでグラフを構成する． ソフトウェアの静的な構造を反映していて， ソフトウェア工学の様々な手法に用いられる． 本研究では，ソフトウェアをソフトウェア部品グラフとして表し， その特徴から，ソフトウェアの性質を得ることを目標とする． このソフトウェアは○○○だ！ ソフトウェア部品グラフ ソフトウェア 2006/7/19 FORCE 3rd Workshop

3 部品グラフとべき乗則 頂点の次数分布: グラフを特徴付ける重要な要素 部品グラフの次数分布に関する研究 これらの研究の特徴
JDKのクラス図を部品グラフを見なしたとき，次数がべき乗則に従う[12] C++のソフトウェアの部品グラフの次数がべき乗則に従う[8] これらの研究の特徴 対象は部分的な利用関係に基づく単体のソフトウェアの部品グラフのみ グラフとしての共通する性質を得ることに主眼があり， 個々のソフトウェアの性質との関連に関して議論されていない べき乗則 (べき分布): 値 x をもつ要素の出現頻度が，x のべき乗に比例する P[X=x] ~ x-a 本研究では，部品グラフの特徴として，頂点の次数分布に注目する． 頂点の次数分布は，一般的に，グラフを特徴付ける重要な要素と言われている． 部品グラフの次数分布における研究として， ・JDK ・C++ がある．べき乗則とは，…，興味深い性質． これは既存研究により示されている，部品グラフの全体像． 真ん中の辺り，ごく一部の部品が多くの利用関係をもつのに対して， 周辺には，ほとんど利用関係を持たない部品が多数存在することがわかる． こういう感じで研究されているが，これらの研究は， ・対象は部分的な利用関係にもとづき，単体のソフトウェアの部品グラフで，一般的な部品グラフではない ・これらの方々が統計を専門としているからだと思うが，グラフとしての～． (次ページつなぎ) 本研究では，この辺りをふまえて， [3] [12] S. Valverde, R. Ferrer-Cancho and R. V. Sole, "Scale-free Networks from Optimal Design", Europhysics Letters, 2002 [8] C. R. Myers, “Software systems as complex networks: Structure, function, and evolvability of software collaboration graphs”, Physical Review E 68, 046116 ,2003 2006/7/19 FORCE 3rd Workshop

4 研究の目的 べき乗則に注目した部品グラフの次数分布の調査
調査1: 詳細な利用関係に基づく部品グラフ・複数のソフトウェア集合に基づく部品グラフの次数は，べき乗則に従うか？ 多数のソフトウェアを収集・解析して部品グラフを構築し，調査 調査2: ソフトウェアの設計の特徴を，部品グラフの次数分布から読み取ることはできるか？ 異なる部品集合に基づく部品グラフの次数分布を比較 既存研究とは異なった視点で，べき乗則に注目した部品グラフの次数分布の調査． 注目するのは以下2点： ・ 2006/7/19 FORCE 3rd Workshop

5 発表の流れ 準備 調査1 調査2 考察 まとめ 部品グラフと部品集合 調査で示す内容 部品グラフの次数がべき乗則に従うか
ソフトウェア設計の特徴を部品グラフの次数分布から読み取れるか 考察 ソフトウェアの設計評価に関して まとめ 2006/7/19 FORCE 3rd Workshop

6 準備: 部品グラフと部品集合 対象：Javaソフトウェアに基づく部品グラフ 部品集合 部品（頂点）：Javaのクラス
継承,実装,変数宣言,生成,フィールド参照,メソッド呼び出し 既存研究では，継承や実装，変数宣言（フィールドのみ）など，部分的 部品集合 説明 クラス数 JDK Java 基本ライブラリ JDK1.4 約11,000 ECLIPSE Java統合開発環境 Eclipse 3.0.1 約14,000 NETBEANS Java統合開発環境 NetBeans 3.6 約13,000 APACHE Apache Projectから収集したソフトウェア集合 約59,000 ALL JDK, Eclipse, NetBeans, Apache Project, SourceForgeから収集したソフトウェア集合 約180,000 2006/7/19 FORCE 3rd Workshop

7 準備: 調査で示す内容 (1/2) 次数分布のプロット P[X=x] ~ x-a 入力次数と出力次数を個別に示す
両対数軸を用いた累積度数プロット べき乗則に従う場合，点が直線上にならぶ P[X=x] ~ x-a 傾き: -(a-1) 傾き: -a 調査結果として示す内容について説明します． まず，頂点の次数分布のプロットを示します． 部品グラフは有向グラフであり，入力と出力に分けることができますので，入力次数と出力次数を個別に示します． そしてプロットについてですが，べき乗則に従う場合， 普通にプロットしますとこのように特徴が捉えられない図になりますので，両対数軸を用います． すると点が直線上に並び，その傾きはべきの乗数であるaとなるのですが， すると値の大きな部分にばらつきが出てしまいます． そこで，上位からの累積度数を取ってプロットします． すると，上位のばらつきが吸収され，よりきれいに直線上に並びます． このときの傾きは-(a-1)となります． 値の大きい部分にばらつき 入力次数:2 出力次数:1 2006/7/19 FORCE 3rd Workshop

8 準備:調査で示す内容 (2/2) 回帰分析により得られる値 P[X=x] ~ x-a べき乗則のパラメータ a 寄与率 R*2
べき乗則に従う度合い P[X=x] ~ x-a 傾き: -(a-1) また，この状態から回帰直線を求めることにより，べき乗則のパラメータである a をもとめます． また，べき乗則に従う度合いとして，対象がどの程度回帰モデルに従っているか，を示す寄与率を求めます． 2006/7/19 FORCE 3rd Workshop

9 発表の流れ 準備 調査1 調査2 考察 まとめ 部品グラフと部品集合 調査で示す内容 部品グラフの次数がべき乗則に従うか
ソフトウェア設計の特徴を部品グラフの次数分布から読み取れるか 考察 ソフトウェアの設計評価に関して まとめ 2006/7/19 FORCE 3rd Workshop

10 調査1 詳細な利用関係に基づく部品グラフ・複数のソフトウェア集合に基づく部品グラフの次数分布は，べき乗則に従うか？ 入力次数・出力次数を調査
部品集合 JDK, ALL 次数と部品との関連を調査し，その要因を考察 上位の部品の傾向，次数とメトリクスとの相関 部品集合 ALL 2006/7/19 FORCE 3rd Workshop

11 調査1: 入力次数の分布 JDK ALL 最大値:116,326 最大値:6,461 a R*2 JDK ALL べき乗則に従う
・グラフ，表の見方 ・きれいに直線上にならんでいる ・寄与率も高い →べき乗則に従う． ・べきの乗数であるaの値は，他の分野で観測されることの多い 2 に近い値. 　例えばWWW上のページのリンク数もこの辺． ・最大値はJDKは約6400だが，対してALLは約11万 →部品数の違いを考慮しても，大きな差が出ている a R*2 JDK 2.1 ±8.6×10-3 0.99 ALL 2.0 ±1.4×10-3 1.00 べき乗則に従う 値域に大きな差が見られる 2006/7/19 FORCE 3rd Workshop

12 調査1: 出力次数の分布 JDK ALL 最大値:140 最大値:354 べき乗則には従わない 値域はそれほど変わらない a R*2 JDK
・図，表の見方． ・値の大きな範囲では入力と同様に直線だが， 　値の小さな範囲で曲線になっている →べき分布では無い <s>・参考程度に直線に回帰してみると，かなり大きな傾き． 　極端な値が出にくい．</s> ・最大値はJDKが140でALLは350で，あまり大きな違いは無い べき乗則には従わない 値の小さな部分は曲線 値域はそれほど変わらない a R*2 JDK 3.1 ±8.2×10-2 0.88 ALL 3.7 ±6.9×10-2 0.90 2006/7/19 FORCE 3rd Workshop

13 調査1: 入力次数と部品との関連 ALLの入力次数上位の部品 メトリクスとの相関** 入力次数がべき乗則に従う要因 部品が持つ役割に関連
JDKなど，基礎的な役割をもつ部品 String,Objectは特に大きな値 メトリクスとの相関** 行数，複雑度*とは相関なし メソッド数とやや相関 クラス名 行数 出力次数 入力次数 1 java.lang.String 675 21 116,326 2 java.lang.Object 35 4 98,377 3 java.lang.Class 605 41 29,767 java.lang.Exception 15 21,057 5 java.lang.Throwable 136 12 19,536 出力次数 行数 複雑度* メソッド数 入力次数 0.00 0.07 0.08 0.24 入力次数がべき乗則に従う要因 部品が持つ役割に関連 一部の基礎的な部品は，様々な部分から利用される 多くの部品は，ソフトウェアの一部など局地的に利用されるのみ ・入力次数に関して，部品との関連をみていくことで， 　べき乗則に従う要因を調べる． ・表(上)の説明 ・JDKの部品が並んでいる． ・その中でも，文字列を表すクラスであるString，すべてのクラスの親クラスであるObjectは特に大きな値． ・表(下)の説明 　・入力次数と，出力次数，行数，複雑度，メソッド数と相関を求めた結果 　・部品そのものから得られるメトリクス ・メソッド数とやや相関が見られる程度で，他とは相関が見られない →入力次数は部品の役割に関連するため 　・基礎的な部品は様々な所から利用され，きわめて大きな値 　・特殊な役割の部品は，ソフトウェアの一部など局地的に利用されるのみで，小さい値しか持たない ** スピアマンの順位相関係数 2006/7/19 FORCE 3rd Workshop *WMC: サイクロマチック数を重みとした，重み付きメソッド和

14 調査1: 出力次数と部品との関連 ALLの出力次数上位の部品 メトリクスとの相関 出力次数がべき乗則に従わない要因 部品の規模や複雑さに関連
単純に大きな部品 メトリクスとの相関 行数や複雑度・メソッド数と高い相関 クラス名 行数 出力次数 入力次数 1 org.apache.poi… …FunctionEval 364 354 2 org.jgraph.GPGraphpad 2,196 255 130 3 com.jgraph.GPGraphpad 2,200 253 131 4 542 252 209 5 org.eclipse.jdt… …ASTConverter 4,520 223 入力次数 行数 複雑度 メソッド数 出力次数 0.00 0.83 0.75 0.64 出力次数がべき乗則に従わない要因 部品の規模や複雑さに関連 極端に大きな部品は非現実的 ・出力次数に関して，部品との関連をみていくことで， 　べき乗則に従わなかった要因を調べる． ・表(上)の説明 ・単純に規模の大きな部品が並んでいる ・表(下)の説明 　・出力次数と，入力次数，行数，複雑度，メソッド数と相関を取った結果 　・．．． →出力次数は，他の部品の存在にあまり影響されず， 　部品の規模や複雑さと関係するため 　・部品に記述された内容に基づいている 　・極端に大きな部品＝規模が大きく複雑な部品は非現実的で，あまり存在せず， 　　存在してもたかだか200～300程度ということ． 2006/7/19 FORCE 3rd Workshop

15 調査1: まとめ 入力次数 出力次数 べき乗則に従う 部品の役割に関連し，基礎的な役割の部品が大きな次数をもつ べき乗則には従わない
高い度合い 部品集合によって値域に大きな差 部品の役割に関連し，基礎的な役割の部品が大きな次数をもつ 出力次数 べき乗則には従わない 値の小さな部分が異なる 部品集合によって値域はあまり変わらない 部品の規模や複雑さと関連し，極端に大きな部品はあまり存在しない ・入力次数 　・高い度合いでべき乗則に従い，部品集合により値域に大きな差 　・これは，部品の役割に関連し，基礎的な部品は大きな次数をもつため． ・出力次数 　・べき乗則に従わず，部品集合がかわっても値域はあまり変わらない 　・これは，出力次数が部品そのものの規模や複雑さに関係し，極端に大きな部品は存在しないため， 2006/7/19 FORCE 3rd Workshop

16 発表の流れ 準備 調査1 調査2 考察 まとめ 部品グラフと部品集合 調査で示す内容 部品グラフの次数がべき乗則に従うか
ソフトウェア設計の特徴を部品グラフの次数分布から読み取れるか 考察 ソフトウェアの設計評価に関して まとめ 2006/7/19 FORCE 3rd Workshop

17 調査2 ソフトウェアの設計の特徴を，部品グラフの次数分布から読み取ることはできるか？ 異なる部品集合の次数分布を比較
2-1: ソフトウェア単体と ソフトウェア集合 部品集合 ECLIPSE, NETBEANS と ALL, APACHE 入力次数の分布を比較 2-2: 類似したソフトウェア同士 部品集合ECLIPSEとNETBEANS 入力次数，出力次数の分布を比較 2006/7/19 FORCE 3rd Workshop

18 実験2-1: 入力次数分布 a R*2 ECLIPSE NETBEANS APACHE ALL
2.2 ±1.6×10-2 0.96 NETBEANS 2.2 ±7.9×10-3 0.99 APACHE 2.4 ±1.1×10-2 0.98 ALL 2.0 ±1.4×10-3 1.00 ECLIPSE APACHE NETBEANS ALL ・図の説明 ・Eclipseはべき乗則に従う度合いがやや低く，また，値の大きな部分で傾きに変化が見られる ・NetBeansはべき乗則に従う度合いは高いが，Eclipse同様，値の大きな部分で傾きに変化が見られる ・Apache, Allは，ともにべき乗則に従う度合いが高く，また傾きの変化は見られない ソフトウェア単体は，値の大きな部分で傾きが変化 ソフトウェア集合は，べき乗則に従う度合いが高い 2006/7/19 FORCE 3rd Workshop

19 調査2-1: まとめ 見られた傾向 要因の考察 ソフトウェア単体は，値の大きな部分で傾きに変化が見られる
ソフトウェア集合は，より高い度合いでべき乗則に従う ソフトウェア単体は，利用関係が一部の部品に集中する度合いが低い 要因の考察 ソフトウェア単体では，一部の部品に利用関係が集中しないような構造となっている レイヤー構造など ソフトウェア集合では，ソフトウェア間で共通して利用される部品に利用関係が集中 JDKやXML関連の部品などに限定 それぞれのソフトウェアでのみ利用される部品の入力次数は相対的に低い 2006/7/19 FORCE 3rd Workshop

20 調査2-2: 対象説明 ECLIPSEとNETBEANS の比較をおこなう 比較内容 どちらも Java の統合開発環境 ほぼ同規模
入力次数と出力次数の分布 次に，調査2について まず比較対象について 　D3:Eclipse と D4: NetBeansの比較をおこなう 　これらはどちらも Javaの統合開発環境であり，Javaソースコードの編集およびビルド・デバッグ機能，また構成管理機能をもつ． 　また，D3は14000クラス/120万行, D4は13000クラスで100万行と，ほぼ同規模であるといえる． これらについて，入力辺数および出力辺数の分布を比較する --- Eclipse 3.0 NetBeans 3.5 ダウンロードしてきたアーカイブに含まれるクラス群が対象. 2006/7/19 FORCE 3rd Workshop

21 調査2-2: 入力次数 ECLIPSE NETBEANS ECLIPSEには極端な傾きの変化（カットオフ）がみられる 最大値にも大きな差
最大値:1,497 最大値:1,921 ECLIPSEには極端な傾きの変化（カットオフ）がみられる NETBEANSにも見られるが，やや小さい 最大値にも大きな差 ECLIPSEの方が，利用関係が集中する度合いが低い まず入力辺数の比較 図はどちらも入力辺数の分布を，対数軸かつ累積度数で示したもので， 左側がD3, 右側がD4となっている． どちらも大体直線になるが，D3の方については，約500付近で カットオフとよばれる傾きの変化が極端に見られる． また，最大値をみてみると，D3は最大値1500付近なのに対し，D4では1900以上となっている． これらのことから，D3については，上位でも比較的入力辺数が小さい， すなわち利用関係の集中度が低い，と言える． --- D3: a=2.20 ± 0.02 D4: a=1.99 ± 0.01 ただし平均だと D3: 10.09 D4: 5.14 で逆転. ただし，今の話は上位あたりなので特に問題は無い. (D3は途中まで傾きがやや小さいので，その辺りが効いている) というかD4は単純に辺数が多い． 2006/7/19 FORCE 3rd Workshop

22 調査2-2: 出力次数 分布の形状はほぼ同じ 最大値に大きな差 ECLIPSEの方が，単位行あたりの利用部品数が多い ECLIPSE
NETBEANS 最大値:102 最大値:192 分布の形状はほぼ同じ 最大値に大きな差 ECLIPSEの方が，単位行あたりの利用部品数が多い 続いて出力辺数を，同様に対数軸かつ累積度数で示す． 先ほどとことなり，分布の形状自体には差がみられない しかし，最大値をみてみると　D3が200近いのに対してD4では100程度と，大きな差がみられる． このことから，D3は全体的に1部品辺りの利用部品数が多いと言える． D3とD4は同程度の総行数であることも考慮すると，D3は単位行あたりの利用部品数が多い，と言える． --- 意味があるかどうか別として，平均だと D2: 10.09 D3: 5.14 こちらも2倍程度の差． (* というか当然入力と同じになる) 2006/7/19 FORCE 3rd Workshop

23 調査2-2: まとめ 見られた傾向 要因の考察 ECLIPSEはNETBEANSよりも，
利用関係が集中する度合いが低い 単位行あたりの利用部品数が多い 要因の考察 ECLIPSEで中心的に利用される部品は，それぞれの役割が細分化されている 保守性や柔軟性のため 次数分布にアーキテクチャの違いが反映 --- 役割を細分化すると，理解がやや困難，てことを口頭で． 2006/7/19 FORCE 3rd Workshop

24 発表の流れ 準備 調査1 調査2 考察 まとめ 部品グラフと部品集合 調査で示す内容 部品グラフの次数がべき乗則に従うか
ソフトウェア設計の特徴を部品グラフの次数分布から読み取れるか 考察 ソフトウェアの設計評価に関して まとめ 2006/7/19 FORCE 3rd Workshop

25 考察 次数分布をみることで，ソフトウェアの設計を評価出来るのでは無いだろうか？ 以下の様なソフトウェアは設計に問題がある
入力次数がべき乗則に従う度合いが高い カットオフがほとんど存在しない 利用関係が一部の部品に集中しすぎている 設計が不十分で，基礎的な部品が直接利用されている "God Class": 一部のクラスに機能が集中しすぎている 具体的にメトリクスとして定式化し，指標を定めることが必要 2006/7/19 FORCE 3rd Workshop

26 発表の流れ 準備 調査1 調査2 考察 まとめ 部品グラフと部品集合 調査で示す内容 部品グラフの次数がべき乗則に従うか
ソフトウェア設計の特徴を部品グラフの次数分布から読み取れるか 考察 ソフトウェアの設計評価に関して まとめ 2006/7/19 FORCE 3rd Workshop

27 まとめ べき乗則に注目した部品グラフの次数分布の調査 明らかになったこと ソフトウェアの設計の評価に関して考察 入力次数はべき乗則に従う
出力次数はべき乗則に従わない 値の小さい部分で異なる ソフトウェア設計の特徴が部品グラフの次数分布に現れる 利用関係の集中の度合い ソフトウェアのアーキテクチャ ソフトウェアの設計の評価に関して考察 今後，次数分布とソフトウェアの設計や品質とのより詳細な関連について調査する必要がある 2006/7/19 FORCE 3rd Workshop