基于復(fù)雜網(wǎng)絡(luò)的大型軟件復(fù)雜性度量

王偉

摘要：軟件系統(tǒng)的復(fù)雜性不斷增長(zhǎng)，這與軟件的開(kāi)發(fā)成本、質(zhì)量以及效率等息息相關(guān)，傳統(tǒng)的復(fù)雜性度量已經(jīng)不能滿(mǎn)足需要。因此，度量一個(gè)大型軟件系統(tǒng)的復(fù)雜性有助于保證軟件質(zhì)量和優(yōu)化軟件結(jié)構(gòu)。復(fù)雜網(wǎng)絡(luò)理論的研究為軟件復(fù)雜性度量提供了理論依據(jù)和新的方向。從大型軟件系統(tǒng)的結(jié)構(gòu)出發(fā)通過(guò)數(shù)學(xué)建?？梢园l(fā)現(xiàn)其具有復(fù)雜網(wǎng)絡(luò)特性，進(jìn)而提出了一個(gè)新的方法對(duì)大型軟件系統(tǒng)的結(jié)構(gòu)復(fù)雜性進(jìn)行度量。

關(guān)鍵詞：軟件復(fù)雜性；復(fù)雜網(wǎng)絡(luò)；復(fù)雜性度量；大型軟件系統(tǒng)

中圖分類(lèi)號(hào)：TP391.41

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.3969/j.issn.1003-6970.2015.11.023

0 引言

質(zhì)量是工程技術(shù)領(lǐng)域中不可缺少的一個(gè)重要因素，隨著軟件工程的發(fā)展，軟件質(zhì)量受到越來(lái)越廣泛的關(guān)注，度量技術(shù)在軟件工程領(lǐng)域的作用越來(lái)越重要，因?yàn)椤叭魏尾豢啥攘康亩际遣豢煽氐摹?。軟件設(shè)計(jì)開(kāi)發(fā)的過(guò)程中軟件度量是其科學(xué)性的重要保證，缺乏合理的度量往往會(huì)使得軟件開(kāi)發(fā)處于失控狀態(tài)。軟件度量的基礎(chǔ)性工作早就已經(jīng)進(jìn)行，之后McCabe和Halstead提出了結(jié)構(gòu)化程序度量方法McCabe環(huán)復(fù)雜度，它首次考慮了軟件內(nèi)部的拓?fù)浣Y(jié)構(gòu)特性。

面向?qū)ο笤O(shè)計(jì)已經(jīng)成為軟件設(shè)計(jì)和開(kāi)發(fā)中應(yīng)用的主要方法，但是之前提出的度量方法不能滿(mǎn)足面向?qū)ο筌浖奶匦?。因此，學(xué)者們開(kāi)始研究面向?qū)ο蟮能浖攘糠椒?，Brit和Abreu提出了MOOD方法，Chidamber和Kemerer提出了C&K方法。它們主要的關(guān)注點(diǎn)在于類(lèi)，衡量類(lèi)與類(lèi)之間以及類(lèi)的內(nèi)部關(guān)系的復(fù)雜性。隨著軟件規(guī)模的不斷增大軟件系統(tǒng)的復(fù)雜程度也越來(lái)越高，軟件質(zhì)量保證變得尤其重要，而軟件復(fù)雜性的度量關(guān)系到軟件的可靠性、可維護(hù)性等質(zhì)量因素。以上的方法對(duì)于大型軟件而言有如下問(wèn)題：只注重統(tǒng)計(jì)關(guān)系，不能反映類(lèi)之間的相互作用；僅注重統(tǒng)計(jì)與對(duì)象類(lèi)有關(guān)的數(shù)量和規(guī)模，沒(méi)有關(guān)注粗粒度的模塊構(gòu)件等方面的度量；缺乏全局的復(fù)雜性度量。

