黃 毅,張 勝,戴維凱,王 碩,楊 芳

(南昌航空大學(xué)信息工程學(xué)院，南昌 330063)

0 引言

現(xiàn)實(shí)生活中廣泛存在著的復(fù)雜系統(tǒng)都可以通過復(fù)雜網(wǎng)絡(luò)來描述。對(duì)復(fù)雜網(wǎng)絡(luò)拓?fù)涮匦缘难芯繉?duì)于深入理解網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)行為之間的關(guān)系，并進(jìn)而考慮改善網(wǎng)絡(luò)的行為具有十分重要的意義,因此這也一直是復(fù)雜網(wǎng)絡(luò)研究最重要的問題之一。1998—1999年,科學(xué)家們揭示了復(fù)雜網(wǎng)絡(luò)的兩大基本拓?fù)涮匦?小世界特性和無標(biāo)度特性[1-2]。隨后不久,2005年,Song等人[3]將重整化分析法和分形理論中的盒子覆蓋法推廣運(yùn)用于復(fù)雜網(wǎng)絡(luò)研究中,揭示了大量真實(shí)網(wǎng)絡(luò)具有自相似性和分形特性,其中自相似性是指網(wǎng)絡(luò)度分布的冪律形式及冪律指數(shù)在重整化過程中保持不變,而分形特性是指覆蓋整個(gè)網(wǎng)絡(luò)所需的最小盒子數(shù)量NB與盒子尺寸lB呈冪律關(guān)系,即NB≈lB-dB,dB為網(wǎng)絡(luò)的分形維數(shù)。復(fù)雜網(wǎng)絡(luò)分形特性的揭示有助于人們更加深入地理解網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性。同時(shí),分形特性被譽(yù)為復(fù)雜網(wǎng)絡(luò)的第三大基本拓?fù)涮匦?也因此成為了目前復(fù)雜網(wǎng)絡(luò)研究的熱點(diǎn)。

復(fù)雜網(wǎng)絡(luò)分形特性研究的主要工作之一是計(jì)算網(wǎng)絡(luò)的分形維數(shù),分形維數(shù)不僅可以對(duì)網(wǎng)絡(luò)的分形特性做出定量刻畫,同時(shí)也可用于度量分形網(wǎng)絡(luò)的魯棒性[4]。最常見的計(jì)算網(wǎng)絡(luò)分形維數(shù)的方法是盒子覆蓋法[5]。盒子覆蓋法最早是運(yùn)用于計(jì)算歐式空間中傳統(tǒng)分形體分形維數(shù)的方法[6],Song等人將這一方法推廣運(yùn)用于計(jì)算復(fù)雜網(wǎng)絡(luò)的分形維數(shù)[3],其基本思想為:用尺寸為lB的盒子覆蓋網(wǎng)絡(luò)(一個(gè)盒子就是一組節(jié)點(diǎn)的集合,在此集合中任意兩個(gè)節(jié)點(diǎn)間的距離小于lB),統(tǒng)計(jì)出覆蓋整個(gè)網(wǎng)絡(luò)所需的最少盒子數(shù)NB,然后增加盒子尺寸(逐次加1直到等于網(wǎng)絡(luò)的直徑),經(jīng)多次實(shí)驗(yàn)后若lnNB與lnlB呈冪律關(guān)系則說明網(wǎng)絡(luò)具有分形特性,其分形維數(shù)(也稱盒維數(shù))為擬合直線斜率的絕對(duì)值。盒子覆蓋法可歸結(jié)為如何找到規(guī)定盒子尺寸下覆蓋整個(gè)網(wǎng)絡(luò)所需的最小盒子數(shù),這是一個(gè)NP難問題,只能盡可能求出最優(yōu)解。Song等人[7]提出了3種經(jīng)典的盒子覆蓋算法:貪婪著色算法、緊湊盒子燃燒算法以及最大排除質(zhì)量燃燒算法。在貪婪著色算法中,尋找網(wǎng)絡(luò)的最小覆蓋問題被映射為圖論中的點(diǎn)著色問題,該算法最大的特點(diǎn)是具有較小的時(shí)間復(fù)雜度且易于實(shí)現(xiàn),因此得到了廣泛的應(yīng)用。緊湊盒子燃燒算法能產(chǎn)生與貪婪著色算法相媲美的結(jié)果,但是不適用于分析異質(zhì)網(wǎng)絡(luò)的分形特性。最大排除質(zhì)量燃燒算法則是通過計(jì)算節(jié)點(diǎn)的排除質(zhì)量來找到網(wǎng)絡(luò)的最小覆蓋,因此往往能得到一個(gè)確定性解,但是該算法具有非常高的時(shí)間復(fù)雜度。隨后,受Song等人[8]思想的啟發(fā),研究人員從提高計(jì)算效率和降低時(shí)間復(fù)雜度等角度提出了更多的盒子覆蓋算法。例如Kim等提出了隨機(jī)序列盒子覆蓋算法,但該算法仍然具有較高的時(shí)間復(fù)雜度。Gao等[9]則對(duì)Kim提出的算法做了進(jìn)一步改進(jìn),提出了等級(jí)驅(qū)動(dòng)盒子覆蓋算法。Sun等人[10]提出了重疊盒子覆蓋算法,這種可重疊的盒子從某種意義上來說與現(xiàn)實(shí)網(wǎng)絡(luò)中存在的重疊社區(qū)相吻合。此外,也有不少研究人員根據(jù)網(wǎng)絡(luò)的現(xiàn)實(shí)特征從其他角度提出了一些盒子覆蓋算法。如Zhang等人[11]從分形網(wǎng)絡(luò)的中心節(jié)點(diǎn)具有排斥性的角度提出了基于庫倫定律的盒子覆蓋法。Wu等人[12]將最小化盒子數(shù)量與最大化分形模塊度作為盒覆蓋過程中的優(yōu)化目標(biāo),提出了一種多目標(biāo)優(yōu)化的盒子覆蓋法。

