面向?qū)ο筌浖到y(tǒng)演化模型

馬 健,樊建平,劉 峰,李紅輝

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

0 引 言

自然界和人類社會中的大量系統(tǒng)都可以通過復雜網(wǎng)絡加以描述[1]。面向?qū)ο筌浖到y(tǒng)也可以轉(zhuǎn)化為人工復雜網(wǎng)絡。這方面的研究有:Bhattacharya等[2]分析了軟件源代碼,將函數(shù)抽象為節(jié)點,調(diào)用關(guān)系抽象為有向邊構(gòu)造圖形,生成軟件拓撲結(jié)構(gòu)。Chong等[3]不僅構(gòu)造了軟件圖形,還為邊分配權(quán)重進行了擴展。Chaikalis等[4]將類抽象為節(jié)點,將類之間的(調(diào)用、關(guān)聯(lián)、依賴)關(guān)系抽象為有向邊。Turnu等[5]分析了Java、Eclipse和Netbeans大型面向?qū)ο筌浖到y(tǒng)的源代碼,研究了源代碼中的類和它們之間的依賴關(guān)系和整個發(fā)行版及其子項目的復雜性,結(jié)果表明,這樣的系統(tǒng)可以被看作是復雜軟件網(wǎng)絡。

網(wǎng)絡演化是網(wǎng)絡的結(jié)構(gòu)發(fā)生變化,網(wǎng)絡演化的模型有:Barabási等[6]提出了BA無標度網(wǎng)絡模型,模型基于增量增長和線性優(yōu)先關(guān)系兩種機制;Valverde等[7]提出了基于節(jié)點復制和邊重新連接的模型;Myers[8]提出了基于重構(gòu)過程的模型。Dorogovtsev等[9]提出了依賴現(xiàn)有節(jié)點的度數(shù)和年齡的模型;Zheng等[10]也提出了一個基于節(jié)點的度數(shù)和年齡的模型(Degree and age dependent adjustable evolution,DAAE);Li等[11]提出了一種模擬軟件網(wǎng)絡演化的模塊連接機制,使用模塊化連接代替在前面的模型中采用的單節(jié)點連接,因為將面向?qū)ο笙到y(tǒng)模塊化與現(xiàn)實世界軟件本質(zhì)上更加相似。張錫哲等[12]提出一種新穎的基于復雜網(wǎng)絡的服務軟件行為演化模型,在大量真實服務數(shù)據(jù)的基礎上,考察了面向服務的軟件系統(tǒng)的演化仿真并分析其拓撲特征,與傳統(tǒng)軟件所構(gòu)成的軟件網(wǎng)絡進行了對比,指出面向服務的軟件系統(tǒng)特有的特征規(guī)律。還有一些模型也從不同的角度模擬了軟件網(wǎng)絡演化這一過程[13]。

本文提出了一種基于局域事件(Local events)的軟件網(wǎng)絡演化模型,模型以面向?qū)ο筌浖到y(tǒng)為研究對象,分析軟件系統(tǒng)網(wǎng)絡的度分布,模擬軟件網(wǎng)絡的演化過程。

1 基本概念

1.1 軟件網(wǎng)絡

本文中從軟件的源代碼中提取組成系統(tǒng)的類抽象為節(jié)點,它們之間的關(guān)系抽象為邊,例如:源類引用目標類對象,將目標類對象作為局部變量或者源類方法的參數(shù)或返回類型是目標類。軟件系統(tǒng)轉(zhuǎn)化為由許多相互連接的類組成的類圖。這樣,復雜的軟件系統(tǒng)就用軟件類圖表示,研究結(jié)論表明像大量人工網(wǎng)絡那樣,軟件類圖也具有“小世界”和“無標度”的特性[14]。我們將類圖看作軟件網(wǎng)絡,也就是將面向?qū)ο筌浖到y(tǒng)也可以轉(zhuǎn)化為人工網(wǎng)絡。

圖1為Junit軟件類圖。將類抽象為節(jié)點,類之間的關(guān)系抽象為邊,Junit軟件類圖可以看作是錯綜復雜的軟件網(wǎng)絡。

圖1 Junit軟件類圖Fig.1 Junit class diagrams

