復雜軟件群體網絡社團中關鍵節點挖掘算法

李維娜，任家東

1(燕山大學 信息科學與工程學院，河北 秦皇島 066004)2(河北省計算機虛擬技術與系統集成重點實驗室，河北 秦皇島 066004)3(河北省軟件工程重點實驗室，河北 秦皇島 066004)

1 引 言

大型軟件系統往往由很多獨立的軟件個體組成，這些軟件個體之間因具有可以獨立運行，同時又相互交互的特點，而區別于軟件模塊[1].開源軟件及云服務的出現促進了這樣的大型軟件系統的產生與發展[2，3].軟件之間的交互結構形成了軟件關系網絡，網絡的穩定、平衡、和諧的存在是企事業單位穩健發展的關鍵.復雜網絡很好描述了自然科學，社會科學，管理科學及工程技術領域的具有交互關系的復雜模型，復雜網絡社團結構及數據挖掘聚類算法的大量的研究成果，已經應用于電網，社交網絡，生物醫學網絡，交通網絡，軟件結構，并逐見成效[4，6].基于復雜網絡及數據挖掘的方法來尋求高效及低成本的軟件維護解決方案，成為熱門的研究思路[7].

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

大量的學者在單個軟件中，通過從源代碼的角度用靜態及動態方式對軟件結構特性進行了研究.2002年Valverde等[12]使用無向網絡表示軟件的系統結構，即用網絡模型中的節點來表示類，而邊用來表示類與類之間的關聯、繼承等關系，分析軟件系統的拓撲結構，給出小世界、無標度的結構特性.2003年Myers和Moura等[13，14]進一步對軟件的系統結構用有向網絡來進行表示，并對大量開源軟件進行了分析，也發現了同樣的特性.近幾年，國內外的相關工作已經通過建立軟件網絡模型，揭示軟件網絡的一些普遍的拓撲特征.2009年，Cai等[15]根據軟件的動態執行過程提出了鏡像進化圖，并對平均路徑、聚類系數等拓撲度量重新進行了定義，發現存在于軟件執行網絡中的“小世界”現象在軟件的動態執行過程中消失了，且體現“無標度”特性的冪率分布中也出現了分段現象.2012年，Ma等[16]將一個軟件包映射為一個復雜網絡，其中函數作為節點，函數間依賴關系作為邊，以此而構建的復雜軟件網絡模型能很好地反應真實世界中軟件包的特性，并提出一種新的符合軟件開發的網絡增長模式，為今后研究軟件網絡特性提供了一種新的觀點.

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

軟件群體由多個有關聯的軟件組成，多種交互關系組成了復雜的交互關系網絡.多代理軟件系統和本文的軟件群體是一個比較相似的概念，但軟件群體概念更寬泛，軟件之間的交互類型更廣泛.多代理系統中多個Agent軟件相互協調，相互服務，共同完成一個任務，是一個任務型系統，并帶有智能化的屬性[34]，而軟件群體，可以是具有相同類庫依賴、數據交換、開發者關系等關系而來.2015年，J.C.Jiang等人提出在多組件軟件系統中，各軟件之間通過相互引用操作結果的網絡模型，通過組中心分析查找網絡中有影響力的群組[35]，但此文的研究沒有從圖聚類，復雜網絡圖聚類，社團發現等角度分析，是一個比較基礎的研究.

通過以上文獻分析，復雜網絡模型只是在單個軟件中有大量研究，在軟件群體中還沒很好的研究，本文為了分析軟件群體特征，提高軟件系統維護效率，進行了軟件群體社團特征發現，查找內部的關鍵節點，提高維護效率及內部穩定性.本文的研究思路及創新點如下：首先，從軟件交互關系的角度研究并定義軟件群體，利用軟件個體的交互行為建立基于時間段的復雜網絡模型.而后提出一種在復雜軟件群體網絡中基于隨機時間權重的挖掘社團結構方法構建軟件社團，得到軟件群體中的關鍵區域.每個關鍵區域內再利用基于節點度的中心點挖掘算法查找關鍵節點.軟件群體中關鍵節點的研究給大型軟件系統的維護展示了一種比較高效的方法，促進軟件群體穩定平衡發展.

2 定義及模型

復雜網絡理論中，網絡圖是基本工具，網絡圖包含節點、邊和帶權組成.一般分為有向圖和無向圖.軟件群體因其具有多個軟件個體及軟件交互關系而可以用網絡圖的形式表示.

定義1.軟件交互：兩個軟件之間的類庫依賴、數據交換、相互調用、數據共享等關系，統稱為軟件之間的交互關系.

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