除了盒子覆蓋算法定義的盒維數(shù)外,Shanker[13]提出了復(fù)雜網(wǎng)絡(luò)體積維數(shù)的概念,其基本思想為任選節(jié)點(diǎn)i為中心節(jié)點(diǎn),將半徑r范圍內(nèi)覆蓋到的節(jié)點(diǎn)數(shù)量定義為節(jié)點(diǎn)i的體積,然后遍歷網(wǎng)絡(luò)中的節(jié)點(diǎn)為中心節(jié)點(diǎn),計(jì)算所有節(jié)點(diǎn)的體積和的平均值,記為V(r),通過改變r(jià)的取值,多次實(shí)驗(yàn)后測(cè)試V(r)與r是否滿足冪律關(guān)系來判斷網(wǎng)絡(luò)是否具有分形特性。隨后,Guo等人[14]在Shanker的基礎(chǔ)上進(jìn)一步提出了基于平均密度的體積維數(shù)。Wei等人[15]從考慮節(jié)點(diǎn)間差異性的角度進(jìn)一步推廣了體積維數(shù)的定義。Wang等人[16]提出了相關(guān)維數(shù)的概念,通過分析給定距離r下,任意兩個(gè)節(jié)點(diǎn)間距離小于r的數(shù)量與網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)總數(shù)的比率之間的關(guān)系來分析網(wǎng)絡(luò)的分形特性。與盒維數(shù)相比,相關(guān)維數(shù)的計(jì)算具有更小的時(shí)間復(fù)雜度。同時(shí),Lacasa等人[17]還提出了基于遍歷理論的相關(guān)維數(shù)。此外,Wei等人[18]考慮到盒子覆蓋算法中每個(gè)盒子覆蓋能力的差異性,提出了復(fù)雜網(wǎng)絡(luò)信息維數(shù)的概念。Zhang等人[19]提出了基于非廣延熵的復(fù)雜網(wǎng)絡(luò)非廣延信息維數(shù)。文獻(xiàn)[20]在Wei等人提出的信息維數(shù)概念上,提出了基于最大熵最小覆蓋的復(fù)雜網(wǎng)絡(luò)信息維數(shù)。