近年來(lái)復(fù)雜網(wǎng)絡(luò)理論的提出使得大型軟件系統(tǒng)的度量有了全新的研究角度。研究表明，Internet、生態(tài)網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等都具有明顯的復(fù)雜網(wǎng)絡(luò)特性，通過(guò)將這些真實(shí)的網(wǎng)絡(luò)用復(fù)雜網(wǎng)絡(luò)建模進(jìn)行研究可以發(fā)現(xiàn)它們的形成和演化的規(guī)律。這對(duì)于生物學(xué)、物理學(xué)、社會(huì)學(xué)等的發(fā)展具有積極的影響。不僅如此，軟件系統(tǒng)中存在大量的類(lèi)、對(duì)象、構(gòu)件等，對(duì)這些元素進(jìn)行建?？梢园l(fā)現(xiàn)明顯的復(fù)雜網(wǎng)絡(luò)現(xiàn)象。因此，將復(fù)雜網(wǎng)絡(luò)的性質(zhì)、規(guī)律等用于軟件系統(tǒng)結(jié)構(gòu)特性的研究中可以讓我們對(duì)軟件系統(tǒng)有更加充分的理解并能夠更好的對(duì)軟件系統(tǒng)進(jìn)行控制。

本文首先分析了大型軟件系統(tǒng)的結(jié)構(gòu)，發(fā)現(xiàn)其具有明顯的復(fù)雜網(wǎng)絡(luò)特性，然后介紹復(fù)雜網(wǎng)絡(luò)的基本理論和大型軟件系統(tǒng)的網(wǎng)絡(luò)性質(zhì)，利用復(fù)雜網(wǎng)絡(luò)理論進(jìn)行軟件復(fù)雜性度量并對(duì)實(shí)例進(jìn)行了分析。

1 復(fù)雜網(wǎng)絡(luò)與軟件網(wǎng)絡(luò)特性

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

隨著計(jì)算機(jī)的數(shù)據(jù)處理能力和計(jì)算能力的快速發(fā)展，大量的、真實(shí)系統(tǒng)的網(wǎng)絡(luò)模型都被證明具有明顯的統(tǒng)計(jì)特征，由于這些網(wǎng)絡(luò)是從真實(shí)復(fù)雜系統(tǒng)的拓?fù)浣Y(jié)構(gòu)抽象得到，所以被稱(chēng)為復(fù)雜網(wǎng)絡(luò)（Complex net-works）。Barabasi和Watts等通過(guò)對(duì)現(xiàn)實(shí)世界中的大量真實(shí)網(wǎng)絡(luò)進(jìn)行研究證明了它們都具有小世界（SW，Small-World）效應(yīng)和無(wú)標(biāo)度特性（SF，Scale-Free）。小世界特性表明了復(fù)雜網(wǎng)絡(luò)中的大部分連結(jié)集中在少數(shù)節(jié)點(diǎn)之上，無(wú)標(biāo)度特性是指網(wǎng)絡(luò)的度分布服從冪級(jí)分布。

1.2 軟件系統(tǒng)的復(fù)雜網(wǎng)絡(luò)特性

復(fù)雜網(wǎng)絡(luò)理論的深入研究，帶動(dòng)了其在軟件領(lǐng)域的應(yīng)用研究。大型復(fù)雜軟件通常由多人協(xié)同開(kāi)發(fā)，在開(kāi)發(fā)過(guò)程中復(fù)雜的功能會(huì)被分解為若干可重用的單元，因此大型軟件系統(tǒng)中存在大量不同粒度的單元，如方法、類(lèi)、包、接口、編譯單元等。這些元素之間的關(guān)系是多樣的，如類(lèi)的繼承、方法的調(diào)用，以這些單元為節(jié)點(diǎn)，它們之間的關(guān)系為邊，就可以構(gòu)成一個(gè)復(fù)雜網(wǎng)絡(luò)，對(duì)這種軟件復(fù)雜網(wǎng)絡(luò)研究表明，大型軟件系統(tǒng)的拓?fù)浣Y(jié)構(gòu)具有明顯的復(fù)雜網(wǎng)絡(luò)特性。

