復(fù)雜網(wǎng)絡(luò)與軟件度量分析

馬 健 ，樊建平 ，劉 峰

(1.北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044;2.中國科學(xué)院 深圳先進(jìn)技術(shù)研究院，廣東 深圳 518055)

?

復(fù)雜網(wǎng)絡(luò)與軟件度量分析

馬 健1，樊建平2，劉 峰1

(1.北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044;2.中國科學(xué)院 深圳先進(jìn)技術(shù)研究院，廣東 深圳 518055)

用復(fù)雜網(wǎng)絡(luò)理論研究軟件系統(tǒng)的復(fù)雜性，選取兩款面向?qū)ο箝_源軟件框架webwork和spring作為研究對象，無(有)向圖節(jié)點代表類，邊代表類間的依賴和關(guān)聯(lián)等關(guān)系，將系統(tǒng)抽象為網(wǎng)絡(luò)圖，并對其拓?fù)浣Y(jié)構(gòu)進(jìn)行分析.研究表明:無(有)網(wǎng)絡(luò)具有較大的聚類系數(shù)和較小的平均路徑長度，具有小世界特性.由于框架都使用了依賴注入和控制反轉(zhuǎn)，程序中類之間的關(guān)系，完全由spring容器來控制，而不是由代碼控制，容器運行時會根據(jù)spring提供的配置信息注入到組件中.用依賴注入的一個結(jié)果是改變了編譯階段部分類之間的相互關(guān)系,由原來的關(guān)聯(lián)實體類到關(guān)聯(lián)加載配置文件類 ,從而影響節(jié)點的度包括入度和出度，使無(有)向圖的邊(弧)數(shù)改變.實驗結(jié)果表明：度分布統(tǒng)計特性仍然具有無標(biāo)度特性.

軟件度量；復(fù)雜網(wǎng)絡(luò)；度分布；聚類系數(shù)

從20世紀(jì)70年代至今，軟件系統(tǒng)已經(jīng)變得極其復(fù)雜,“軟件作坊”式的開發(fā)方式導(dǎo)致了軟件危機的出現(xiàn).1968年，NATO(北約)的科技委員會上第1次提出了軟件工程(Software Engineering)這個概念.軟件工程包括兩方面的內(nèi)容：軟件開發(fā)技術(shù)和軟件項目管理.要想有效管理，就難以繞開度量的問題[1-3].其中，軟件度量是軟件項目管理的一個關(guān)鍵環(huán)節(jié)，軟件復(fù)雜性度量一直是軟件工程的重要研究領(lǐng)域.軟件復(fù)雜性是指理解和處理軟件的難易程度，包括程序復(fù)雜性和文檔復(fù)雜性，主要體現(xiàn)在程序復(fù)雜性中.復(fù)雜性度量方法有：代碼行度量法(Loc)[4]，Mccabe圈復(fù)雜性度量法[5]，Halstead提出的程序體積度量[2].結(jié)構(gòu)化程序軟件復(fù)雜性的度量，出現(xiàn)了新的度量方法：Henry和Kafura提出的信息流度量[6]，Kavitha 和Shanmugam 提出的動態(tài)耦合測量[7]，Collofello提出的穩(wěn)定度量[8].1990年以后，面向?qū)ο蠓椒?Object-Oriented)逐漸成為軟件設(shè)計和開發(fā)的主流，常用的度量方法包括：Chidamber和Kemerer提出了一系列面向?qū)ο蠖攘糠椒ㄒ卜QC&K度量方法的面向?qū)ο蠖攘縖9]，Brito和Abreu提出了MOOD度量方法包含6個度量指標(biāo),是對面向?qū)ο蟮姆庋b性、繼承性、耦合性和多態(tài)性等方面提出的度量指標(biāo)[10].