以上的研究從不同的角度分析了復(fù)雜網(wǎng)絡(luò)的分形特性。但是,值得注意的是,大多數(shù)研究只是針對(duì)無權(quán)網(wǎng)絡(luò)。文獻(xiàn)[21]提出了分析加權(quán)網(wǎng)絡(luò)分形特性的改進(jìn)盒子覆蓋算法(Box-covering algorithm for weighted networks,BCANW),為研究加權(quán)網(wǎng)絡(luò)的分形特性提供了一個(gè)非常好的思想。隨后,文獻(xiàn)[22]采用這種思想提出了分析加權(quán)網(wǎng)絡(luò)多重分形特性的沙箱算法(Sandbox algorithm,SBW)。事實(shí)上,在SBW算法中,通過對(duì)廣義分形維數(shù)D(q)取特殊值也能計(jì)算得到加權(quán)網(wǎng)絡(luò)的分形維數(shù)(q=0時(shí),D(0)為網(wǎng)絡(luò)的盒維數(shù))。但是,不同q值對(duì)應(yīng)的D(q)值是通過選取實(shí)驗(yàn)曲線中合適的冪律范圍然后對(duì)該范圍進(jìn)行線性擬合得到,而如何選取適合的冪律范圍只是通過觀察實(shí)驗(yàn)曲線,并無精確的數(shù)值方法,故這種通過取特殊值的方法來計(jì)算加權(quán)網(wǎng)絡(luò)的分形維數(shù)與網(wǎng)絡(luò)的實(shí)際維數(shù)值存在差別。加權(quán)網(wǎng)絡(luò)能對(duì)復(fù)雜系統(tǒng)各單元間的相互作用提供更加細(xì)致的描述。因此,進(jìn)一步完善有關(guān)加權(quán)網(wǎng)絡(luò)的分形研究理論就顯得至關(guān)重要。一些表面上很相似的維數(shù)定義,它們具有的性質(zhì)可能差別很大,尤其是目前分形理論已經(jīng)不局限于考察分形體結(jié)構(gòu)的分形,而是擴(kuò)展到從功能和信息等角度考察分形體的分形特性。為此,本文提出基于信息維數(shù)的加權(quán)網(wǎng)絡(luò)分形特性分析方法(Information dimension algorithm for weighted networks,IDANW),從信息量的角度刻畫加權(quán)網(wǎng)絡(luò)的分形特性。

1 無權(quán)網(wǎng)絡(luò)信息維數(shù)算法

信息維的概念是由Renyi基于概率理論提出。文獻(xiàn)[23]將這一概念推廣應(yīng)用于復(fù)雜網(wǎng)絡(luò)分形特性的研究。然而,該方法并不適用于計(jì)算實(shí)際網(wǎng)絡(luò)的信息維數(shù),原因在于該方法的核心思想是將復(fù)雜網(wǎng)絡(luò)嵌入到一個(gè)平面上,然后用不同尺度的正方形格子分割此平面,但是真實(shí)系統(tǒng)抽象出的復(fù)雜網(wǎng)絡(luò)模型往往不易于嵌入到一個(gè)平面上。Wei等人[18]提出的基于盒子覆蓋算法的復(fù)雜網(wǎng)絡(luò)信息維數(shù)改進(jìn)算法則使得信息維在實(shí)際網(wǎng)絡(luò)中具有可操作性而不再局限于構(gòu)造網(wǎng)絡(luò)。在盒子覆蓋算法中,每個(gè)盒子被視為具有相同的覆蓋能力。而在信息維的定義中,則充分考慮覆蓋過程中每個(gè)盒子覆蓋能力的差異性。具體的無權(quán)復(fù)雜網(wǎng)絡(luò)信息維數(shù)的算法實(shí)現(xiàn)步驟可歸納為

1)對(duì)給定的網(wǎng)絡(luò)G和盒子尺寸lB,利用盒子覆蓋法找出網(wǎng)絡(luò)的最小覆蓋。

2)將所有的盒子進(jìn)行編號(hào),定義復(fù)雜網(wǎng)絡(luò)落入第i個(gè)盒子的概率為

(1)

其中,n為網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù),ni(lB)為盒子尺寸為lB時(shí)第i個(gè)盒子中包含的節(jié)點(diǎn)總數(shù)?；谶@樣一組概率值,計(jì)算該盒子尺寸下網(wǎng)絡(luò)的信息熵：

(2)

綜合式(1)和(2),可得到復(fù)雜網(wǎng)絡(luò)信息維數(shù)的計(jì)算公式為

(3)