Potanin等對(duì)幾個(gè)大型面向?qū)ο蟮能浖到y(tǒng)的研究，它們的網(wǎng)絡(luò)都具有明顯的復(fù)雜網(wǎng)絡(luò)特征。Valverde等研究了軟件的拓?fù)浣Y(jié)構(gòu)，發(fā)現(xiàn)它們都呈現(xiàn)出明顯的復(fù)雜網(wǎng)絡(luò)特征。Myers研究了軟件系統(tǒng)中模塊之間的協(xié)作和調(diào)用關(guān)系的網(wǎng)絡(luò)模型，證明了軟件網(wǎng)絡(luò)的無(wú)標(biāo)度特性。Wheeldon等以大型軟件系統(tǒng)的不同屬性和關(guān)系構(gòu)造多個(gè)網(wǎng)絡(luò)，證明了這些軟件網(wǎng)絡(luò)都具有無(wú)標(biāo)度特性。Tamai等通過(guò)統(tǒng)計(jì)學(xué)方法證明了大型軟件中類(lèi)的方法數(shù)和方法的代碼行數(shù)所具有的無(wú)標(biāo)度特性。

因此隨著軟件系統(tǒng)的發(fā)展，軟件與網(wǎng)絡(luò)之間的關(guān)系越來(lái)越密切。從復(fù)雜網(wǎng)絡(luò)的角度，它為我們重新認(rèn)識(shí)軟件和軟件工程提供了堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)。

2 軟件復(fù)雜性度量

2.1 大型軟件系統(tǒng)的網(wǎng)絡(luò)化建模

目前，進(jìn)行軟件系統(tǒng)的復(fù)雜網(wǎng)絡(luò)研究時(shí)實(shí)現(xiàn)軟件系統(tǒng)網(wǎng)絡(luò)化的方法主要是逆向工程方法，即從代碼中獲得類(lèi)圖，在進(jìn)一步得到網(wǎng)絡(luò)圖。從而，我們可以分析大型復(fù)雜軟件系統(tǒng)的組織結(jié)構(gòu)，發(fā)現(xiàn)其整體的復(fù)雜網(wǎng)絡(luò)特性，而不是一些獨(dú)立的組件堆積出的軟件所具有的性質(zhì)。

因此我們定義一個(gè)復(fù)雜網(wǎng)絡(luò)G=（V，E），其中V為節(jié)點(diǎn)的集合，E為邊的集合，E中的邊代表元素之間的關(guān)系。

2.2 復(fù)雜性的度量

大量研究已經(jīng)證明，復(fù)雜軟件系統(tǒng)的拓?fù)浣Y(jié)構(gòu)具有小世界特性和無(wú)標(biāo)度特性。目前，大型復(fù)雜軟件系統(tǒng)的發(fā)展主要是以組件軟件技術(shù)為基礎(chǔ)，架構(gòu)主要是面向服務(wù)的，每個(gè)組件的編程方法用面向?qū)ο筮M(jìn)行設(shè)計(jì)。因此，現(xiàn)在的軟件系統(tǒng)與客觀的世界更相似，具有更加明顯的無(wú)標(biāo)度特性，而軟件中組件的復(fù)用則使得其小世界特性更加顯著。軟件中組件的自主性和異質(zhì)性使得它們成為不同的層次。這些組件以服務(wù)的方式相互作用，因此，組件之間的耦合較為松散。綜上所述，大型復(fù)雜軟件系統(tǒng)的拓?fù)浣Y(jié)構(gòu)具有明顯的復(fù)雜網(wǎng)絡(luò)特性。endprint