1998年Watts和Strogatz在Nature雜志上首次提出了“WS小世界”模型，提出的模型具有較大的聚類系數(shù)和較短的平均路徑長度[11].1999年Barabási和Albert在的Science雜志上提出了無標(biāo)度(BA)網(wǎng)絡(luò)模型，以演員網(wǎng)絡(luò)和WWW為例，考慮到增長特性和優(yōu)先連接，指出現(xiàn)實中的網(wǎng)絡(luò)節(jié)點在增加時優(yōu)先與度數(shù)大的節(jié)點連接[12].2002年Valverde等從軟件的源代碼中提取組成單元抽象為節(jié)點，它們之間的依賴?yán)^承關(guān)系抽象為邊，復(fù)雜的軟件結(jié)構(gòu)用軟件圖表示，研究結(jié)論表明:像大量人工網(wǎng)絡(luò)那樣，軟件圖也具有“小世界”和“無標(biāo)度”的特性，為軟件的度量引入了新的方法和工具[13].隨后，Myers等在進(jìn)一步將軟件圖中的無向邊根據(jù)依賴(調(diào)用、繼承和消息等)關(guān)系轉(zhuǎn)化為有向邊，得到了類似的結(jié)論[14].Vassa等提出邊增長模型，檢測面向?qū)ο笙到y(tǒng)結(jié)構(gòu)的變化.發(fā)現(xiàn)在軟件升級中，修改代碼比刪除代碼更為常見，擁有更大扇入的類往往更容易被修改[15].

本文作者選取webwork 5.5和spring 4.2.0兩款開源軟件作為研究對象，框架都使用了依賴注入(Dependency Injection，DI)和控制反轉(zhuǎn)(Inversion of Control ,IoC).不同于傳統(tǒng)軟件工程提供的方法僅僅關(guān)心局部特征，而是利用復(fù)雜網(wǎng)絡(luò)理論從整體上把握系統(tǒng)，用復(fù)雜網(wǎng)絡(luò)的方法度量軟件.

1 復(fù)雜網(wǎng)絡(luò)

1.1 無向圖與有向圖

1)一個無向圖G定義為一個有序的二元組〈V,E〉 ，其中：V是非空有限集合稱為頂點集，其元素稱為頂點或節(jié)點；E稱為邊集，它是無序積V&V多重子集，其元素稱為無向邊，簡稱邊.對于任意的v∈V ,稱v作為G中邊的端點的次數(shù)之和為v的度數(shù)，簡稱度[16].

2)有向圖D與無向圖的定義類似，只是邊集E是卡氏積V×V的多重子集，其元素稱為有向邊，簡稱邊.對于任意的v∈V，稱v作為D中邊的起始的次數(shù)之和為v的出度；稱v作為D中邊終點的次數(shù)之和為v的入度，出度與入度之和為v的度.

面向?qū)ο蟮能浖到y(tǒng)可以表示成一個無向圖G(V,E)或有向依賴圖D(V,E)不同粒度的單元 (模塊、包、類和方法)可以被視為節(jié)點n(其中,n∈V).這些單元的關(guān)系(調(diào)用、繼承和消息等)形成圖的邊l(l∈E).

1.2 度與度分布

1)設(shè)vi是無向網(wǎng)絡(luò)中的任意節(jié)點，與vi相關(guān)聯(lián)的邊的數(shù)量，稱為該節(jié)點vi的度.若為有向網(wǎng)絡(luò)，vi作為網(wǎng)絡(luò)中邊的終點的邊的數(shù)量，稱為vi的入度；vi作為網(wǎng)絡(luò)中邊的始點的邊的數(shù)量，稱為vi的出度.網(wǎng)絡(luò)中所有節(jié)點vi的度ki的平均值稱為網(wǎng)絡(luò)的(節(jié)點)平均度，記為〈k〉[17]為

(1)

2)P(k)的含義是一個隨機選定的節(jié)點的度恰好為k的概率.網(wǎng)絡(luò)中節(jié)點的度的分布情況用分布函數(shù)P(k)來描述.

有向網(wǎng)絡(luò)的平均度可以求平均入度〈kin〉和平均出度〈kout〉為

(2)

(3)