定義3.軟件群體網絡SG-NetWork：數學理論中網絡用圖來表示，軟件群體可以用圖抽象描述，若圖中的頂點表示軟件群體中的軟件，圖中的有向邊表示軟件之間的交互，這個圖稱為SG-NetWork.

定義4.軟件群體網絡邊權值列表WL：軟件群體中軟件同時具有交互和獨立的特點，因此交互不是每時每刻存在的，軟件之間產生交互的時間具有隨機特性.軟件群體網絡的邊時間點列表是一段時間內軟件單向交互時間點的列表[T0，Tn+1].符號表示為WTL=[T1，T2，T3…，Tn](n>1，i∈Z+，n∈Z+).邊權值是時間點的函數，對于邊ei，其邊權值如公式(1)

(1)

WL是軟件群體網絡中所有邊權值的一個排列，可以表示為WL=[WL，WL，WL…，WL].

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

SG-NetWork可以表示為三元組{SL，EL，WL}，其中SL={vk}表示節點的集合，EL={ek}表示由SL中元素無序對組成的邊的集合，WL表示邊權重列表的集合，ei表示第i條邊，Si表示第i個節點(i∈Z+)，其中i，k∈Z+.

定義5.間接交互與直接交互關系：SG-NetWork中，S1∈SL，S2∈SL，S3∈SL，若S2調用了S1的操作結果，S3又調用了S2的操作結果，那么S2與S1存在直接交互關系，S1與S3存在間接交互關系.

例1.在大型多軟件系統中，S1是一個文檔編輯系統，S2是一個文檔校驗系統，則S2對S1產生的文檔進行校驗，并把校驗結果返回給S1.S1，S2之間是數據交換交互關系.如若S1是一個導航系統，S2是一個管理系統，則S1對S2進行調用，S2把啟動結果返回S1.S1，S2之間是相互調用交互關系.S1與S2單方交互用符號表示為S1→S2，雙向交互S1?S2.

定義6.子網絡SG-Child-NetWork：存在兩個軟件群體網絡SG-NetWork1=(SL1，EL1，WL1)和SG-NetWork2=(SL2，EL2，WL2)，若SL1是SL2的子集，EL1是EL2的子集，且EL1中的邊僅與SL1中的頂點相關聯，則SG-NetWork1是SG-NetWork2的子網絡SG-Child-NetWork.

連接節點的邊的條數表示為網絡節點的度，根據邊的方向，度又分為出度和入度，分別表示為O-degree，C-degree，軟件群體網絡節點的度表示為：

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

(2)

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

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

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

(3)

若S1→S2不可達，則二者之間的距離為無窮大.

定義8.軟件群體社團結構SG-Group：在SG-Child-NetWork中，若任意兩個節點都存在直接交互關系或間接交互關系或平行關系，這樣的SG-Child-NetWork稱為SG-Group.

定義9.軟件群體社團支持度SG-Group-Support：軟件群體社團支持度是SG-Group中節點個數的閾值.若軟件群體社團SG中的節點個數NodeNum>SG-Group-Support，則稱SG為節點個數達到要求的社團結構.

定義10.軟件群體社團結構關鍵節點SG-kP：SG-NetWork可以由多個社團組成.若給定一個用戶自定義個數k，若OC-degree[V1]，OC-degree[V2]， …，OC-degree[Vk]為最大的k個節點的度，則稱V1，V2，…，Vk為關鍵節點.若OC-degree[Vk]最大，Vk稱為社團結構的中心點.

例3.圖1中S6的O-degree和C-degree分別為1和3，其OC-degree=4大于其他節點，是社團結構的中心點.

定義11.軟件群體穩定性系數SG-Sdegree：SG-NetWork中，任意節點到達其他節點的最短距離總和稱為軟件群體穩定性系數，并且總和越小，軟件群體相對越穩定.

表1 軟件群體網絡邊時間列表與帶權Table 1 Edge time list and weight in Software group network

定義12.軟件群體網絡邊介數E-degree：參見文獻[17]，SG-NetWork中，經過邊ei(i∈Z+)的所有最短路徑的條數，表示為E-degre.

定義13.軟件群體網絡帶權邊介數E-wdegree：SG-NetWork中，邊ei的帶權邊介數是經過邊ei的所有最短路徑的條數E-degree與邊權值WL的乘積，表示為：

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

(4)

圖2 穩定網絡挖掘模型構建Fig.2 Modeling and mining processes