在大型軟件系統(tǒng)的復(fù)雜性度量中，將軟件的類(lèi)、對(duì)象、方法等定義為節(jié)點(diǎn)，它們之間的關(guān)系定義為邊。軟件復(fù)雜性度量中基于復(fù)雜網(wǎng)絡(luò)理論得出的參數(shù)有以下幾種。

平均距離D（Average distance）。網(wǎng)絡(luò)中節(jié)點(diǎn)i到節(jié)點(diǎn)j至少要經(jīng)過(guò)的邊的數(shù)目為兩點(diǎn)間的最短距離，用d_min（i，j）表示。在無(wú)向網(wǎng)絡(luò)中，網(wǎng)絡(luò)的平均距離定義如下：

根據(jù)網(wǎng)絡(luò)的定義可知，V為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，而N則為網(wǎng)絡(luò)中所擁有的節(jié)點(diǎn)總數(shù)。

聚集系數(shù)C（Clustering coefhcient）。某節(jié)點(diǎn)i的集聚系數(shù)為：

C_i=2E_i/[k_i（k_i-1）]

其中k_i表示節(jié)點(diǎn)i的鄰邊個(gè)數(shù)，這些鄰邊之間有E_i條連邊。它度量的是節(jié)點(diǎn)的聚集程度。

整個(gè)網(wǎng)絡(luò)的聚集系數(shù)是每個(gè)節(jié)點(diǎn)聚集系數(shù)的平均值：

度和度分布（Degree&Degree-distribution）。節(jié)點(diǎn)的度用來(lái)描述該節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度，用網(wǎng)絡(luò)中與其相連的邊的個(gè)數(shù)表示。在有向網(wǎng)絡(luò)中，節(jié)點(diǎn)的度分為人度和出度，入度為指向該節(jié)點(diǎn)的邊的個(gè)數(shù)，出度為從該節(jié)點(diǎn)指出的邊的個(gè)數(shù)。在無(wú)向網(wǎng)絡(luò)中，不區(qū)分入度和出度。P（k）表示網(wǎng)絡(luò)中度數(shù)為k的節(jié)點(diǎn)在網(wǎng)絡(luò)中所占的比例。在復(fù)雜網(wǎng)絡(luò)中它服從冪級(jí)分布P（k）=k^-r，即具有無(wú)標(biāo)度特性。

模塊性T（Community modularity）。社區(qū)模塊性的定義需要基于以下兩個(gè)前提：（1）社區(qū)間的結(jié)點(diǎn)之間應(yīng)盡可能少的相連；（2）社區(qū)內(nèi)的結(jié)點(diǎn)之間應(yīng)盡可能多的相連。模塊性的定義如下：

其中，L為圖G中的總邊數(shù)。I_t社區(qū)Q_t內(nèi)各節(jié)點(diǎn)之間的總邊數(shù)，k_t為社區(qū)Q_t內(nèi)所有節(jié)點(diǎn)的總度數(shù)。T值越大表明越多的邊在屬于選定的社區(qū)，社區(qū)的模塊性越為明顯。軟件系統(tǒng)的構(gòu)件、包等就是由許多類(lèi)構(gòu)成的一個(gè)聚合性高且耦合性低的類(lèi)集合。因此，對(duì)于特定的構(gòu)件或包，T值越大，則該劃分的模塊性越好。

介數(shù)B（Betweenness centrality））。介數(shù)的定義分為節(jié)點(diǎn)的介數(shù)和邊的介數(shù)。網(wǎng)絡(luò)中任意連通的兩個(gè)節(jié)點(diǎn)之間都至少存在著一條最短路徑。因此對(duì)于節(jié)點(diǎn)而言，其介數(shù)可用整個(gè)網(wǎng)絡(luò)中最短路徑總數(shù)與通過(guò)該節(jié)點(diǎn)的最短路徑的條數(shù)之比來(lái)表示，通過(guò)某節(jié)點(diǎn)的最短路徑數(shù)量越多則該節(jié)點(diǎn)越重要。因此結(jié)點(diǎn)的介數(shù)定義如下：