度分布是網(wǎng)絡統(tǒng)計性質(zhì)中最重要的性質(zhì),也稱為網(wǎng)絡節(jié)點的度分布,分布情況可用分布函數(shù)P(k)表示,P(k)表示一個隨機選定的節(jié)點的度恰好為k的概率。網(wǎng)絡中一個節(jié)點直接連接的鄰接點的多少通常反映了它在網(wǎng)絡中的重要程度。例如萬維網(wǎng)、電影演員網(wǎng)、論文引用關(guān)系網(wǎng)等,新演員總是愿意與有影響力的演員合作,網(wǎng)頁鏈接總是更多地指向那些有很多連接指向它的網(wǎng)頁,一篇論文被引用的次數(shù)越多,被新論文引用的概率就越大。

1.2 BA無標度網(wǎng)絡模型(Scale-free networks)

1999年,Barabási等[15]提出了無標度網(wǎng)絡(Scale-free networks)模型,具有冪律分布的網(wǎng)絡被稱為無標度網(wǎng)絡,其度分布具有胖尾現(xiàn)象,實驗結(jié)果表明許多現(xiàn)實的大規(guī)模網(wǎng)絡的度分布服從冪律分布。

BA網(wǎng)絡包括兩個特性:

(1)增長。初始時具有少量m0個節(jié)點,每個時間步增加一個新節(jié)點,連接到m m≤m0()個已存在于系統(tǒng)中的舊節(jié)點上。

(2)優(yōu)先連接。新節(jié)點連接到舊節(jié)點的概率與舊節(jié)點的度成正比,N表示網(wǎng)絡節(jié)點總數(shù)。

經(jīng)過t時間間隔后,網(wǎng)絡演化為一個有N＝m0＋mt個節(jié)點、mt條邊的網(wǎng)絡,達到穩(wěn)定的狀態(tài)。

無標度網(wǎng)絡模型是節(jié)點的度連接沒有明顯的特征長度,因此也稱為無標度網(wǎng)絡。該模型描述了網(wǎng)絡具有演化生長和節(jié)點依附偏好的特性,即精確或近似地遵循冪函數(shù)的度分布。

2 基于局域事件網(wǎng)絡演化模型

軟件最初的版本一般都相對簡單,軟件內(nèi)部的復雜程度也相對一般,但隨著時間的推移,為滿足新的需求或加入新的功能會對程序進行修改,軟件的復雜程度也會不斷地增加。在真實的軟件系統(tǒng)中,新增類加入到軟件中與軟件中已存在的類發(fā)生關(guān)系,已存在的類之間也會改變現(xiàn)有的各種關(guān)系或刪除已存在的類及其關(guān)系。局域事件演化網(wǎng)絡模型模擬了上述情形,例如:帶有新邊的新節(jié)點與現(xiàn)有節(jié)點之間的連接,在網(wǎng)絡中現(xiàn)有節(jié)點間添加新邊,現(xiàn)有邊的刪除和重新連接。在BA模型的基礎上,本文提出了基于局域事件網(wǎng)絡演化模型模擬真實軟件網(wǎng)絡的演化過程。

(1)初始網(wǎng)絡:具有少量m0個節(jié)點。

(2)網(wǎng)絡演化:

①以概率p1增加一個新節(jié)點,新節(jié)點連接m條新邊,新節(jié)點按擇優(yōu)概率式(1)選取節(jié)點i與新增節(jié)點產(chǎn)生一條邊,這個過程重復m次。

②以概率p2在網(wǎng)絡已有節(jié)點之間增添m條邊,新增的邊一端按擇優(yōu)概率公式(1)∏(k i)選取節(jié)點i,另一個節(jié)點也按擇優(yōu)概率公式(1)∏(k j)選取節(jié)點j。

③以概率p3在網(wǎng)絡已有節(jié)點之間刪除m條邊。

綜合上述3種情況,將式(3)(4)(5)相加可得:

式中:N＝m0＋mt;∑jk j＝2mt－m;對于較大的t、m0和m可以忽略,初始條件t i時刻增加的連接數(shù)為m,k i(t i)＝m。

對上述微分方程(6)求解得:

網(wǎng)絡中所有的節(jié)點都以同樣的冪律增長,γ稱為動力學指數(shù)。p1＋p2＋p3＝1。

隨機變量t i服從(0,t)區(qū)間上的均勻分布,有:;

由式(7)可以看出,基于局域事件網(wǎng)絡演化模型也是無標度模型。

3 實驗分析

