復(fù)雜軟件群體網(wǎng)絡(luò)社團(tuán)中關(guān)鍵節(jié)點(diǎn)挖掘算法

李維娜，任家東

1(燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004)2(河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004)3(河北省軟件工程重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004)

1 引 言

大型軟件系統(tǒng)往往由很多獨(dú)立的軟件個(gè)體組成，這些軟件個(gè)體之間因具有可以獨(dú)立運(yùn)行，同時(shí)又相互交互的特點(diǎn)，而區(qū)別于軟件模塊[1].開(kāi)源軟件及云服務(wù)的出現(xiàn)促進(jìn)了這樣的大型軟件系統(tǒng)的產(chǎn)生與發(fā)展[2，3].軟件之間的交互結(jié)構(gòu)形成了軟件關(guān)系網(wǎng)絡(luò)，網(wǎng)絡(luò)的穩(wěn)定、平衡、和諧的存在是企事業(yè)單位穩(wěn)健發(fā)展的關(guān)鍵.復(fù)雜網(wǎng)絡(luò)很好描述了自然科學(xué)，社會(huì)科學(xué)，管理科學(xué)及工程技術(shù)領(lǐng)域的具有交互關(guān)系的復(fù)雜模型，復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)及數(shù)據(jù)挖掘聚類算法的大量的研究成果，已經(jīng)應(yīng)用于電網(wǎng)，社交網(wǎng)絡(luò)，生物醫(yī)學(xué)網(wǎng)絡(luò)，交通網(wǎng)絡(luò)，軟件結(jié)構(gòu)，并逐見(jiàn)成效[4，6].基于復(fù)雜網(wǎng)絡(luò)及數(shù)據(jù)挖掘的方法來(lái)尋求高效及低成本的軟件維護(hù)解決方案，成為熱門(mén)的研究思路[7].

1970年，美國(guó)學(xué)術(shù)機(jī)構(gòu)提出了開(kāi)源軟件的定義：是一個(gè)自由發(fā)布，代碼公開(kāi)，用戶免費(fèi)使用的軟件系統(tǒng)，而后的90年代才大量出現(xiàn)；并且最近十多年得到了研究和發(fā)展，開(kāi)源軟件的特點(diǎn)漸漸被人知曉[8]，有很多成功的案例如：Apache，PHP，Nginx，MySQL，MariaDB等；一個(gè)完整的開(kāi)源軟件系統(tǒng)包括了開(kāi)發(fā)者，用戶及軟件本身三大要素.開(kāi)源ERP及CRM軟件在企業(yè)中的應(yīng)用也越來(lái)越得到認(rèn)可，這得益于開(kāi)源軟件工程本身的價(jià)格優(yōu)勢(shì)和逐漸提高的質(zhì)量，以及企業(yè)有限的資源[9].開(kāi)源軟件社區(qū)也在這樣的條件下逐漸形成.開(kāi)源社區(qū)的大量的成員對(duì)軟件的使用和測(cè)試是保障開(kāi)源軟件的質(zhì)量基礎(chǔ)，是其能長(zhǎng)期生存的必備條件，但并不是所有的開(kāi)源社區(qū)都注重軟件質(zhì)量[10，11].開(kāi)源軟件社區(qū)的全球性開(kāi)放性特點(diǎn)促進(jìn)它逐漸龐大，進(jìn)而形成大量的軟件個(gè)體，而社區(qū)往往具有目的統(tǒng)一性，形成的軟件具有交互性，類庫(kù)依賴性，而且同類型軟件會(huì)存在多個(gè)，交互軟件群體在這種條件下就產(chǎn)生了.然而，社區(qū)管理的自由渙散讓這些軟件群體很難有很高的穩(wěn)定性，急需一種高效的軟件群體管理思路.