相關(guān)性R（Correlation）。度和聚集系數(shù)之間的相關(guān)性描述了不同網(wǎng)絡(luò)結(jié)構(gòu)的差異，它包括以下兩個(gè)方面：度數(shù)不同的節(jié)點(diǎn)之間的相關(guān)性、節(jié)點(diǎn)的聚集系數(shù)與度之間的相關(guān)性。

3 實(shí)驗(yàn)驗(yàn)證

3.1 建模

實(shí)驗(yàn)選擇一個(gè)開(kāi)源的大型軟件系統(tǒng)進(jìn)行研究，把它的類(lèi)作為一個(gè)單元，并將軟件系統(tǒng)分解成類(lèi)單元的不同集合。通過(guò)這些類(lèi)單元之間的交互，軟件系統(tǒng)的所有功能都可以實(shí)現(xiàn)。用這些類(lèi)單元作為節(jié)點(diǎn)，它們之間的相互作用作為邊，則軟件的系統(tǒng)結(jié)構(gòu)和其中復(fù)雜的連接關(guān)系可以用如下的網(wǎng)絡(luò)圖進(jìn)行表示：

3.2 仿真結(jié)果和復(fù)雜性分析

利用本文提出的復(fù)雜性度量方法可以得到表2所示的統(tǒng)計(jì)計(jì)算結(jié)果。從表中可以看出，這個(gè)網(wǎng)絡(luò)的平均最短距離是3.6012，它反映了網(wǎng)絡(luò)中信息傳播的便利程度。網(wǎng)絡(luò)聚集系數(shù)是0.1012，這一參數(shù)值相對(duì)較高，說(shuō)明網(wǎng)絡(luò)中不同實(shí)體間的信息交換較為順暢。這只是基本的統(tǒng)計(jì)結(jié)果，需要進(jìn)一步進(jìn)行分析才能獲得軟件系統(tǒng)的復(fù)雜性。

通過(guò)在雙對(duì)數(shù)坐標(biāo)下對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的度進(jìn)行分析可以發(fā)現(xiàn)其度分布為P（k）～k^-r。這一現(xiàn)象表示這一軟件網(wǎng)絡(luò)符合冪級(jí)分布，即網(wǎng)絡(luò)具有無(wú)標(biāo)度特性。這一特性表明軟件中存在一些中心節(jié)點(diǎn)與其他大多數(shù)節(jié)點(diǎn)相連，這些節(jié)點(diǎn)在網(wǎng)絡(luò)中具有重要的作用，可以影響其他度數(shù)相對(duì)小的節(jié)點(diǎn)。而且，軟件網(wǎng)絡(luò)中如果新增節(jié)點(diǎn)也會(huì)優(yōu)先與中心節(jié)點(diǎn)相連.

4 結(jié)論

本文中應(yīng)用復(fù)雜網(wǎng)絡(luò)的理論從全局角度分析了大型軟件系統(tǒng)的統(tǒng)計(jì)特性。并對(duì)其進(jìn)行了深入的研究，結(jié)果表明這一軟件網(wǎng)絡(luò)中的平均最短距離、聚集系數(shù)等都比隨機(jī)網(wǎng)絡(luò)要高，并且網(wǎng)絡(luò)的度呈冪級(jí)分布。進(jìn)而可以得出結(jié)論：該軟件系統(tǒng)網(wǎng)絡(luò)的小世界特性和無(wú)標(biāo)度特性較為明顯。

然而，將復(fù)雜網(wǎng)絡(luò)理論用于軟件度量的研究工作尚為完善，沿著這一思路進(jìn)行深入的研究，會(huì)讓我們更加了解軟件系統(tǒng)復(fù)雜網(wǎng)絡(luò)特性，對(duì)軟件度量以及軟件工程也具有重要的意義。endprint