在實(shí)際計(jì)算中,由于盒子長度lB為離散值,無法實(shí)現(xiàn)lB→0,因此通常處理的方法是讓盒子尺寸lB從1開始逐次加1直到等于網(wǎng)絡(luò)直徑,分別統(tǒng)計(jì)出每個(gè)盒子尺寸lB下對(duì)應(yīng)的信息熵I(lB),然后線性擬合I(lB)～lnlB的直線,其斜率值即為信息維數(shù)dI的值。

2 加權(quán)網(wǎng)絡(luò)信息維數(shù)算法

和無權(quán)網(wǎng)絡(luò)相比,加權(quán)網(wǎng)絡(luò)能更加細(xì)致地刻畫網(wǎng)絡(luò)的特征。例如在科學(xué)家合作網(wǎng)絡(luò)中[24],兩個(gè)科學(xué)家之間合作的次數(shù)越多,表明這兩個(gè)科學(xué)家之間的關(guān)系越密切,倘若用無權(quán)網(wǎng)絡(luò)刻畫該網(wǎng)絡(luò),則會(huì)丟失很多重要信息。信息維數(shù)的計(jì)算首先基于盒子覆蓋算法,而在盒子覆蓋算法中,傳統(tǒng)的盒子尺寸賦值規(guī)則是從1開始逐次加1直到等于網(wǎng)絡(luò)的直徑,這種賦值規(guī)則與無權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)間距離的定義具有某種內(nèi)在的關(guān)系。但是,加權(quán)網(wǎng)絡(luò)中節(jié)點(diǎn)間距離的定義與無權(quán)網(wǎng)絡(luò)并不一致,甚至存在一些加權(quán)網(wǎng)絡(luò)的直徑小于1。這說明傳統(tǒng)的盒子尺寸賦值規(guī)則并不完全適用于加權(quán)網(wǎng)絡(luò)。

2.1 算法思想

無權(quán)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間的距離定義為節(jié)點(diǎn)間的最短路徑長度,也即連接這兩個(gè)節(jié)點(diǎn)的最小邊數(shù),其距離值為正整數(shù)。加權(quán)網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)間的距離則和連接這兩個(gè)節(jié)點(diǎn)的邊的權(quán)重值有關(guān),邊權(quán)重值又可分為相異權(quán)和相似權(quán)兩種相反的情況。相異權(quán)表示權(quán)重值越大,節(jié)點(diǎn)間的連接越疏遠(yuǎn),距離也就越遠(yuǎn);相似權(quán)意味著權(quán)重值越大,節(jié)點(diǎn)間的連接越緊密,距離也就越近。目前如何通過邊權(quán)重值計(jì)算節(jié)點(diǎn)間距離值并無統(tǒng)一的標(biāo)準(zhǔn),最常見的一種方法是Dijkstra算法。具體定義如下：

(4)

或者是：

(5)

其中,τ是節(jié)點(diǎn)i和j之間所有相連路徑的集合。然而,該方法求出的節(jié)點(diǎn)間距離值往往是一個(gè)小數(shù),且值很小,表明網(wǎng)絡(luò)的直徑也很小,這意味著在盒子覆蓋算法中,盒子尺寸很快就能達(dá)到網(wǎng)絡(luò)的直徑,從而無法得到多組數(shù)據(jù)來描繪盒子尺寸與該尺寸下相應(yīng)信息熵的關(guān)系,最終導(dǎo)致無法準(zhǔn)確地刻畫網(wǎng)絡(luò)的分形特性。文獻(xiàn)[21]提出的BCANW算法的核心思想是摒棄習(xí)慣上盒子長度為整數(shù)的想法,對(duì)直接相連的節(jié)點(diǎn)間距離值進(jìn)行累加來給盒子尺寸賦值。實(shí)際上,這種賦值方式與傳統(tǒng)的盒子尺寸賦值思想完全吻合,只是在傳統(tǒng)的盒子尺寸賦值規(guī)則中,每次累加的基數(shù)為1,也即無權(quán)網(wǎng)絡(luò)中直接相連的節(jié)點(diǎn)間距離值。受BCANW算法思想的啟發(fā),提出基于信息維數(shù)的加權(quán)網(wǎng)絡(luò)分形特性分析方法,稱為IDANW算法(Information dimension algorithm for weighted networks)。

2.2 算法步驟

IDANW算法步驟描述為