大量的學(xué)者在單個(gè)軟件中，通過(guò)從源代碼的角度用靜態(tài)及動(dòng)態(tài)方式對(duì)軟件結(jié)構(gòu)特性進(jìn)行了研究.2002年Valverde等[12]使用無(wú)向網(wǎng)絡(luò)表示軟件的系統(tǒng)結(jié)構(gòu)，即用網(wǎng)絡(luò)模型中的節(jié)點(diǎn)來(lái)表示類，而邊用來(lái)表示類與類之間的關(guān)聯(lián)、繼承等關(guān)系，分析軟件系統(tǒng)的拓?fù)浣Y(jié)構(gòu)，給出小世界、無(wú)標(biāo)度的結(jié)構(gòu)特性.2003年Myers和Moura等[13，14]進(jìn)一步對(duì)軟件的系統(tǒng)結(jié)構(gòu)用有向網(wǎng)絡(luò)來(lái)進(jìn)行表示，并對(duì)大量開(kāi)源軟件進(jìn)行了分析，也發(fā)現(xiàn)了同樣的特性.近幾年，國(guó)內(nèi)外的相關(guān)工作已經(jīng)通過(guò)建立軟件網(wǎng)絡(luò)模型，揭示軟件網(wǎng)絡(luò)的一些普遍的拓?fù)涮卣?2009年，Cai等[15]根據(jù)軟件的動(dòng)態(tài)執(zhí)行過(guò)程提出了鏡像進(jìn)化圖，并對(duì)平均路徑、聚類系數(shù)等拓?fù)涠攘恐匦逻M(jìn)行了定義，發(fā)現(xiàn)存在于軟件執(zhí)行網(wǎng)絡(luò)中的“小世界”現(xiàn)象在軟件的動(dòng)態(tài)執(zhí)行過(guò)程中消失了，且體現(xiàn)“無(wú)標(biāo)度”特性的冪率分布中也出現(xiàn)了分段現(xiàn)象.2012年，Ma等[16]將一個(gè)軟件包映射為一個(gè)復(fù)雜網(wǎng)絡(luò)，其中函數(shù)作為節(jié)點(diǎn)，函數(shù)間依賴關(guān)系作為邊，以此而構(gòu)建的復(fù)雜軟件網(wǎng)絡(luò)模型能很好地反應(yīng)真實(shí)世界中軟件包的特性，并提出一種新的符合軟件開(kāi)發(fā)的網(wǎng)絡(luò)增長(zhǎng)模式，為今后研究軟件網(wǎng)絡(luò)特性提供了一種新的觀點(diǎn).

數(shù)據(jù)挖掘的圖挖掘算法的研究促進(jìn)了復(fù)雜網(wǎng)絡(luò)在軟件系統(tǒng)中的應(yīng)用[21].2005年，Chao Liu[22]等人在閉頻繁子圖特征空間上構(gòu)造軟件行為圖樣本集，按照遞增的軟件執(zhí)行順序來(lái)構(gòu)建分類器，通過(guò)尋找分類精度的急劇變化點(diǎn)來(lái)定位軟件錯(cuò)誤.Eichinger[23]等人提出有區(qū)分力的圖挖掘(Discriminative Graph Mining)，在正確和錯(cuò)誤的軟件執(zhí)行路徑集合中發(fā)現(xiàn)軟件bug思想，隨后，在2009年，Hong Cheng等[24]，將圖挖掘算法LEAP[25]應(yīng)用到軟件調(diào)試和錯(cuò)誤定位中.隨后，F(xiàn)rank Eichinger等[26]利用圖描述了執(zhí)行過(guò)程中的方法調(diào)用，基于動(dòng)態(tài)調(diào)用圖進(jìn)行分析，利用圖挖掘方法來(lái)進(jìn)行錯(cuò)誤定位.Giuseppe Di Fatta等[27]基于頻繁模式挖掘算法，提出了一種方法對(duì)軟件系統(tǒng)進(jìn)行錯(cuò)誤定位，對(duì)給定的能被檢測(cè)到的錯(cuò)誤的程序進(jìn)行了大量的測(cè)試用例.執(zhí)行結(jié)果被記錄為函數(shù)調(diào)用樹(shù).測(cè)試結(jié)果分為成功和失敗.頻繁模式挖掘算法被用于在成功和失敗的執(zhí)行中識(shí)別頻繁子樹(shù).這些信息是根據(jù)包含錯(cuò)誤的可能性用于給函數(shù)排序.在錯(cuò)誤分析中，根據(jù)排的順序來(lái)檢查函數(shù).Vandecruys等[28]提出了基于分類技術(shù)AntMiner+的蟻群優(yōu)化算法(ACO)，使用數(shù)據(jù)挖掘技術(shù)來(lái)預(yù)測(cè)軟件錯(cuò)誤模型.Maxwell[29]等人使用圖挖掘算法在調(diào)用堆棧上發(fā)現(xiàn)程序中內(nèi)存泄露問(wèn)題.2011年，Belderrar[30]等人使用子圖挖掘方法識(shí)別在OO軟件演化中軟件類圖的微架構(gòu).2012年，Tekin[31]等人研究了使用頻繁圖挖掘方法尋找頻繁出現(xiàn)的代碼設(shè)計(jì)結(jié)構(gòu)，輔助克隆檢測(cè)和代碼重構(gòu).Frank Eichinger等[32]通過(guò)結(jié)合結(jié)構(gòu)化的和數(shù)值技術(shù)挖掘權(quán)重圖，引入了邊權(quán)重，提出了一種新穎的對(duì)調(diào)用圖進(jìn)行縮減的技術(shù).而且基于圖挖掘和傳統(tǒng)的特征選擇方案對(duì)這種權(quán)重調(diào)用圖提出了一種分析技術(shù).2017年，HongFang Zhou[33]等人從圖聚類的角度挖掘復(fù)雜網(wǎng)絡(luò)社團(tuán)，提出了AR-Cluster聚類算法，在K-Mediods框架的基礎(chǔ)上利用設(shè)計(jì)的節(jié)點(diǎn)相似度計(jì)算方法獲得節(jié)點(diǎn)的社團(tuán).