定義14.軟件群體網絡邊介數支持度E-wdegree-support：軟件群體網絡邊介數支持度是加權邊介數大小的閾值，若E-wdegree>E-wdegree-support，則邊ei是帶權邊介數達到要求的邊.

3 算法

3.1 挖掘模型構建

文章第2部分給出了軟件群體網絡模型的定義，利用軟件群體中的軟件及其交互關系組成軟件群體網絡圖，其中軟件是節點，軟件之間的交互看成邊，構建群體交互模型.然后，利用3.2中的SG-GroupMining算法挖掘網絡中的社團結構，發現網絡中關鍵模塊.第三，利用3.3中社團結構中心點算法SG-CPMining查找每個社團的關鍵點.關鍵點代表了軟件群體關鍵模塊中交互關系發生頻繁的軟件，是維護軟件群體穩定性的重點考慮對象.最后把社團之間交互轉移到關鍵節點之間，組建穩定的網絡.模型流程圖如圖2所示.

3.2 軟件群體社團發現算法

在軟件群體網絡中，發現社團結構，是分析軟件交互關系及結構的重要途徑.其主要思想是這樣的：(1)設定帶權邊介數閾值Se-degree(2)在SG-NetWork中，計算出所有邊的帶權邊介數，刪除具有最大帶權邊介數的邊，組成新的SG-NetWork；(3)循環操作第(2)步，直到最大邊介數小于Se-degree為止；具體參見算法1.

算法1.SG-GroupMining算法

輸入：軟件群體網絡SG-NetWork，邊介數閾值Se-degree，社團閾值SG-Group-Support

輸出：軟件群體網絡SG中的社團SG-Group

1 初始化邊集合列表EL=[e1，e2，…，en]，節點的集合列表SL=[S1，S2，…，Sn]，帶權邊介數列表E-wdegree={}，邊介數臨時變量e-degree，最大邊介數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行初始化變量及輸入基本數據，算法第2-11行是產生社團結構的關鍵代碼，其中3-8行分別計算各個節點的帶權邊介數，并求出最大帶權邊介數，刪除具有最大邊介數的節點.進行循環執行，直到滿足最大帶權邊介數小于給定的邊介數閾值為止.第13行輸出社團結構，第14-17行遍歷所有的社團結構，輸出滿足節點個數的社團.

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

1)遍歷各個節點，求出所有的最短路徑如表2所示.

2)計算各條邊帶權邊介數，詳細如表3所示.

3)找出具有帶權邊介數小于閾值Se-degree的邊，，E-wdegree

4)重復以上1)-3)步驟，發現沒有邊可以刪除，得到兩個社團結構，見圖3與圖4.

表2 節點最短路徑表Table 2 Table of the shortest paths of nodes

表3 邊帶權介數表

5) 由于SG-Group-Support=4，得出社團結構1的節點數為5>SG-Group-Support，算法最終得到一個社團結構見圖3.

3.3 社團結構中心點算法

通過算法1發現了SG-NetWork的多個社團，也即是SG-NetWork中的關鍵模塊.在關鍵模塊中發現關鍵節點，關鍵點代表了模塊中的中心，是維持模塊穩定性的關鍵部分.發現模

圖3 分裂的社團結構1 Fig.3 Divided community structure 1 圖4 分裂的社團結構2Fig.4 Divided community structure 2

塊中的關鍵點的過程是這樣的：對于任意模塊，分別計算節點的OC-degree，其中OC-degree最大者就是社團的關鍵點；具體流程如算法2.

算法2.SG-CPMining算法

輸入：軟件社團結構SG-Group，關鍵節點的個數k

輸出：SG-Group中k個關鍵點SG-kP

1 初始化邊集合列表EL=[e1，e2，…，en]，節點的集合列表SL=[S1，S2，…，Sn]，節點的度列表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行是初始化數據，第2-4行是循環計算所有節點的度，第6行是進行所有節點度的降序排列，并輸入具有最大節點度的前k個節點.

例5.圖1和表1組成的軟件群體網絡模型通過算法1得出了兩個社團結構如圖3及圖4，繼續用算法2求出社團的關鍵節點如表4所示.

表4 社團中節點度列表

從表中不難得出，SG-Group1，SG-Group2中的關鍵節點分別為S4與S5.

3.4 算法討論

本文的算法從軟件交互的角度出發，可以得到多個軟件之間是否具有緊密的聯系，通過社團中心點發現算法可以得到多個軟件中的比較關鍵的軟件個體.然而以前的對軟件社團結構的發現，都是從軟件源碼的角度對單個軟件處理，發現單個軟件內的關鍵函數.和本文算法相比，本文是從宏觀的角度研究了軟件之間的關系，而現有的算法從微觀的角度研究單個軟件內部的類及函數之間的關系.