步驟1 對(duì)給定的加權(quán)復(fù)雜網(wǎng)絡(luò)G,根據(jù)網(wǎng)絡(luò)權(quán)重值表示的實(shí)際含義,計(jì)算網(wǎng)絡(luò)中直接相連的節(jié)點(diǎn)間的距離值,并按從小到大的順序排序,記為d1,d2,d3,…，dn。設(shè)置初始盒子尺寸lB=d1。

步驟2 對(duì)給定的盒子尺寸lB,利用貪婪著色算法找出網(wǎng)絡(luò)的最小覆蓋,并計(jì)算該尺寸下網(wǎng)絡(luò)G的信息熵I(lB)。

步驟3 分別設(shè)置盒子尺寸lB=d1+d2,lB=d1+d2+d3,lB=d1+d2+d3+d4…,重復(fù)第二步,直到盒子尺寸lB大于等于網(wǎng)絡(luò)的直徑。統(tǒng)計(jì)出每個(gè)lB所對(duì)應(yīng)的I(lB)。

步驟4 擬合I(lB)～lnlB。

考察擬合I(lB)～lnlB后的直線,若呈線性關(guān)系,說明加權(quán)復(fù)雜網(wǎng)絡(luò)G具有分形特性,對(duì)應(yīng)的信息維數(shù)即為擬合直線的斜率的絕對(duì)值。

3 實(shí)驗(yàn)結(jié)果及分析

本節(jié)分別采用IDANW算法來分析一類構(gòu)造的加權(quán)網(wǎng)絡(luò)和3個(gè)實(shí)際加權(quán)網(wǎng)絡(luò)的分形特性。并且,在對(duì)實(shí)際加權(quán)網(wǎng)絡(luò)分形特性的分析中,分別將網(wǎng)絡(luò)看成無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)兩種情況。

3.1 對(duì)構(gòu)造加權(quán)網(wǎng)絡(luò)的分析