軟件群體由多個(gè)有關(guān)聯(lián)的軟件組成，多種交互關(guān)系組成了復(fù)雜的交互關(guān)系網(wǎng)絡(luò).多代理軟件系統(tǒng)和本文的軟件群體是一個(gè)比較相似的概念，但軟件群體概念更寬泛，軟件之間的交互類型更廣泛.多代理系統(tǒng)中多個(gè)Agent軟件相互協(xié)調(diào)，相互服務(wù)，共同完成一個(gè)任務(wù)，是一個(gè)任務(wù)型系統(tǒng)，并帶有智能化的屬性[34]，而軟件群體，可以是具有相同類庫(kù)依賴、數(shù)據(jù)交換、開(kāi)發(fā)者關(guān)系等關(guān)系而來(lái).2015年，J.C.Jiang等人提出在多組件軟件系統(tǒng)中，各軟件之間通過(guò)相互引用操作結(jié)果的網(wǎng)絡(luò)模型，通過(guò)組中心分析查找網(wǎng)絡(luò)中有影響力的群組[35]，但此文的研究沒(méi)有從圖聚類，復(fù)雜網(wǎng)絡(luò)圖聚類，社團(tuán)發(fā)現(xiàn)等角度分析，是一個(gè)比較基礎(chǔ)的研究.

通過(guò)以上文獻(xiàn)分析，復(fù)雜網(wǎng)絡(luò)模型只是在單個(gè)軟件中有大量研究，在軟件群體中還沒(méi)很好的研究，本文為了分析軟件群體特征，提高軟件系統(tǒng)維護(hù)效率，進(jìn)行了軟件群體社團(tuán)特征發(fā)現(xiàn)，查找內(nèi)部的關(guān)鍵節(jié)點(diǎn)，提高維護(hù)效率及內(nèi)部穩(wěn)定性.本文的研究思路及創(chuàng)新點(diǎn)如下：首先，從軟件交互關(guān)系的角度研究并定義軟件群體，利用軟件個(gè)體的交互行為建立基于時(shí)間段的復(fù)雜網(wǎng)絡(luò)模型.而后提出一種在復(fù)雜軟件群體網(wǎng)絡(luò)中基于隨機(jī)時(shí)間權(quán)重的挖掘社團(tuán)結(jié)構(gòu)方法構(gòu)建軟件社團(tuán)，得到軟件群體中的關(guān)鍵區(qū)域.每個(gè)關(guān)鍵區(qū)域內(nèi)再利用基于節(jié)點(diǎn)度的中心點(diǎn)挖掘算法查找關(guān)鍵節(jié)點(diǎn).軟件群體中關(guān)鍵節(jié)點(diǎn)的研究給大型軟件系統(tǒng)的維護(hù)展示了一種比較高效的方法，促進(jìn)軟件群體穩(wěn)定平衡發(fā)展.

2 定義及模型

復(fù)雜網(wǎng)絡(luò)理論中，網(wǎng)絡(luò)圖是基本工具，網(wǎng)絡(luò)圖包含節(jié)點(diǎn)、邊和帶權(quán)組成.一般分為有向圖和無(wú)向圖.軟件群體因其具有多個(gè)軟件個(gè)體及軟件交互關(guān)系而可以用網(wǎng)絡(luò)圖的形式表示.

定義1.軟件交互：兩個(gè)軟件之間的類庫(kù)依賴、數(shù)據(jù)交換、相互調(diào)用、數(shù)據(jù)共享等關(guān)系，統(tǒng)稱為軟件之間的交互關(guān)系.

定義2.軟件群體SG：軟件群體是一系列具有交互行為而且可以獨(dú)立運(yùn)行的軟件個(gè)體的集合，表示為SG={S1，S2，S3,…}，其中SG表示軟件群體，Sn(n∈Z+)表示為單個(gè)軟件.

定義3.軟件群體網(wǎng)絡(luò)SG-NetWork：數(shù)學(xué)理論中網(wǎng)絡(luò)用圖來(lái)表示，軟件群體可以用圖抽象描述，若圖中的頂點(diǎn)表示軟件群體中的軟件，圖中的有向邊表示軟件之間的交互，這個(gè)圖稱為SG-NetWork.

定義4.軟件群體網(wǎng)絡(luò)邊權(quán)值列表WL：軟件群體中軟件同時(shí)具有交互和獨(dú)立的特點(diǎn)，因此交互不是每時(shí)每刻存在的，軟件之間產(chǎn)生交互的時(shí)間具有隨機(jī)特性.軟件群體網(wǎng)絡(luò)的邊時(shí)間點(diǎn)列表是一段時(shí)間內(nèi)軟件單向交互時(shí)間點(diǎn)的列表[T0，Tn+1].符號(hào)表示為WTL=[T1，T2，T3…，Tn](n>1，i∈Z+，n∈Z+).邊權(quán)值是時(shí)間點(diǎn)的函數(shù)，對(duì)于邊ei，其邊權(quán)值如公式(1)