4 仿真實驗

4.1 實驗環境與數據來源

為了滿足用戶多方面的需要，多個軟件往往需要集成起來，集成后的軟件具有交互關系，軟件之間的調用的時間具有隨機特征.仿真實驗的數據來源是這樣的，在特定的時間段內，用900個軟件節點產生與收集調用關系及隨機時間戳.保證了數據的一般性.實驗在Windows 10操作系統，CPU E5200 @2.5GHz下用java語言實現.

4.2 算法性能分析

文中與算法相關的參數有：軟件群體網絡節點的數據量，軟件群體內軟件之間的調用次數，社團內節點數支持度，帶權邊介數支持度.為了體現實驗結果的準確性，每次執行算法都采取隨機產生的數據.由于本文算法基于邊介數的社團發現GN算法[17]，因此把GN算法作為SG-GroupMining算法的對比算法.

圖5中，帶權邊介數支持度0.8，社團內節點支持度為5，調用次數為300，節點數從500到900之間變化.圖中看出GN算法[17]，SG-GroupMining算法，SG-CPMining算法隨節點量變大，消耗時間為增長趨勢，GN算法時間消耗明顯較高，SG-GroupMining算法，SG-CPMining算法時間消耗比較穩定.圖6中，節點數為900，帶權邊介數支持度0.8，社團內節點支持度為5，調用次數從350到450之間變化，產生的算法執行時間變化規律與圖5類似.圖7中，社團節點數支持度從3到7之間變化，節點數為600，調用次數為300，帶權邊介數為0.8，隨著社團節點數支持度的變大，GN算法執行時間有先上升最高點后逐漸下降的趨勢，SG-GroupMining算法，SG-CPMining算法則比較平穩.圖8中，帶權邊介數從0.8到0.96間變化，節點數，調用次數與社團節點數支持度都同圖7，從圖中看出隨著帶權邊介數的變大，SG-GroupMining算法，SG-CPMining算法執行時間都有上升趨勢，GN算法執行時間有先上升最高點后逐漸下降的趨勢.

從圖5到8可以看出，SG-GroupMining算法，SG-CPMining算法較GN算法有較好的時間特性，GN算法在大數據量下消耗時間越來越多，也證實了其本身復雜度高的缺點.本文的算法時間引入了社團節點數支持度與帶權邊介數支持度，產生的時間消耗較為平穩，算法在數據量，社團節點數支持度，帶權邊介數上都有較好的可擴展性.

圖5 節點量與算法執行時間的關系Fig.5 Relationship of node amount and time圖6 調用次數與執行時間的關系Fig.6 Relationship of call number and time圖7 社團支持度與算法執行時間的關系Fig.7 Relationship of SG-Group-Support and time圖8 帶權邊介數支持度與執行時間的關系Fig.8 Relationship of Se-degree and time

圖9 節點量與算法執行結果的關系Fig.9 Relationship of node amount and results of algorithm圖10 調用次數與算法執行結果的關系Fig.10 Relationship of call number and results of algorithm圖11 社團支持度與算法執行結果的關系Fig.11 Relationship of SG-Group-Support and results of algorithm圖12 帶權邊介數支持度與執行結果的關系Fig.12 Relationship of Se-degree and results of algorithm

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

文章中算法得出的關鍵節點考慮了軟件群體網絡中軟件之間調用的時間權值，選出了重要程度較高的邊，劃分的社團具有更高的興趣度特性.關鍵節點是在劃分的社團中產生的，而不是在網絡中直接查找，這樣避免了關鍵點的扎堆現象，可以找到空間范圍更廣的關鍵節點，體現挖掘結果的整體兼顧性.

5 結 論

軟件群體中的關鍵軟件對提高軟件群體維護效率至關重要.本文從軟件群體交互的角度提出了一種復雜軟件群體網絡中關鍵節點挖掘算法SG-CPMining.首先，定義了軟件群體，利用軟件群體中軟件與軟件之間基于數據交換，數據共享，互相調用的信息流構建了基于隨機時間權值的復雜軟件群體網絡模型及軟件交互模型.其次，在軟件交互模型的基礎上，提出了一種復雜軟件群體網絡中的社團結構發現算法SG-GroupMining.第三，在發現的社團結構中提出了一種基于節點度的關鍵節點發現算法.最后，實驗仿真，驗證了交互模型的可行性，高效的挖掘出了軟件群體中的關鍵節點.