3.1 實驗數(shù)據(jù)

Dependency Finder分析工具可以實現(xiàn)從Java字節(jié)碼文件中抽取面向?qū)ο筌浖愱P(guān)系和度量。在本實驗中使用Dependency Finder抽取所選實驗對象類的之間關(guān)系進行分析。

為驗證本文提出的基于局域事件的無標度網(wǎng)絡模型,選取了6款Java面向?qū)ο箝_源軟件,表1為Azureus5.7.1.0,structs1.3.10,tomcat9.0.0,ant1.9.7,itext5.5.9,jedit4.3的參數(shù),使用Mablab對生成的冪律函數(shù)曲線進行分析擬合。

表1 軟件相關(guān)參數(shù)Table 1 Software related parameters

3.2 實驗結(jié)果分析

圖2為在雙對數(shù)坐標中的參數(shù)分析,是提出的模型式(7)的度分布曲線。對變量分別取對數(shù)可以得到度分布曲線是一條負斜率的直線,所以,得到模型為無標度網(wǎng)絡模型。

圖2 模型不同參數(shù)度分布圖Fig.2 Different parameter of model degree distribution

本文分析了6個面向?qū)ο筌浖到y(tǒng),以Azureus5.7.1.0為例,圖3(a)中的‘?’為Azureus真實網(wǎng)絡的度分布,‘＋’為BA無標度網(wǎng)絡模型的度分布曲線,‘·’為基于局域事件(LE)的無標度網(wǎng)絡的度分布曲線?？梢钥闯?在圖3(a)的雙對數(shù)坐標中,Azureus真實網(wǎng)絡度分布具有胖尾現(xiàn)象。說明度數(shù)大的節(jié)點占少數(shù),大部分的節(jié)點的度數(shù)較小,度數(shù)較大的少數(shù)節(jié)點對應于軟件系統(tǒng)中的通用類,這些類被程序員經(jīng)常使用。上述結(jié)果表明,面向?qū)ο筌浖到y(tǒng)的度分布遵循冪律分布。

這種基于局域網(wǎng)絡演化機制的模型適合描述面向?qū)ο筌浖到y(tǒng),軟件網(wǎng)絡經(jīng)過長時間演化后,導致網(wǎng)絡中大多數(shù)節(jié)點擁有少數(shù)連接的邊,而極少數(shù)節(jié)點,擁有大量連接。結(jié)果導致“富者越富”和中樞點現(xiàn)象。這些軟件網(wǎng)絡的度分布都服從冪律分布。

圖3 軟件系統(tǒng)演化模型的仿真結(jié)果Fig.3 Simulation results of software systems

采用目前通用的驗證度指數(shù)的方法,根據(jù)初步統(tǒng)計,對軟件系統(tǒng)進行度指數(shù)分析。所有軟件網(wǎng)絡擬合后曲線的斜率均在(2,3)區(qū)間,結(jié)論與建模分析得到的結(jié)論一致。顯然,本文提出的模型更能較好地模擬真實網(wǎng)絡的度分布情況,模擬Azureus仿真網(wǎng)絡的參數(shù)為m＝10,p1＝0.8,p2＝0.1;模擬structs仿真網(wǎng)絡的參數(shù)為m＝10,p1＝0.8,p2＝0.06;其他模擬仿真網(wǎng)絡的參數(shù)如表2所示,與實際系統(tǒng)的演化度分布情況基本一致。

表2 模擬參數(shù)Table 2 Simulation parameters

綜上所述,軟件系統(tǒng)經(jīng)過長時間演化后,導致網(wǎng)絡中大多數(shù)節(jié)點擁有少數(shù)連接的邊,而極少數(shù)節(jié)點,擁有大量連接。即軟件大多數(shù)節(jié)點較少與其他節(jié)點產(chǎn)生依賴(調(diào)用、繼承、消息等)關(guān)系,極少節(jié)點與大量其他節(jié)點具有依賴關(guān)系。例如:有的工具類被許多其他類調(diào)用,面向?qū)ο筌浖W(wǎng)絡具有復雜網(wǎng)絡特性,即度分布服從冪律分布。

4 結(jié)束語