(1)

WL是軟件群體網(wǎng)絡(luò)中所有邊權(quán)值的一個(gè)排列，可以表示為WL=[WL，WL，WL…，WL].

若SL={S1，S2，…，Sn}，EL?SL×SL；EL={e1，e2，…，en}，其中ei=，表示Su引用Sv的操作結(jié)果，反之表示為.WTL與WTL表示兩個(gè)相反的邊的時(shí)間列表.若ei的WTL=[T1，T2，T3]，則Su在T1，T2，T3與Sv產(chǎn)生了交互關(guān)系.

SG-NetWork可以表示為三元組{SL，EL，WL}，其中SL={vk}表示節(jié)點(diǎn)的集合，EL={ek}表示由SL中元素?zé)o序?qū)M成的邊的集合，WL表示邊權(quán)重列表的集合，ei表示第i條邊，Si表示第i個(gè)節(jié)點(diǎn)(i∈Z+)，其中i，k∈Z+.

定義5.間接交互與直接交互關(guān)系：SG-NetWork中，S1∈SL，S2∈SL，S3∈SL，若S2調(diào)用了S1的操作結(jié)果，S3又調(diào)用了S2的操作結(jié)果，那么S2與S1存在直接交互關(guān)系，S1與S3存在間接交互關(guān)系.

例1.在大型多軟件系統(tǒng)中，S1是一個(gè)文檔編輯系統(tǒng)，S2是一個(gè)文檔校驗(yàn)系統(tǒng)，則S2對(duì)S1產(chǎn)生的文檔進(jìn)行校驗(yàn)，并把校驗(yàn)結(jié)果返回給S1.S1，S2之間是數(shù)據(jù)交換交互關(guān)系.如若S1是一個(gè)導(dǎo)航系統(tǒng)，S2是一個(gè)管理系統(tǒng)，則S1對(duì)S2進(jìn)行調(diào)用，S2把啟動(dòng)結(jié)果返回S1.S1，S2之間是相互調(diào)用交互關(guān)系.S1與S2單方交互用符號(hào)表示為S1→S2，雙向交互S1?S2.

定義6.子網(wǎng)絡(luò)SG-Child-NetWork：存在兩個(gè)軟件群體網(wǎng)絡(luò)SG-NetWork1=(SL1，EL1，WL1)和SG-NetWork2=(SL2，EL2，WL2)，若SL1是SL2的子集，EL1是EL2的子集，且EL1中的邊僅與SL1中的頂點(diǎn)相關(guān)聯(lián)，則SG-NetWork1是SG-NetWork2的子網(wǎng)絡(luò)SG-Child-NetWork.

連接節(jié)點(diǎn)的邊的條數(shù)表示為網(wǎng)絡(luò)節(jié)點(diǎn)的度，根據(jù)邊的方向，度又分為出度和入度，分別表示為O-degree，C-degree，軟件群體網(wǎng)絡(luò)節(jié)點(diǎn)的度表示為：

OC-degree[vk]=O-degree[vk]+C-degree[vk]，k∈Z+

(2)

圖1 軟件群體交互模型示例圖Fig.1 A sample graph of software group interaction

例2.圖1展示了一個(gè)軟件群體的一部分.圖中有節(jié)點(diǎn)S1，S2，S3，S4，S5，S6，S7，S5，S9，S10，S6與S4具有雙向交互關(guān)系.各條邊的WTL及計(jì)算得出的WL如表1所示.

定義7.節(jié)點(diǎn)之間的帶權(quán)距離E-wdis：SG-NetWork中，S1，S2∈SL，S1到達(dá)S2的最短路徑short-path含有的邊的條數(shù)表示為S1與S2之間的距離E-dis.節(jié)點(diǎn)S1到達(dá)S2的帶權(quán)距離E-wdis是包含所有邊的帶權(quán)之和.若short-path=，邊，的帶權(quán)之和表示為邊帶權(quán)距離E-wdis.任意兩個(gè)節(jié)點(diǎn)Sm，Sn(m>n，m∈Z+，n∈Z+)的帶權(quán)距離公式表示為：

(3)

若S1→S2不可達(dá)，則二者之間的距離為無(wú)窮大.

定義8.軟件群體社團(tuán)結(jié)構(gòu)SG-Group：在SG-Child-NetWork中，若任意兩個(gè)節(jié)點(diǎn)都存在直接交互關(guān)系或間接交互關(guān)系或平行關(guān)系，這樣的SG-Child-NetWork稱為SG-Group.