Pin(k) 和Pout(k)分別表示入度分布和出度分布，含義是一個隨機選定的節(jié)點的入度或出度恰好為k的概率.

無標(biāo)度網(wǎng)絡(luò)具有冪指數(shù)形式的度分布，即p(k)～k-γ，有時也用累積度分布來描述度的分布情況，用公式表示為

度分布與累積度分布在雙對數(shù)坐標(biāo)中均表現(xiàn)為一條負(fù)斜率的直線.揭示網(wǎng)絡(luò)的度分布的統(tǒng)計特性對于復(fù)雜網(wǎng)絡(luò)研究具有重要意義，度描述了節(jié)點相互連接的統(tǒng)計特性，在社交網(wǎng)絡(luò)中，度數(shù)越大的節(jié)點往往對應(yīng)著明星用戶，擁有更多的粉絲和網(wǎng)絡(luò)影響力,也是復(fù)雜網(wǎng)絡(luò)演化的重要性質(zhì).

1.3 聚類系數(shù)

1)無向網(wǎng)絡(luò)中的節(jié)點vi與其他ki個節(jié)點相鄰，在這ki個節(jié)點之間最多可能有ki(ki-1)/2 條邊，而實際存在的邊數(shù)Ei，兩者之間的比值為

(4)

式中Ci為節(jié)點i的聚類系數(shù).

假設(shè)網(wǎng)絡(luò)的節(jié)點數(shù)為N，網(wǎng)絡(luò)的聚類系數(shù)定義為

(5)

2)所有以有向網(wǎng)絡(luò)中的節(jié)點vi為終點的弧的起始節(jié)點及它們之間的弧構(gòu)成一個小集團(tuán)，稱之為入集團(tuán)；而所有以該節(jié)點為起點的弧的終止節(jié)點及它們之間的弧構(gòu)成一個小集團(tuán)，稱之為出集團(tuán)[18].有ki,in個節(jié)點作為邊的始點，與ki,in個節(jié)點最多可能有ki(ki-1)條邊，而實際存在的邊數(shù)Ei，定義Ci,in稱節(jié)點vi的入集聚系數(shù)為

(6)

Ci,out稱節(jié)點vi的出集聚系數(shù)為

(7)

Cin是網(wǎng)絡(luò)的入集團(tuán)的聚集系數(shù)為

(8)

Cout是網(wǎng)絡(luò)的出集團(tuán)的聚集系數(shù)為

(9)

1.4 平均路徑長度

網(wǎng)絡(luò)中兩個節(jié)點vi,vj之間邊數(shù)最少的一條簡單路徑，稱為測地線.網(wǎng)絡(luò)中兩個節(jié)點i和j之間的距離dij定義為測地線的邊數(shù)，網(wǎng)絡(luò)的直徑(diameter)，記為D定義為網(wǎng)絡(luò)中任意兩個節(jié)點之間的距離的最大值稱為D=max dij.

網(wǎng)絡(luò)的平均路徑長度L定義為所有節(jié)點對之間的距離的平均值為

(10)

如不考慮節(jié)點到自身的距離，在式中包含了節(jié)點到自身的距離dii=0，網(wǎng)絡(luò)的平均路徑長度L為

(11)

有向網(wǎng)絡(luò)中定義平均路徑與無向網(wǎng)絡(luò)非常類似，只是有向圖路徑中有向邊方向必須一致[7-8]，網(wǎng)絡(luò)的平均路徑長度L為

(12)

復(fù)雜網(wǎng)絡(luò)具有大的聚類系數(shù)和小的平均距離，具有小世界效應(yīng).

2 復(fù)雜性度量

本文作者使用兩款開源軟件對面向?qū)ο罂蚣躻ebwork和spring進(jìn)行分析.使用DependencyFinder和Pajek作為分析工具.

webwork是由OpenSymphony組織開發(fā)的，致力于組件化和代碼重用的J2EE Web框架.spring是輕量級的Java 開發(fā)框架,見表1.

表1 兩款軟件的參數(shù)Tab.1 Parameters of the two software