本文選取了6款開源面向?qū)ο筌浖到y(tǒng)為研究對象,對BA無標度網(wǎng)絡模型進行改進,增加了添加節(jié)點、添加邊、刪除邊和邊的重連等局域事件,模擬軟件網(wǎng)絡的演化過程。實驗結(jié)果表明,軟件系統(tǒng)的度分布服從衰減冪律分布和無標度分布。標度指數(shù)在2和3之間,也就是說,大規(guī)模軟件系統(tǒng)的度分布服從衰減冪律分布的無標度分布,這種現(xiàn)象說明通用類在軟件系統(tǒng)的成長過程中發(fā)揮著重要作用,其中代碼重用引起了“富者越富”現(xiàn)象的產(chǎn)生。軟件演化的過程中還伴隨著節(jié)點和邊的添加、移除和邊的重連現(xiàn)象,為了描述軟件系統(tǒng)的演化過程,構(gòu)建了一個軟件系統(tǒng)演化模型,模擬軟件網(wǎng)絡演化增長,就是文中提出的基于局域事件的網(wǎng)絡演化模型。實驗結(jié)果表明,該模型的度分布與實際軟件網(wǎng)絡基本相符,提出的模型能較好地描述真實軟件的演化增長情況,計算得到的冪律指數(shù)與真實軟件的度分布基本一致。數(shù)據(jù)仿真驗證了該模型的有效性。

[1]郭玉泉,李雄飛.復雜網(wǎng)絡社區(qū)的分形聚類檢測方法[J].吉林大學學報:工學版,2016,46(5):1633-1638.Guo Yu-quan,Li Xiong-fei.Fractal clustering method for uncovering community of complex network[J].Journal of Jinlin University(Engineering and Technology Edition),2016,46(5):1633-1638.

[2]Bhattacharya P,Iliofotou M,Neamtiu I,et al.Graph-based analysis and prediction for software evolution[C]∥Proceedings of the 34th International Conference on Software Engineering(ICSE).Zuricah:ACM,2012:419-429.

[3]Chong C Y,Lee S P.Analyzing maintainability and reliability of object-oriented software using weighted complex network[J].Journal of Systems and Software,2015,110:28-53.

[4]Chaikalis T,Chatzigeorgiou A.Forecasting java software evolution trends employing network mod-els[J].IEEE Transactions on Software Engineering,2015,41(6):582-602.

[5]Turnu I,Concas G,Marchesi M,et al.The fractal dimension of software networks as a global quality metric[J].Information Sciences,2013,245(10):290-303.

[6]Barabási A L,Albert R.Emergence of scaling in random networks[J].Science,1999,286(5439):509-512.

[7]alverde S,SoléR V.Network motifs in computational graphs:a case study in software architecture[J].Physical Review E Statistical Nonlinear and Soft Matter Physics,2005,72(2):026107.

[8]Myers C R.Software systems as complex networks:structure,function,and evolvability of software collaboration graphs[J].Physical Review E Statistical Nonlinear and Soft Matter Physics,2003,68(2):046116.

[9]Dorogovtsev S N,Mendes J F F.Evolution of reference networks with aging[J].Physical Review E Statistical Physics,Plasmas,Fluids,and Related Interdisciplinary Topics,2000,62(2):1842-1845.

[10]Zheng X L,Zeng D,Li H,et al.Analyzing opensource software systems as complex networks[J].Physica A Statistical Mechanics and Its Applications,2008,387(24):6190-6200.

[11]Li H,Zhao H,Cai W,et al.A modular attachment mechanism for software network evolution[J].Physica A Statistical Mechanics and Its Applications,2013,392(9):2025-2037.

[12]張錫哲,呂天陽,張斌.基于服務交互行為的復雜服務協(xié)同網(wǎng)絡建模[J].軟件學報,2016,27(2):231-246.Zhang Xi-zhe,LüTian-yang,Zhang Bin.Modeling complex collaboration network for service-oriented software based on execution behaviors[J].Journal of Software,2016,27(2):231-246.

[13]Dabrowski R,Stencel K,Timoszuk G.Software is a directed multigraph[C]∥Proceedings of the 5th European conference on Software architecture.Essen:Spring,2011:360-369.

[14]Valverde S,Cancho R F I,Sole R V.Scale-free networks from optimal design[J].Europhysics Letters,2002,60(4):512-517.

[15]Barabási A L,Alert R,Jeong H.Mean-field theory for scale-free random networks[J].Physica A Statistical Mechanics and Its Applications,1999,272(1):173-187.