定義9.軟件群體社團(tuán)支持度SG-Group-Support：軟件群體社團(tuán)支持度是SG-Group中節(jié)點(diǎn)個(gè)數(shù)的閾值.若軟件群體社團(tuán)SG中的節(jié)點(diǎn)個(gè)數(shù)NodeNum>SG-Group-Support，則稱SG為節(jié)點(diǎn)個(gè)數(shù)達(dá)到要求的社團(tuán)結(jié)構(gòu).

定義10.軟件群體社團(tuán)結(jié)構(gòu)關(guān)鍵節(jié)點(diǎn)SG-kP：SG-NetWork可以由多個(gè)社團(tuán)組成.若給定一個(gè)用戶自定義個(gè)數(shù)k，若OC-degree[V1]，OC-degree[V2]， …，OC-degree[Vk]為最大的k個(gè)節(jié)點(diǎn)的度，則稱V1，V2，…，Vk為關(guān)鍵節(jié)點(diǎn).若OC-degree[Vk]最大，Vk稱為社團(tuán)結(jié)構(gòu)的中心點(diǎn).

例3.圖1中S6的O-degree和C-degree分別為1和3，其OC-degree=4大于其他節(jié)點(diǎn)，是社團(tuán)結(jié)構(gòu)的中心點(diǎn).

定義11.軟件群體穩(wěn)定性系數(shù)SG-Sdegree：SG-NetWork中，任意節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的最短距離總和稱為軟件群體穩(wěn)定性系數(shù)，并且總和越小，軟件群體相對(duì)越穩(wěn)定.

表1 軟件群體網(wǎng)絡(luò)邊時(shí)間列表與帶權(quán)Table 1 Edge time list and weight in Software group network

定義12.軟件群體網(wǎng)絡(luò)邊介數(shù)E-degree：參見(jiàn)文獻(xiàn)[17]，SG-NetWork中，經(jīng)過(guò)邊ei(i∈Z+)的所有最短路徑的條數(shù)，表示為E-degre.

定義13.軟件群體網(wǎng)絡(luò)帶權(quán)邊介數(shù)E-wdegree：SG-NetWork中，邊ei的帶權(quán)邊介數(shù)是經(jīng)過(guò)邊ei的所有最短路徑的條數(shù)E-degree與邊權(quán)值WL的乘積，表示為：

E-wdegree=E-degre×WL，i∈Z+

(4)

圖2 穩(wěn)定網(wǎng)絡(luò)挖掘模型構(gòu)建Fig.2 Modeling and mining processes

定義14.軟件群體網(wǎng)絡(luò)邊介數(shù)支持度E-wdegree-support：軟件群體網(wǎng)絡(luò)邊介數(shù)支持度是加權(quán)邊介數(shù)大小的閾值，若E-wdegree>E-wdegree-support，則邊ei是帶權(quán)邊介數(shù)達(dá)到要求的邊.

3 算法

3.1 挖掘模型構(gòu)建

文章第2部分給出了軟件群體網(wǎng)絡(luò)模型的定義，利用軟件群體中的軟件及其交互關(guān)系組成軟件群體網(wǎng)絡(luò)圖，其中軟件是節(jié)點(diǎn)，軟件之間的交互看成邊，構(gòu)建群體交互模型.然后，利用3.2中的SG-GroupMining算法挖掘網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)，發(fā)現(xiàn)網(wǎng)絡(luò)中關(guān)鍵模塊.第三，利用3.3中社團(tuán)結(jié)構(gòu)中心點(diǎn)算法SG-CPMining查找每個(gè)社團(tuán)的關(guān)鍵點(diǎn).關(guān)鍵點(diǎn)代表了軟件群體關(guān)鍵模塊中交互關(guān)系發(fā)生頻繁的軟件，是維護(hù)軟件群體穩(wěn)定性的重點(diǎn)考慮對(duì)象.最后把社團(tuán)之間交互轉(zhuǎn)移到關(guān)鍵節(jié)點(diǎn)之間，組建穩(wěn)定的網(wǎng)絡(luò).模型流程圖如圖2所示.

3.2 軟件群體社團(tuán)發(fā)現(xiàn)算法

在軟件群體網(wǎng)絡(luò)中，發(fā)現(xiàn)社團(tuán)結(jié)構(gòu)，是分析軟件交互關(guān)系及結(jié)構(gòu)的重要途徑.其主要思想是這樣的：(1)設(shè)定帶權(quán)邊介數(shù)閾值Se-degree(2)在SG-NetWork中，計(jì)算出所有邊的帶權(quán)邊介數(shù)，刪除具有最大帶權(quán)邊介數(shù)的邊，組成新的SG-NetWork；(3)循環(huán)操作第(2)步，直到最大邊介數(shù)小于Se-degree為止；具體參見(jiàn)算法1.

算法1.SG-GroupMining算法

輸入：軟件群體網(wǎng)絡(luò)SG-NetWork，邊介數(shù)閾值Se-degree，社團(tuán)閾值SG-Group-Support

輸出：軟件群體網(wǎng)絡(luò)SG中的社團(tuán)SG-Group