DependencyFinder分析工具可以實現(xiàn)從Java字節(jié)碼文件中抽取依賴關(guān)系和面向?qū)ο蠖攘?Pajek是專門用來分析大型網(wǎng)絡(luò)(含有成百上千個節(jié)點的專用程序)[19].

2.1 軟件依賴

圖1為模塊(對象、類、方法和子程序)抽象為節(jié)點A、B、C，關(guān)系抽象為邊.其中圖1(a)為編寫的一段示例代碼，圖1(b)表示類A,B,C之間的關(guān)系.圖中的邊表示類之間的無向關(guān)系.圖(c)表示類A,B,C之間的有向關(guān)系.類B調(diào)用了A中的方法aMethod(·)，C調(diào)用了B中的方法bMethod(·).以便于對多線程序進(jìn)行度量.

2.2 webwork和spring的參數(shù)分析

Pajek運行在Windows環(huán)境，用于帶上千及至數(shù)百萬個節(jié)點大型網(wǎng)絡(luò)的分析和可視化操作[19].

圖2是用Pajek畫出的webwork包為節(jié)點的無向軟件關(guān)系圖.圖3是spring包為節(jié)點的有向軟件關(guān)系圖.圖2中點表示軟件系統(tǒng)中的包，邊(弧)表示包之間有依賴等關(guān)系.

2.3 webwork和spring的聚類系數(shù)

表2中為將webwork和spring抽象為無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)入集團(tuán)和出集團(tuán)時的聚類系數(shù).

表2 兩款軟件的聚類系數(shù)Tab.2 Clustering coefficients of the two software

利用公式C=p=〈k〉/N,可計算出相同節(jié)點情況下隨機網(wǎng)絡(luò)的聚類系數(shù)，其中:C是聚類系數(shù);p代表ER隨機圖兩節(jié)點連接的概率;〈k〉為平均度;N為網(wǎng)絡(luò)節(jié)點數(shù).ER隨機網(wǎng)絡(luò)服從泊松分布，計算可得出：與webwork相同節(jié)點的隨機網(wǎng)絡(luò)的聚類系數(shù)分別為0.01，0.002，0.002，和spring相同節(jié)點的隨機網(wǎng)絡(luò)的聚類系數(shù)分別為0.017,0.004,0.004.對比表2中的數(shù)據(jù)可以看出軟件復(fù)雜網(wǎng)絡(luò)的聚類系數(shù)明顯大于隨機網(wǎng)絡(luò)的聚類系數(shù).軟件復(fù)雜網(wǎng)絡(luò)有明顯的聚類特性.

2.4 webwork和spring的平均路徑長度

表3中為將webwork和spring抽象為無向網(wǎng)絡(luò)和有向網(wǎng)絡(luò)入集團(tuán)和出集團(tuán)時的平均路徑長度.

表3 兩款軟件的平均路徑長度Tab.3 Average distances of the two software

利用公式L=ln N/ln〈k〉可計算出相同節(jié)點情況下隨機網(wǎng)絡(luò)的平均路徑長度，其中，L為隨機網(wǎng)絡(luò)的平均路徑長度，N為網(wǎng)絡(luò)節(jié)點數(shù)，〈k〉為平均度，計算可得出：和webwork相同節(jié)點的隨機網(wǎng)絡(luò)的平均路徑長度分別為2.82，7.07，7.07，和spring相同節(jié)點的隨機網(wǎng)絡(luò)的平均路徑長度分別為2.68，5.35，5.35.對比表3中的數(shù)據(jù)可以看出，軟件復(fù)雜網(wǎng)絡(luò)的聚類系數(shù)明顯接近于隨機網(wǎng)絡(luò)的平均路徑長度聚類系數(shù)，軟件復(fù)雜網(wǎng)絡(luò)具有小世界特性.

2.5 webwork和spring的度分布