謝爾賓斯基(Sierpinski)加權(quán)分形網(wǎng)絡(luò)是由Carletti等人提出,由迭代函數(shù)系統(tǒng)(Iterated Function Systems)生成,其生成過程由兩個(gè)參數(shù)決定,分別是圖形復(fù)制數(shù)目s(s>1)以及變化比例因子f(0

(6)

為了構(gòu)造謝爾賓斯基加權(quán)分形網(wǎng)絡(luò),初始網(wǎng)絡(luò)設(shè)置為單個(gè)節(jié)點(diǎn),然后根據(jù)參數(shù)s和f的值,依次生成下一代網(wǎng)絡(luò)。如圖1表示s=3,f=1/2的謝爾賓斯基加權(quán)網(wǎng)絡(luò)生成過程,其中G0由單個(gè)節(jié)點(diǎn)構(gòu)成,將G0復(fù)制3次然后通過權(quán)重值為“1”的邊連接起來得到G1,如此重復(fù),后一次連接權(quán)重值為前一次的“1/2”倍,易知其自相似維數(shù)為lg3/lg2≈1.585 0。

s=3,f=1/2圖1 “謝爾賓斯基”加權(quán)網(wǎng)絡(luò)生成過程Fig.1 The growth process of sierpinski weighted networks with parameters

這里將圖形復(fù)制數(shù)目s設(shè)置為3,比例變化因子f依次設(shè)置為1/2,1/3,1/4,1/5,1/6,1/7,1/8,1/9,然后利用IDANW算法計(jì)算每個(gè)f值下的謝爾賓斯基加權(quán)網(wǎng)絡(luò)的信息維數(shù)。由于計(jì)算機(jī)處理能力有限,我們只生成第八代謝爾賓斯基加權(quán)分形網(wǎng)絡(luò),記為G8。G8具有9 841個(gè)節(jié)點(diǎn)和9 837條邊。謝爾賓斯基加權(quán)分形網(wǎng)絡(luò)的邊權(quán)重值并無特殊的物理含義,因此可直接將邊權(quán)重值視為連接這兩個(gè)節(jié)點(diǎn)的距離值。當(dāng)f=1/2時(shí),盒子尺寸分別設(shè)置為1/128,1/128+1/64,1/128+1/64+1/32,…,1/128+1/64+1/32+1/16+1/8+1/4+1/2+1,然后計(jì)算相應(yīng)的信息熵并對(duì)所得數(shù)據(jù)進(jìn)行擬合,結(jié)果如圖2a所示。同理設(shè)置其余值下的盒子尺寸并計(jì)算相應(yīng)信息熵,結(jié)果如圖2b-2h所示。

圖2 第八代謝爾賓斯基加權(quán)網(wǎng)絡(luò)的分形特性分析Fig.2 Fractal scaling analysis of the eighth generation of sierpinski weighted networks

圖3 s=3,-lg(3)/lg(f)的理論曲線與不同f值對(duì)應(yīng)的信息維數(shù)Fig.3 When s=3, the theoretical curve of -lg(3)/lg(f) and the information dimensions with respect to different values of f

從圖2可以看出,每個(gè)值下的盒子尺寸與相應(yīng)信息熵均能夠很好擬合成一條直線,擬合直線的斜率即為信息維數(shù)的值。當(dāng)而取不同值時(shí),謝爾賓斯基加權(quán)分形網(wǎng)絡(luò)的理論維數(shù)值可由式(7)計(jì)算

(7)

為此,分別計(jì)算每個(gè)f值對(duì)應(yīng)的理論維數(shù)值,并與實(shí)際計(jì)算的信息維數(shù)值進(jìn)行比較。結(jié)果如圖3和表1所示。

從圖3和表1可看出,當(dāng)變化比例因子f取不同值時(shí),IDANW算法計(jì)算所得的信息維數(shù)值與謝爾賓斯基加權(quán)分形網(wǎng)絡(luò)的理論維數(shù)值十分接近,最大相對(duì)誤差為5.93%,這也表明了IDANW算法在分析構(gòu)造加權(quán)網(wǎng)絡(luò)分形特性時(shí)的有效性。

3.2 對(duì)實(shí)際加權(quán)網(wǎng)絡(luò)的分析

進(jìn)一步地,利用IDANW算法分析3個(gè)更具代表性的實(shí)際加權(quán)網(wǎng)絡(luò)的分形特性。分別是Newman科學(xué)家合作網(wǎng)絡(luò)[24],美國航空網(wǎng)絡(luò)(數(shù)據(jù)源:http://vlado.fmf.unilj.si/pub/networks/data/)以及線蟲神經(jīng)網(wǎng)絡(luò)[1]。這3個(gè)實(shí)際網(wǎng)絡(luò)的盒維數(shù)已在文獻(xiàn)[21]中計(jì)算得到。

表1 s=3,不同f值對(duì)應(yīng)的信息維數(shù)與理論維數(shù)Tab.1 The information dimensions and the theoretical dimensions of sierpinski weighted networks with parameter s=3 and different values of f

Newman科學(xué)家合作網(wǎng)絡(luò)具有1 589個(gè)節(jié)點(diǎn)與2 742條邊,其中節(jié)點(diǎn)代表科學(xué)家,邊代表兩個(gè)科學(xué)家之間具有合作關(guān)系。節(jié)點(diǎn)i和節(jié)點(diǎn)j之間權(quán)重值的計(jì)算方法為

(8)

美國航空網(wǎng)絡(luò)是將332個(gè)機(jī)場抽象為網(wǎng)絡(luò)節(jié)點(diǎn),2 126條航班抽象為邊的網(wǎng)絡(luò)。網(wǎng)絡(luò)的權(quán)重值是指定期航班的客容量(單位:百萬人次/年)。顯然,當(dāng)權(quán)重值越大時(shí),表示兩個(gè)機(jī)場關(guān)系密切,距離就越近(這里的距離并非指兩個(gè)機(jī)場之間的地理距離),因此美國航空網(wǎng)絡(luò)的權(quán)重類型也是相似權(quán)。采用式(5)計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)間距離后得到網(wǎng)絡(luò)的直徑為0.96。若采用傳統(tǒng)的盒子尺寸賦值思想,覆蓋整個(gè)網(wǎng)絡(luò)只需一個(gè)盒子,相應(yīng)的信息熵為0,因此無法利用信息維數(shù)刻畫該網(wǎng)絡(luò)的分形特性。同樣地,分別將美國航空網(wǎng)絡(luò)視為加權(quán)網(wǎng)絡(luò)和無權(quán)網(wǎng)絡(luò)兩種情況并分析其分形特性。結(jié)果如圖4b所示。從圖4b可以看出,無權(quán)航空網(wǎng)絡(luò)和加權(quán)航空網(wǎng)絡(luò)均表現(xiàn)出分形特性,其信息維數(shù)分別為3.218和1.179。

圖4 IDANW算法分析實(shí)際加權(quán)網(wǎng)絡(luò)Fig.4 Fractal scaling analysis of real-world networks by IDANW

線蟲神經(jīng)網(wǎng)絡(luò)具有306個(gè)節(jié)點(diǎn)和2 148條邊,節(jié)點(diǎn)表示神經(jīng)元,邊表示神經(jīng)元之間的連接,邊的權(quán)重值由神經(jīng)元之間的連接強(qiáng)度決定。當(dāng)連接強(qiáng)度越大時(shí)權(quán)重值也越大,表明兩個(gè)神經(jīng)元關(guān)系密切,距離就越近,因此線蟲神經(jīng)網(wǎng)絡(luò)的權(quán)重類型仍然是相似權(quán)。對(duì)無權(quán)線蟲神經(jīng)網(wǎng)絡(luò)和加權(quán)線蟲神經(jīng)網(wǎng)絡(luò)分形特性的分析結(jié)果如圖4c所示。從圖4c可以看出,無權(quán)線蟲神經(jīng)網(wǎng)絡(luò)和加權(quán)線蟲神經(jīng)網(wǎng)絡(luò)也均表現(xiàn)出分形特性,其信息維數(shù)分別為3.505和1.458。

通過對(duì)3個(gè)不同實(shí)際加權(quán)網(wǎng)絡(luò)的分析可以看出,當(dāng)把網(wǎng)絡(luò)看成無權(quán)網(wǎng)絡(luò)和加權(quán)網(wǎng)絡(luò)兩種情況時(shí),兩者的信息維數(shù)并不一致,這說明加權(quán)網(wǎng)絡(luò)的邊權(quán)重值對(duì)網(wǎng)絡(luò)的分形特性具有一定的影響。更進(jìn)一步地,采用BCANW算法分析上述3個(gè)實(shí)際加權(quán)網(wǎng)絡(luò)的分形特性,并將分析結(jié)果與IDANW算法得到的結(jié)果進(jìn)行對(duì)比。同樣,分別將網(wǎng)絡(luò)看成加權(quán)網(wǎng)絡(luò)和無權(quán)網(wǎng)絡(luò)兩種情況。采用BCANW算法分析的結(jié)果如圖4中紅色圓點(diǎn)所示,對(duì)比結(jié)果如表2所示。

圖5 BCANW算法分析實(shí)際加權(quán)網(wǎng)絡(luò)Fig.5 Fractal scaling analysis of real-world network by BCANW

算法分形維數(shù)科學(xué)家合作網(wǎng)絡(luò)美國航空網(wǎng)絡(luò)線蟲神經(jīng)網(wǎng)絡(luò)IDANW加權(quán)信息維數(shù)0.6551.1791.458無權(quán)信息維數(shù)無分形特性3.2183.505BCANW加權(quán)盒維數(shù)0.3461.0080.826無權(quán)盒維數(shù)無分形特性3.1193.331

從圖5和表2可以看出,當(dāng)利用盒維數(shù)分析這3個(gè)實(shí)際網(wǎng)絡(luò)的分形特性時(shí),加權(quán)科學(xué)家合作網(wǎng)絡(luò)的盒維數(shù)為0.346,而無權(quán)科學(xué)家合作網(wǎng)絡(luò)則沒有表現(xiàn)出分形特性。對(duì)于美國航空網(wǎng)絡(luò),加權(quán)美國航空網(wǎng)絡(luò)和無權(quán)美國航空網(wǎng)絡(luò)均表現(xiàn)出分形特性,其盒維數(shù)分別為1.008和3.119。對(duì)于線蟲神經(jīng)網(wǎng)絡(luò),加權(quán)線蟲神經(jīng)網(wǎng)絡(luò)和無權(quán)線蟲神經(jīng)網(wǎng)絡(luò)的盒維數(shù)分別為0.826和3.331。注意到,對(duì)不同的實(shí)際網(wǎng)絡(luò),IDANW算法和BCANW算法計(jì)算所得的分形維數(shù)值差異性表現(xiàn)差別較大。對(duì)于科學(xué)家合作網(wǎng)絡(luò)和美國航空網(wǎng)絡(luò),IDANW算法和BCANW算法計(jì)算所得的分形維數(shù)值較為接近,差值分別為0.309和0.171。而對(duì)于線蟲神經(jīng)網(wǎng)絡(luò),二者的差值較大,為0.632。實(shí)質(zhì)上,IDANW算法和BCANW算法是對(duì)同一個(gè)網(wǎng)絡(luò),從不同的角度去分析它的分形特性,其中BCANW算法是從盒子尺寸與該尺寸下盒子數(shù)量間的關(guān)系分析網(wǎng)絡(luò)的分形特征,而IDANW算法則是從盒子尺寸與該尺寸下網(wǎng)絡(luò)信息熵間的關(guān)系來分析網(wǎng)絡(luò)的分形特征,所以兩種方法計(jì)算求得的維數(shù)值也不同。

為了考察直線的擬合效果和進(jìn)一步比較IDANW算法和BCANW算法,這里考慮最小二乘擬合法的均方誤差值Q,其定義為

(9)

表3 IDANW算法和BCANW算法擬合結(jié)果對(duì)比Tab.3 The fitting results comparison between IDANW and BCANW

從表3可以看出,科學(xué)家合作網(wǎng)絡(luò)和美國航空網(wǎng)絡(luò)的均方誤差值都比較小,用IDANW算法和BCANW算法均能發(fā)現(xiàn)其具有分形特性。對(duì)于線蟲神經(jīng)網(wǎng)絡(luò),IDANW算法的均方誤差較小,為0.419 5,而BCANW算法的均方誤差值則達(dá)到0.735 0,接近于1。表2中表明對(duì)于線蟲神經(jīng)網(wǎng)絡(luò)用IDANW算法和BCANW算法分析其分形特征時(shí),兩個(gè)方法的結(jié)果差異比較明顯,并且從圖5c中也能發(fā)現(xiàn)其數(shù)據(jù)點(diǎn)較為分散,這說明加權(quán)線蟲神經(jīng)網(wǎng)絡(luò)的分形特性用BCANW算法不易度量出。此外,從表3也能看出,Q1的值要比Qb的值小,這也進(jìn)一步表明了IDANW算法在分析實(shí)際加權(quán)網(wǎng)絡(luò)分形特性時(shí)的有效性。

4 結(jié)論

復(fù)雜網(wǎng)絡(luò)信息維數(shù)實(shí)質(zhì)是香農(nóng)熵的一種表現(xiàn)形式。本文針對(duì)目前網(wǎng)絡(luò)分形研究主要針對(duì)無權(quán)網(wǎng)絡(luò)這一問題,提出了一種基于信息維數(shù)的加權(quán)網(wǎng)絡(luò)分形特性分析方法(IDANW)。通過對(duì)一類構(gòu)造的謝爾賓斯基加權(quán)網(wǎng)絡(luò)和3個(gè)實(shí)際加權(quán)網(wǎng)絡(luò)的分形分析結(jié)果表明了IDANW算法能夠較好度量出加權(quán)網(wǎng)絡(luò)的分形特征。此外,在對(duì)實(shí)際網(wǎng)絡(luò)的分形特性分析中,分別將網(wǎng)絡(luò)看成加權(quán)網(wǎng)絡(luò)和無權(quán)網(wǎng)絡(luò)兩種情況,結(jié)果發(fā)現(xiàn)加權(quán)網(wǎng)絡(luò)的信息維數(shù)值與無權(quán)網(wǎng)絡(luò)的信息維數(shù)值并不一致,表明網(wǎng)絡(luò)權(quán)重值對(duì)網(wǎng)絡(luò)分形特征有一定影響,這一結(jié)論與文獻(xiàn)[21]和文獻(xiàn)[22]所得結(jié)論一致。加權(quán)網(wǎng)絡(luò)可以對(duì)復(fù)雜系統(tǒng)的相互作用結(jié)構(gòu)提供更加細(xì)致的刻畫。因此加權(quán)網(wǎng)絡(luò)分形分析理論的建立有助于去分析實(shí)際加權(quán)網(wǎng)絡(luò)中的統(tǒng)計(jì)特性從而更好地認(rèn)識(shí)復(fù)雜系統(tǒng)。本文的研究進(jìn)一步豐富了復(fù)雜網(wǎng)絡(luò)分形的研究成果。