1 初始化邊集合列表EL=[e1，e2，…，en]，節(jié)點(diǎn)的集合列表SL=[S1，S2，…，Sn]，帶權(quán)邊介數(shù)列表E-wdegree={}，邊介數(shù)臨時(shí)變量e-degree，最大邊介數(shù)be-degree；

2 While(be-degree

3 For each ei in EL，do

4 Compute E-wdegree，E-wdegree.add(E-wdegree)

5 If E-wdegree> e-degree，then

6 e-degree= E-wdegree，

7 End if

8 End for

9 Delete theei，whoseE-degree=e-degree

10be-degree=e-degree

11 End while

12 OutputSG-Group

13 For eachSG-Groupin theSG-NetWork，do

14 If the node number m>SG-Group-Support

15 Output SG-Group in the SG-NetWork

16 End If

17 End for

算法第1行初始化變量及輸入基本數(shù)據(jù)，算法第2-11行是產(chǎn)生社團(tuán)結(jié)構(gòu)的關(guān)鍵代碼，其中3-8行分別計(jì)算各個(gè)節(jié)點(diǎn)的帶權(quán)邊介數(shù)，并求出最大帶權(quán)邊介數(shù)，刪除具有最大邊介數(shù)的節(jié)點(diǎn).進(jìn)行循環(huán)執(zhí)行，直到滿足最大帶權(quán)邊介數(shù)小于給定的邊介數(shù)閾值為止.第13行輸出社團(tuán)結(jié)構(gòu)，第14-17行遍歷所有的社團(tuán)結(jié)構(gòu)，輸出滿足節(jié)點(diǎn)個(gè)數(shù)的社團(tuán).

例4.在圖1和表1中，假設(shè)邊介數(shù)閾值為Se-degree=0.7，SG-Group-Support=4，執(zhí)行算法1，實(shí)例過(guò)程如下：

1)遍歷各個(gè)節(jié)點(diǎn)，求出所有的最短路徑如表2所示.

2)計(jì)算各條邊帶權(quán)邊介數(shù)，詳細(xì)如表3所示.

3)找出具有帶權(quán)邊介數(shù)小于閾值Se-degree的邊，，E-wdegree

4)重復(fù)以上1)-3)步驟，發(fā)現(xiàn)沒(méi)有邊可以刪除，得到兩個(gè)社團(tuán)結(jié)構(gòu)，見(jiàn)圖3與圖4.

表2 節(jié)點(diǎn)最短路徑表Table 2 Table of the shortest paths of nodes

表3 邊帶權(quán)介數(shù)表

5) 由于SG-Group-Support=4，得出社團(tuán)結(jié)構(gòu)1的節(jié)點(diǎn)數(shù)為5>SG-Group-Support，算法最終得到一個(gè)社團(tuán)結(jié)構(gòu)見(jiàn)圖3.

3.3 社團(tuán)結(jié)構(gòu)中心點(diǎn)算法

通過(guò)算法1發(fā)現(xiàn)了SG-NetWork的多個(gè)社團(tuán)，也即是SG-NetWork中的關(guān)鍵模塊.在關(guān)鍵模塊中發(fā)現(xiàn)關(guān)鍵節(jié)點(diǎn)，關(guān)鍵點(diǎn)代表了模塊中的中心，是維持模塊穩(wěn)定性的關(guān)鍵部分.發(fā)現(xiàn)模

圖3 分裂的社團(tuán)結(jié)構(gòu)1 Fig.3 Divided community structure 1 圖4 分裂的社團(tuán)結(jié)構(gòu)2Fig.4 Divided community structure 2

塊中的關(guān)鍵點(diǎn)的過(guò)程是這樣的：對(duì)于任意模塊，分別計(jì)算節(jié)點(diǎn)的OC-degree，其中OC-degree最大者就是社團(tuán)的關(guān)鍵點(diǎn)；具體流程如算法2.

算法2.SG-CPMining算法

輸入：軟件社團(tuán)結(jié)構(gòu)SG-Group，關(guān)鍵節(jié)點(diǎn)的個(gè)數(shù)k

輸出：SG-Group中k個(gè)關(guān)鍵點(diǎn)SG-kP

1 初始化邊集合列表EL=[e1，e2，…，en]，節(jié)點(diǎn)的集合列表SL=[S1，S2，…，Sn]，節(jié)點(diǎn)的度列表OCL=[]；

2 For eacheiinEL，do

3OC-degreei=O-degreei+C-degreei

4OCL.add(ei，OC-degreei)

5 End for

6 Sort(OCL)

7 Output topkSG-kP

算法第1行是初始化數(shù)據(jù)，第2-4行是循環(huán)計(jì)算所有節(jié)點(diǎn)的度，第6行是進(jìn)行所有節(jié)點(diǎn)度的降序排列，并輸入具有最大節(jié)點(diǎn)度的前k個(gè)節(jié)點(diǎn).