復(fù)雜網(wǎng)絡(luò)的連接度分布服從冪律特征，即網(wǎng)絡(luò)節(jié)點的度函數(shù)具有冪律形式，節(jié)點的連接沒有明顯的尺度特征，不像隨機網(wǎng)絡(luò)可以把平均度看作節(jié)點度的特征，這類網(wǎng)絡(luò)也稱作無標(biāo)度網(wǎng)絡(luò).

圖4和圖5是無向圖的度分布與有向圖圖的入度、出度的p(k)分布函數(shù).而且曲線可以看出擬合成一條直線(以下圖都用 “.”表示無向圖;“*”表示有向圖入度;“+”表示有向圖出度).

圖6和圖7是無向圖的累積度分布與有向圖圖的累積入度、出度的p(k)分布函數(shù).而且曲線可以擬合成一條直線.

網(wǎng)絡(luò)中節(jié)點出現(xiàn)了很多度數(shù)為某些較大值時，沒有對應(yīng)節(jié)點的度數(shù)等于該值，如果將對應(yīng)的度數(shù)為零的值去掉去掉，圖8和圖9是簡化的無向圖的累積度分布與有向圖圖的累積入度、出度的p(k)分布函數(shù).而且曲線可以擬合成一條直線.

通過分析網(wǎng)絡(luò)的度分布和累積度分布表明：表明軟件圖具有冪律分布特性，也就是無標(biāo)度特性.

3 結(jié)論

本文使用webwork和spring作為研究對象，其不同于其他軟件的特點是原來的關(guān)聯(lián)實體類到關(guān)聯(lián)加載配置文件類 ,影響節(jié)點的度包括入度和出度，使無(有)向圖的邊數(shù)改變.本文采用逆向工程的方法，得出網(wǎng)絡(luò)模型.使用復(fù)雜網(wǎng)絡(luò)理論分析，復(fù)雜網(wǎng)絡(luò)復(fù)雜性度量計算其聚類系數(shù)和平均路徑長度，分析結(jié)果：同其他面向?qū)ο筌浖愃栖浖?nèi)部結(jié)構(gòu)具有小世界特性.對其度分布進(jìn)行分析，結(jié)果顯示，網(wǎng)絡(luò)節(jié)點的度函數(shù)具有冪律形式，具有無標(biāo)度特性.

[1] 你如果無法度量它，就無法管理它[EB/OL].(2013-03-27)[2015-12-30]. https://book.douban.com/review/5823792/. It you can't measure it,you can't manage it[EB/OL].(2013-03-27)[2015-12-30].https://book.douban.com/review/5823792/. (in Chinese)

[2] EMERSON T J. A discriminate metric for module comprehension[C]. Proceedings of 7th International Conference on SW-Engineering , 1984: 294-431.

[3] MA Y HE K, DU D. A qualitative method for measuring the structural complexity of software systems based on complex networks[C]. Software Engineering Conference, 2005: 257-263.

[4] HALSTEAD M H. Elements of software science[M].New York: Elsevier North-Holland, 1997: 2-10.

[5] MCCABE T J. A complexity measure[J]. IEEE Transactions on Software Engineering, 1976,2(4):308-320.

[6] HENRY S M, KAFURA D. Software structure metrics based on information flow[J]. IEEE Transactions on Software Engineering, 1981,7(5): 510-518.

[7] KAVITHA A, SHANMUGAM A. Dynamic coupling measurement of object oriented software using trace events[C]. International Symposium on Applied Machine Intelligence and Informatics, 2008: 255-259.

[8] YAU S S , COLLOFELLO J S. Some stability measures for software maintenance[J]. IEEE Transactions on Software Engineering, 1980,6(6): 545-552.

[9] CHIDAMBER S R, KEMERER C F. A metrics suite for object oriented design[J]. IEEE Transactions on Software Engineering,1994, 20(6):476-492.

[10] BRITO F, ABREU E. MOOD-metrics for object-oriented design[C]. COOPSLA’94 Workshop on Pragmatic and Theoretical Directions in Object-Oriented Software Metrics,1994.