例5.圖1和表1組成的軟件群體網(wǎng)絡(luò)模型通過(guò)算法1得出了兩個(gè)社團(tuán)結(jié)構(gòu)如圖3及圖4，繼續(xù)用算法2求出社團(tuán)的關(guān)鍵節(jié)點(diǎn)如表4所示.

表4 社團(tuán)中節(jié)點(diǎn)度列表

從表中不難得出，SG-Group1，SG-Group2中的關(guān)鍵節(jié)點(diǎn)分別為S4與S5.

3.4 算法討論

本文的算法從軟件交互的角度出發(fā)，可以得到多個(gè)軟件之間是否具有緊密的聯(lián)系，通過(guò)社團(tuán)中心點(diǎn)發(fā)現(xiàn)算法可以得到多個(gè)軟件中的比較關(guān)鍵的軟件個(gè)體.然而以前的對(duì)軟件社團(tuán)結(jié)構(gòu)的發(fā)現(xiàn)，都是從軟件源碼的角度對(duì)單個(gè)軟件處理，發(fā)現(xiàn)單個(gè)軟件內(nèi)的關(guān)鍵函數(shù).和本文算法相比，本文是從宏觀的角度研究了軟件之間的關(guān)系，而現(xiàn)有的算法從微觀的角度研究單個(gè)軟件內(nèi)部的類及函數(shù)之間的關(guān)系.

4 仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)來(lái)源

為了滿足用戶多方面的需要，多個(gè)軟件往往需要集成起來(lái)，集成后的軟件具有交互關(guān)系，軟件之間的調(diào)用的時(shí)間具有隨機(jī)特征.仿真實(shí)驗(yàn)的數(shù)據(jù)來(lái)源是這樣的，在特定的時(shí)間段內(nèi)，用900個(gè)軟件節(jié)點(diǎn)產(chǎn)生與收集調(diào)用關(guān)系及隨機(jī)時(shí)間戳.保證了數(shù)據(jù)的一般性.實(shí)驗(yàn)在Windows 10操作系統(tǒng)，CPU E5200 @2.5GHz下用java語(yǔ)言實(shí)現(xiàn).

4.2 算法性能分析

文中與算法相關(guān)的參數(shù)有：軟件群體網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)據(jù)量，軟件群體內(nèi)軟件之間的調(diào)用次數(shù)，社團(tuán)內(nèi)節(jié)點(diǎn)數(shù)支持度，帶權(quán)邊介數(shù)支持度.為了體現(xiàn)實(shí)驗(yàn)結(jié)果的準(zhǔn)確性，每次執(zhí)行算法都采取隨機(jī)產(chǎn)生的數(shù)據(jù).由于本文算法基于邊介數(shù)的社團(tuán)發(fā)現(xiàn)GN算法[17]，因此把GN算法作為SG-GroupMining算法的對(duì)比算法.

圖5中，帶權(quán)邊介數(shù)支持度0.8，社團(tuán)內(nèi)節(jié)點(diǎn)支持度為5，調(diào)用次數(shù)為300，節(jié)點(diǎn)數(shù)從500到900之間變化.圖中看出GN算法[17]，SG-GroupMining算法，SG-CPMining算法隨節(jié)點(diǎn)量變大，消耗時(shí)間為增長(zhǎng)趨勢(shì)，GN算法時(shí)間消耗明顯較高，SG-GroupMining算法，SG-CPMining算法時(shí)間消耗比較穩(wěn)定.圖6中，節(jié)點(diǎn)數(shù)為900，帶權(quán)邊介數(shù)支持度0.8，社團(tuán)內(nèi)節(jié)點(diǎn)支持度為5，調(diào)用次數(shù)從350到450之間變化，產(chǎn)生的算法執(zhí)行時(shí)間變化規(guī)律與圖5類似.圖7中，社團(tuán)節(jié)點(diǎn)數(shù)支持度從3到7之間變化，節(jié)點(diǎn)數(shù)為600，調(diào)用次數(shù)為300，帶權(quán)邊介數(shù)為0.8，隨著社團(tuán)節(jié)點(diǎn)數(shù)支持度的變大，GN算法執(zhí)行時(shí)間有先上升最高點(diǎn)后逐漸下降的趨勢(shì)，SG-GroupMining算法，SG-CPMining算法則比較平穩(wěn).圖8中，帶權(quán)邊介數(shù)從0.8到0.96間變化，節(jié)點(diǎn)數(shù)，調(diào)用次數(shù)與社團(tuán)節(jié)點(diǎn)數(shù)支持度都同圖7，從圖中看出隨著帶權(quán)邊介數(shù)的變大，SG-GroupMining算法，SG-CPMining算法執(zhí)行時(shí)間都有上升趨勢(shì)，GN算法執(zhí)行時(shí)間有先上升最高點(diǎn)后逐漸下降的趨勢(shì).

從圖5到8可以看出，SG-GroupMining算法，SG-CPMining算法較GN算法有較好的時(shí)間特性，GN算法在大數(shù)據(jù)量下消耗時(shí)間越來(lái)越多，也證實(shí)了其本身復(fù)雜度高的缺點(diǎn).本文的算法時(shí)間引入了社團(tuán)節(jié)點(diǎn)數(shù)支持度與帶權(quán)邊介數(shù)支持度，產(chǎn)生的時(shí)間消耗較為平穩(wěn)，算法在數(shù)據(jù)量，社團(tuán)節(jié)點(diǎn)數(shù)支持度，帶權(quán)邊介數(shù)上都有較好的可擴(kuò)展性.

圖5 節(jié)點(diǎn)量與算法執(zhí)行時(shí)間的關(guān)系Fig.5 Relationship of node amount and time圖6 調(diào)用次數(shù)與執(zhí)行時(shí)間的關(guān)系Fig.6 Relationship of call number and time圖7 社團(tuán)支持度與算法執(zhí)行時(shí)間的關(guān)系Fig.7 Relationship of SG-Group-Support and time圖8 帶權(quán)邊介數(shù)支持度與執(zhí)行時(shí)間的關(guān)系Fig.8 Relationship of Se-degree and time

圖9 節(jié)點(diǎn)量與算法執(zhí)行結(jié)果的關(guān)系Fig.9 Relationship of node amount and results of algorithm圖10 調(diào)用次數(shù)與算法執(zhí)行結(jié)果的關(guān)系Fig.10 Relationship of call number and results of algorithm圖11 社團(tuán)支持度與算法執(zhí)行結(jié)果的關(guān)系Fig.11 Relationship of SG-Group-Support and results of algorithm圖12 帶權(quán)邊介數(shù)支持度與執(zhí)行結(jié)果的關(guān)系Fig.12 Relationship of Se-degree and results of algorithm

圖9與圖5有相同的節(jié)點(diǎn)數(shù)，調(diào)用次數(shù)，社團(tuán)節(jié)點(diǎn)數(shù)與帶權(quán)邊介數(shù)支持度，且圖10同圖6，圖11同圖7，圖12同8有相同的數(shù)據(jù)量與參數(shù).從圖中可以看出，SG-GroupMining算法，SG-CPMining算法得出了較少的挖掘結(jié)果，這樣就有利于軟件群體中對(duì)個(gè)別比較重要的軟件進(jìn)行特殊維護(hù)，體現(xiàn)了挖掘結(jié)果的精煉.圖9及圖10中隨數(shù)據(jù)量變化，挖掘結(jié)果只有稍微的變化，這是算法中采用社團(tuán)數(shù)支持度與邊介數(shù)支持度的結(jié)果.圖11中，隨社團(tuán)節(jié)點(diǎn)支持度的增加，挖掘結(jié)果有減少趨勢(shì)，圖12隨帶權(quán)邊介數(shù)的增加，挖掘結(jié)果數(shù)有上升趨勢(shì)，體現(xiàn)了支持度對(duì)挖掘結(jié)果的篩選作用.

文章中算法得出的關(guān)鍵節(jié)點(diǎn)考慮了軟件群體網(wǎng)絡(luò)中軟件之間調(diào)用的時(shí)間權(quán)值，選出了重要程度較高的邊，劃分的社團(tuán)具有更高的興趣度特性.關(guān)鍵節(jié)點(diǎn)是在劃分的社團(tuán)中產(chǎn)生的，而不是在網(wǎng)絡(luò)中直接查找，這樣避免了關(guān)鍵點(diǎn)的扎堆現(xiàn)象，可以找到空間范圍更廣的關(guān)鍵節(jié)點(diǎn)，體現(xiàn)挖掘結(jié)果的整體兼顧性.

5 結(jié) 論

軟件群體中的關(guān)鍵軟件對(duì)提高軟件群體維護(hù)效率至關(guān)重要.本文從軟件群體交互的角度提出了一種復(fù)雜軟件群體網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)挖掘算法SG-CPMining.首先，定義了軟件群體，利用軟件群體中軟件與軟件之間基于數(shù)據(jù)交換，數(shù)據(jù)共享，互相調(diào)用的信息流構(gòu)建了基于隨機(jī)時(shí)間權(quán)值的復(fù)雜軟件群體網(wǎng)絡(luò)模型及軟件交互模型.其次，在軟件交互模型的基礎(chǔ)上，提出了一種復(fù)雜軟件群體網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)發(fā)現(xiàn)算法SG-GroupMining.第三，在發(fā)現(xiàn)的社團(tuán)結(jié)構(gòu)中提出了一種基于節(jié)點(diǎn)度的關(guān)鍵節(jié)點(diǎn)發(fā)現(xiàn)算法.最后，實(shí)驗(yàn)仿真，驗(yàn)證了交互模型的可行性，高效的挖掘出了軟件群體中的關(guān)鍵節(jié)點(diǎn).