[11] WATTS D J, STROGATZ S H. Collective dynamics of small-world networks[J]. Nature, 1998, 393: 440-442.

[13] VALVERDE S, CANEHO R F, SOLE R V. Scale free networks from optimal design[J]. Europhysics Letters, 2002, 60(4):512-517.

[14] MYERS C R. Software systems as complex networks:structure,function,and evolvability of software collaboration graphs[J]. Physical Review E Statistical Nonlinear & Soft Matter Physics,2003,68(4):352-375.

[15] VASA R,SCHNEIGER J G,WOODWARD C, et al. Detecting structural changes in object oriented software systems[C]. International Symposium on Empirical Software Engineering, 2005: 479-486.

[16] 耿素云，屈婉玲，王捍貧.離散數(shù)學(xué)教程[M].北京:北京大學(xué)出版社,2002:109-110. GENG Suyun, QU Wanling, WANG Hanpin.Discrete mathematics[M].Beijing:Peking University Press,2002:109-110.(in Chinese)

[17] 汪曉帆，李翔，陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京：清華大學(xué)出版社,2006：1-48. WANG Xiaofan，LI Xiang，CHEN Guanrong. Complex networks theory and its application [M]. Beijing: Tsinghua University Press, 2006:1-48.(in Chinese)

[18] 復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論[EB/OL].(2013-05-02)[2015-12-30] .http://wenku.baidu.com/link?url=UonUDDZwfQoffb VwSju8YrMsOuEB-sHcmdOtbRJN2O ZGPT Jw- LQyEN4vz8b2o9Po7d2hXQRTeu EonnshKEn-B-Sb B-TWxQeceDi0v0w3aVeda. Complex network fundemental theory[EB/OL].(2013-05-02)[2015-12-30] .http://wenku.baidu.com/link?url=UonUDDZwfQoffb VwSju8YrMsOuEB-sHcmdOtbRJN2OZGPT JwLQyEN4vz8b2o9Po7d2hXQRT-eu EonnshKEn-B-Sb BTWxQeceDi0v0w3aVeda.(in Chinese)

[19] Pajek中文使用手冊[EB/OL].(2012-05-19)[ 2015-12-30]. http://www.doc88.com/p-395360089504.html. Pajek User manual in Chinese[EB/OL].(2012-05-19)[ 2015-12-30]. http://www.doc88.com/p-395360089- 504.html. (in Chinese)

Complex networks and software metrics analysis

MAJian1，F(xiàn)ANJianping2，LIUFeng1

(1.School of Computer and Information Technology , Beijing Jiaotong University, Beijing 100044，China ; 2. Shenzhen Institutes of Advanced Technology,Chinese Academy of Sciences， Shenzhen Guangdong 518055， China)

Complex network theory is used to study the complexity of the software system in this paper. The selected object-oriented open-source software framework both webwork and spring as the research object, undirected (directed) graph nodes representing classes, relationships between classes edges representing dependency, association, etc., the system is abstracted to the network graph and its topology is analyzed. Studies show that undirected (directed) network has a large clustering coefficient and a smaller average path length, which are characteristics of a small world. Because of the inversion control and dependency injection used in the framework, program relations between classes, entirely controlled by the spring container, rather than by code control, will be injected into the container runtime according to configuration information provided by the spring assembly. Using dependency injection is to change the relationship between the compilation phases of the class such as an associated entity class changed to the class of associated load configuration file. Thus it influences the degree of the nodes including in-degree and out-degree and change the number of undirected (directed) graph edges (arcs) has been changed. The results show that the statistical properties of the degree distribution still have scale-free characteristics.

software metrics; complex network; degree distribution; clustering coefficients

2016-02-21

國家“863”高技術(shù)研究發(fā)展計劃項目資助 (2015AA043701)

馬健(1985—)，女，山西長治人，博士生.研究方向為軌道信息交通技術(shù).email:13112083@bjtu.edu.cn.

TP311

A

1673-0291(2016)05-0023-06

10.11860/j.issn.1673-0291.2016.05.004