加權(quán)網(wǎng)絡的體積維數(shù)

， ，， ，

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

0 引言

復雜網(wǎng)絡作為復雜系統(tǒng)的高度抽象和研究工具,近十幾年來受到了來自計算機科學、信息科學、生物學、統(tǒng)計物理學、社會學等眾多不同學科領域研究人員的廣泛關注,成為科學研究的熱點。對復雜網(wǎng)絡拓撲性質(zhì)的準確度量對于復雜網(wǎng)絡模型的建立以及復雜網(wǎng)絡動力學行為的研究具有十分重要的意義,因此復雜網(wǎng)絡拓撲性質(zhì)的研究也是復雜網(wǎng)絡理論研究的關鍵。20世紀末,科學家們揭示了復雜網(wǎng)絡的兩大基本拓撲特性:小世界特性和無標度特性[1-2]。小世界特性是指網(wǎng)絡節(jié)點間的平均路徑短且平均聚集系數(shù)高,對應于社交網(wǎng)絡中的“六度分割”現(xiàn)象。無標度特性則是指網(wǎng)絡節(jié)點的度分布服從冪律分布,對應于經(jīng)濟生活中的“馬太效應”。隨后,2005年, Song等人開創(chuàng)性地將重整化理論和分形理論中的盒子覆蓋法推廣應用于復雜網(wǎng)絡的研究,揭示了大量實際網(wǎng)絡具有自相似性和分形特性[3],其中自相似性是指網(wǎng)絡度分布的冪律形式及冪指數(shù)在重整化過程中保持不變,分形特性則是指覆蓋整個網(wǎng)絡所需的最小盒子數(shù)量與盒子長度呈冪律關系,即NB(lB)≈lB-dB,dB為網(wǎng)絡的分形維數(shù)。復雜網(wǎng)絡分形特性的揭示有助于人們更加深入地理解網(wǎng)絡結(jié)構(gòu)的復雜性。同時,分形特性也被譽為復雜網(wǎng)絡的第三大基本拓撲特性。

分形維數(shù)是定量刻畫分形體分形特性的最重要指標。在復雜網(wǎng)絡領域,關于分形維數(shù)的定義和算法有很多[4-6],其中最常見的是由盒子覆蓋法定義的盒維數(shù)[7]。盒子覆蓋法計算網(wǎng)絡盒維數(shù)的過程大致可分為3個步驟:第一步用長度為lB的盒子覆蓋整個網(wǎng)絡(一個盒子就是一組節(jié)點的集合,在此集合中任意兩個節(jié)點間的距離小于lB),計算覆蓋整個網(wǎng)絡所需的最小盒子數(shù)量NB(lB);第二步增加盒子長度lB(每次以1遞增,直到lB等于網(wǎng)絡的直徑),分別計算在規(guī)定盒子長度下所需的最小盒子數(shù)量NB(lB);第三步將數(shù)據(jù)對(lB,NB(lB))繪制在雙對數(shù)坐標中,若lB與NB(lB)呈冪律關系,則表明網(wǎng)絡具有分形特性,盒維數(shù)即為擬合直線斜率的絕對值。實質(zhì)上,盒子覆蓋法可歸結(jié)為如何在規(guī)定的盒子長度下找到覆蓋整個網(wǎng)絡所需的最小盒子數(shù)量,這是一個NP完全問題,只能盡可能找到最優(yōu)解。Song等人在文獻[8]中提出了3種經(jīng)典的方法:貪婪著色算法、緊湊盒子燃燒算法以及最大排除質(zhì)量燃燒算法。隨后,更多的改進盒子覆蓋算法被提出。例如Schneider等人在最大排除質(zhì)量燃燒算法的基礎上,提出了一種新型的優(yōu)化算法[9],該算法在對許多實際網(wǎng)絡的分形分析中能得到更加精確的解,但是該算法的時間復雜度較高,達到O(2N),N為網(wǎng)絡節(jié)點總數(shù)。Sun等人提出了重疊盒子覆蓋算法[10],這種可重疊盒子的思想與現(xiàn)實網(wǎng)絡存在重疊社區(qū)是相吻合的,并且該算法能得到與Schneider等人提出的算法相媲美的結(jié)果。 此外,也有不少研究人員根據(jù)網(wǎng)絡的現(xiàn)實特征從其他角度提出了一些盒子覆蓋算法。例如Zhang等人[11]利用網(wǎng)絡節(jié)點間的排斥力重新定義了節(jié)點間的距離,也可以得到現(xiàn)實網(wǎng)絡的分形特征。Wu等人[12]將最小化盒子數(shù)量與最大化分形模塊度作為盒覆蓋過程中的優(yōu)化目標,提出了一種多目標優(yōu)化的盒子覆蓋法。Wei等人[13]考慮到現(xiàn)實中的網(wǎng)絡多為加權(quán)網(wǎng)絡而傳統(tǒng)的盒子覆蓋算法并不完全適用于度量加權(quán)網(wǎng)絡的分形特性,從而提出了一種加權(quán)的盒子覆蓋算法,為分析加權(quán)網(wǎng)絡的分形特性提供了新的視角和方法。

除盒子覆蓋法定義的盒維數(shù)外,體積維數(shù)也被廣泛地應用于度量網(wǎng)絡的分形特性。值得注意的是,這里所指的“體積”與傳統(tǒng)意義上三維空間中的體積并非一個概念。復雜網(wǎng)絡體積維數(shù)的概念最早由O.Shanker提出[14-15], 其基本思想為任選節(jié)點i為中心節(jié)點,將半徑r范圍內(nèi)覆蓋到的節(jié)點數(shù)量定義為節(jié)點i的體積,然后遍歷網(wǎng)絡中的節(jié)點為中心節(jié)點,計算所有節(jié)點的體積和的平均值,記為V(r),通過改變r的取值,多次實驗后若V(r)與r滿足冪律關系V(r)～rdv,則說明網(wǎng)絡具有分形特性,其中dv為對應的體積維數(shù)。隨后,Guo等人[16]及Wei等人[17]進一步改進了O.Shanker提出的體積維數(shù)的概念,并用改進后的方法分析了多個實際網(wǎng)絡的分形特性。然而,現(xiàn)有的網(wǎng)絡分形維數(shù)的定義主要是針對無權(quán)網(wǎng)絡提出,鮮有關于加權(quán)網(wǎng)絡分形維數(shù)的定義及算法。加權(quán)網(wǎng)絡和無權(quán)網(wǎng)絡相比能對復雜系統(tǒng)各單元間的關系及相互作用提供更加細致的刻畫。因此,完善有關加權(quán)網(wǎng)絡的分形研究理論有助于去分析實際加權(quán)網(wǎng)絡中的統(tǒng)計特性從而更好地認識復雜系統(tǒng)。在O.Shanker提出的無權(quán)網(wǎng)絡體積維數(shù)中,在尺度r(半徑)下,每個節(jié)點的體積為以該節(jié)點為中心覆蓋到的節(jié)點數(shù)目,整個網(wǎng)絡的體積則為所有節(jié)點體積的平均值,也即O.Shanker是以節(jié)點數(shù)目來定義網(wǎng)絡的“體積”。加權(quán)網(wǎng)絡中,節(jié)點的強度是一個非常重要的統(tǒng)計量,其是節(jié)點局域信息的一種綜合表達方式[18]。因此,本文沿著O.Shanker提出的無權(quán)網(wǎng)絡體積維數(shù)思想進一步考慮,在尺度r(半徑)下,將每個節(jié)點的體積定義為以該節(jié)點為中心節(jié)點覆蓋到的節(jié)點強度和,將整個網(wǎng)絡的“體積”定義為所有節(jié)點體積的平均值,從強度體積的角度來考察加權(quán)網(wǎng)絡的分形特征,并稱這種衡量加權(quán)網(wǎng)絡分形特性的維數(shù)為強度體積維。

1 前期工作

一個給定的復雜網(wǎng)絡可以抽象為一個由點集V和邊集E組成的圖G=(V,E),其中E中的每條邊都有V中的一對節(jié)點與之對應。無權(quán)網(wǎng)絡中任意兩個節(jié)點間的距離定義為連接這兩個節(jié)點的最小邊數(shù),因此其值為正整數(shù)。在O.Shanker提出的經(jīng)典的體積維數(shù)定義中,“體積”是指每一盒子長度下覆蓋到的節(jié)點的數(shù)量。Guo等人將O.Shanker提出的體積維數(shù)進行了進一步改進:首先任選節(jié)點i為中心節(jié)點并設定盒子長度為r, 將r范圍內(nèi)覆蓋到的節(jié)點數(shù)量與網(wǎng)絡節(jié)點總數(shù)間的比值定義為節(jié)點i的密度,然后遍歷網(wǎng)絡中的所有節(jié)點為中心節(jié)點,計算得到給定盒子長度r下的平均密度,記為〈ρ(r)〉,通過對一些實際無權(quán)網(wǎng)絡的實證分析,Guo等人發(fā)現(xiàn)〈ρ(r)〉與r之間存在一定的冪律關系[16]:

〈ρ(r)〉?krdf

(1)

其中,k為實數(shù),df為網(wǎng)絡的體積維數(shù)。Guo等人是從網(wǎng)絡密度〈ρ(r)〉和測量尺度之間的冪律關系來考察網(wǎng)絡的分形特征,本質(zhì)上,〈ρ(r)〉反應的是特定長度的盒子對網(wǎng)絡的一種覆蓋能力。Wei等人[17]則將每一盒子長度下覆蓋到的節(jié)點度和的平均值作為考察對象,從度體積的角度研究了無權(quán)網(wǎng)絡的分形特性,發(fā)現(xiàn)無權(quán)分形網(wǎng)絡存在如下關系式:

VD(r)?kdrdd

(2)

其中,VD(r)表示盒子半徑為r時所覆蓋到的節(jié)點的度和平均值,kd為常數(shù)值,dd為體積維數(shù)。這些不同的方法從不同的角度度量了無權(quán)網(wǎng)絡的分形特性。并且,盒長r的賦值規(guī)則均是從1開始逐次加1直到等于網(wǎng)絡的直徑。

2 基于節(jié)點強度的加權(quán)網(wǎng)絡體積維數(shù)

2.1 算法思想

在加權(quán)網(wǎng)絡中,節(jié)點的強度是一個基礎但十分重要的統(tǒng)計量。網(wǎng)絡中任一節(jié)點i的強度可由式(3)計算[19-20]

(3)

其中,Ni為節(jié)點i的鄰居節(jié)點的集合,wij為連接節(jié)點i和節(jié)點j的邊的權(quán)重值。節(jié)點的強度既包含了節(jié)點度的信息也包含了與該節(jié)點相連的邊權(quán)的信息,是節(jié)點局域信息的一種綜合表達方式。并且,不同強度值的節(jié)點也體現(xiàn)了網(wǎng)絡節(jié)點間的差異性。

和無權(quán)網(wǎng)絡相比,加權(quán)網(wǎng)絡最突出的特點是連邊強度的異質(zhì)性,而正是這種異質(zhì)性使得加權(quán)網(wǎng)絡中任意兩個節(jié)點間的距離定義與無權(quán)網(wǎng)絡中不一致。目前如何通過網(wǎng)絡權(quán)重值來計算節(jié)點間的距離并無統(tǒng)一的標準,最常用的方法是Dijkstra算法,具體描述為

(4)

或者是

(5)

其中,τ為節(jié)點i和節(jié)點j之間所有相連路徑的集合。式(4)表示網(wǎng)絡權(quán)重為相異權(quán)的情況,式(5)表示網(wǎng)絡權(quán)重為相似權(quán)的情況。但是,由式(4)或式(5)計算出的節(jié)點間距離值通常較小,表明網(wǎng)絡的直徑也很小,甚至有些實際加權(quán)網(wǎng)絡的直徑小于1。這說明當盒長設置為1時即可將網(wǎng)絡中的所有的節(jié)點覆蓋,因此針對無權(quán)網(wǎng)絡的盒子長度賦值規(guī)則并不完全適用于加權(quán)網(wǎng)絡。文獻[13]提出的針對加權(quán)網(wǎng)絡的盒子長度賦值規(guī)則能很好地解決這一問題,其核心思想是摒棄習慣上盒子長度為整數(shù)的想法,通過對直接相連的節(jié)點間距離值進行累加來給盒子長度賦值。受這種思想的啟發(fā),本文以不同盒長r下覆蓋到的節(jié)點強度和來定義加權(quán)網(wǎng)絡體積維中“體積”的概念,從強度體積的角度來考察加權(quán)網(wǎng)絡的分形特性。

2.2 算法步驟

按照強度體積維的定義,算法設計如下:

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

步驟2計算G中所有節(jié)點的強度值。

步驟3隨機選擇節(jié)點i為中心節(jié)點,計算到節(jié)點i的距離小于r的所有節(jié)點的強度和,記為ViS(r)。

步驟4遍歷網(wǎng)絡中的所有節(jié)點,計算節(jié)點強度和的平均值,記為VS,數(shù)值上有：

(6)

步驟5分別設置盒子長度r=d1+d2,r=d1+d2+d3,r=d1+d2+d3+…dn,重復步驟3和4，直到r大于網(wǎng)絡的直徑，統(tǒng)計出每個r所對應的VS(r)。

步驟6擬合lnVS(r)～lnr的直線,直線的斜率值即為強度體積維數(shù)值ds。

3 實驗結(jié)果及分析

本節(jié)分別利用強度體積維數(shù)來度量兩類構(gòu)造的加權(quán)網(wǎng)絡的分形特性及3個實際加權(quán)網(wǎng)絡的分形特性。并在對實際網(wǎng)絡的分形分析中,將分析結(jié)果與利用盒維數(shù)得到的結(jié)果進行對比。

3.1 對構(gòu)造網(wǎng)絡的分析

謝爾賓斯基加權(quán)分形網(wǎng)絡和康托三角塵加權(quán)分形網(wǎng)絡是由Carletti等人提出[21],由迭代函數(shù)系統(tǒng)(Iterated Function Systems)生成。這兩類網(wǎng)絡的生成過程和自相似維數(shù)(也稱豪斯多夫維數(shù))由兩個主要的參數(shù)決定,分別是圖形復制數(shù)目s(s>1)以及變化比例因子f(0

(7)

為了構(gòu)造謝爾賓斯基加權(quán)分形網(wǎng)絡,初始網(wǎng)絡設置為單個節(jié)點,然后根據(jù)參數(shù)s和f的值依次生成下一代網(wǎng)絡。如圖1表示s=3,f=1/2的謝爾賓斯基加權(quán)網(wǎng)絡的生成過程,其中G0由單個節(jié)點構(gòu)成,將G0復制三次并用一個新的節(jié)點通過權(quán)重值為“1”的邊連接起來得到G1,如此重復,后一次的邊權(quán)重值變?yōu)榍耙淮蔚摹?/2”,易知其自相似維數(shù)為lg3/lg2≈1.585 0?？低腥菈m加權(quán)分形網(wǎng)絡的生成過程與此類似。如圖2表示s=4,f=1/5的康托三角塵加權(quán)分形網(wǎng)絡的生成過程,其中初始網(wǎng)絡G0由一個三角形組成，將G0復制4次然后用一個新的節(jié)點通過權(quán)重值為“1”的邊連接起來得到G1,如此重復,后一次的邊權(quán)重值變?yōu)榍耙淮蔚摹?/5”,易知其自相似維數(shù)為lg4/lg5≈0.861 3。

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

s=4,f=1/5圖2 康托三角塵加權(quán)網(wǎng)絡生成過程Fig.2 The growth process of Cantor dust weighted networks

對于謝爾賓斯基加權(quán)網(wǎng)絡,首先考慮s=3,f=1/2和s=3,f=1/3兩種情況?？紤]到計算機處理能力有限,這里只生成第八代謝爾賓斯基加權(quán)網(wǎng)絡,記為G8。G8具有9 841個節(jié)點和9 837條邊。當s=3,f=1/2時,邊的權(quán)重值分為1 ,1/2, 1/4, 1/8, 1/16,1/32,1/64,1/128八類,當s=3,f=1/3時,邊的權(quán)重值分為1, 1/3, 1/9,1/27,1/81, 1/243,1/729,1/2 187八類。由于謝爾賓斯基加權(quán)網(wǎng)絡的邊權(quán)重值并無特殊的物理含義,因此可直接將邊權(quán)重值視為連接這兩個節(jié)點的距離值。當s=3,f=1/2時,分別設置盒子長度r為1/128, 1/128+1/64,…,1/128+1/64+1/32+1/16+1/8+1/4+1/2+1,然后計算相應盒子長度下節(jié)點強度和的平均值VS(r),結(jié)果如圖3a所示。同理設置s=3,f=1/3時的盒子長度并計算相應盒子長度下節(jié)點強度和的平均值,結(jié)果如圖3b所示。

對于康托三角塵加權(quán)網(wǎng)絡,這里只生成第六代網(wǎng)絡,其具有13 653個節(jié)點和17 748條邊。類似地,首先考慮s=4,f=1/2和s=4,f=1/3兩種情況,結(jié)果分別如圖4a和圖4b所示。

s=3圖3 第八代謝爾賓斯基加權(quán)網(wǎng)絡的分形特性分析Fig.3 The fractal property analysis of the eighth generation of Sierpinski weighted networks

s=4圖4 第六代康托三角塵加權(quán)網(wǎng)絡的分形特性分析Fig.4 The fractal property analysis of the sixth generation of Cantor dust weighted networks

從圖3和圖4可以看出,無論是謝爾賓斯基加權(quán)網(wǎng)絡還是康托三角塵加權(quán)網(wǎng)絡,兩種情況下盒子長度與相應的節(jié)點強度和的平均值均能很好地擬合成一條直線。謝爾賓斯基加權(quán)網(wǎng)絡擬合直線的斜率值分別為1.398和0.946,與理論計算的自相似維數(shù)值1.585 0和1相差不大?？低腥菈m加權(quán)網(wǎng)絡擬合直線的斜率值分別為1.764和1.181,同樣與理論計算的自相似維數(shù)值2和1.262相差不大。這初步表明了強度體積維數(shù)在加權(quán)網(wǎng)絡分形分析上的有效性。

為了進一步驗證強度體積維數(shù)的有效性,在謝爾賓斯基加權(quán)網(wǎng)絡中,令圖形復制數(shù)目s=3,然后分別設置變化比例因子f=1/4,1/5,1/6,1/7,1/8,1/9,計算對應的強度體積維數(shù)值,并與理論值進行比較。在康托三角塵加權(quán)網(wǎng)絡中,令圖形復制數(shù)目s=4,然后分別設置變化比例因子f=1/4,1/5,1/6,1/7,1/8,1/9,計算對應的強度體積維數(shù)值,并與理論值進行比較。結(jié)果如表1和表2所示。

表1 s=3時,不同f值的謝爾賓斯基網(wǎng)絡對應的強度體積維數(shù)與理論維數(shù)Tab.1 The volume dimensions and the theoretical dimensions of Sierpinski weighted networks with s=3 and different values of f

表2 s=4時,不同f值的康托三角塵網(wǎng)絡對應的強度體積維數(shù)與理論維數(shù)Tab.2 The volume dimensions and the theoretical dimensions of Cantor dust weighted networks with s=3 and different values of f

從表1和表2可以看出,當變化比例因子f取不同值時,謝爾賓斯基加權(quán)網(wǎng)絡和康托三角塵加權(quán)網(wǎng)絡的強度體積維數(shù)值與理論計算的維數(shù)值十分接近,這充分說明了強度體積維數(shù)在分析構(gòu)造加權(quán)網(wǎng)絡分形特性時的有效性。強度體積維數(shù)和理論的分形維數(shù)在數(shù)值上并不會嚴格相等,這是因為二者具有不同的定義,是從兩個不同的角度對同一個分形體的分形特征進行考察。而不同定義的分形維數(shù)具有的性質(zhì)差別可能很大,即使是對很“規(guī)則”的分形體,不同定義的分形維數(shù)也不能給出相同的維數(shù)值[22],這也是強度體積維數(shù)和理論分形維數(shù)在數(shù)值結(jié)果上不會嚴格相等的重要原因。

3.2 對實際網(wǎng)絡的分析

對構(gòu)造加權(quán)網(wǎng)絡的分形分析結(jié)果表明了強度體積維數(shù)的有效性,進一步地,利用強度體積維數(shù)分析3個更具代表性的實際加權(quán)網(wǎng)絡的分形特性。為對照研究,這里選取與文獻[13]中一致的網(wǎng)絡數(shù)據(jù),分別是Newman科學家合作網(wǎng)絡[23],美國航空網(wǎng)絡(數(shù)據(jù)源:http://vlado.fmf.unilj.si/pub/networks/data/)以及線蟲神經(jīng)網(wǎng)絡[1]。這3個實際網(wǎng)絡的盒維數(shù)在文獻[13]中已計算得到。

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

(8)

美國航空網(wǎng)絡具有306個節(jié)點和2 126條邊,其中節(jié)點表示機場,邊表示兩個機場間存在航班。網(wǎng)絡的權(quán)重值是指定期航班的客運量(單位:百萬人次/年)。顯然,當權(quán)重值越大時,表示兩個機場關系密切,距離就越近(這里的距離并非指兩個機場之間的地理距離),因此加權(quán)美國航空網(wǎng)絡的權(quán)重類型也為相似權(quán)。根據(jù)式(5)求得網(wǎng)絡中任意兩個節(jié)點間的距離值后發(fā)現(xiàn)網(wǎng)絡的直徑為0.96。若采用傳統(tǒng)的盒子長度賦值思想顯然無法利用強度體積維數(shù)分析該網(wǎng)絡的分形特性。因此必須采用新的盒子長度賦值思想,分析結(jié)果如圖5b所示。通過擬合計算得到直線的斜率值為0.947,即加權(quán)美國航空網(wǎng)絡的強度體積維數(shù)為0.947。

線蟲神經(jīng)網(wǎng)絡具有306個節(jié)點和2 148條邊,節(jié)點表示神經(jīng)元,邊表示神經(jīng)元之間的連接,邊的權(quán)重值由神經(jīng)元之間的連接強度決定。當連接強度越大時權(quán)重值也越大,表明兩個神經(jīng)元間的關系越密切,距離就越近,因此加權(quán)線蟲神經(jīng)網(wǎng)絡的權(quán)重類型仍然是相似權(quán)。利用強度體積維數(shù)分析加權(quán)線蟲神經(jīng)網(wǎng)絡分形特性的結(jié)果如圖5c所示。通過擬合計算得到直線的斜率值為1.088,即加權(quán)線蟲神經(jīng)網(wǎng)絡的強度體積維數(shù)為1.088。

圖5 強度體積維分析實際加權(quán)網(wǎng)絡Fig.5 Fractal scaling analysis of real-world networks by the volume dimension method

從圖5可以看出,當利用強度體積維數(shù)分析上述3個實際加權(quán)網(wǎng)絡的分形特性時,這3個實際加權(quán)網(wǎng)絡均在一定的尺度范圍內(nèi)表現(xiàn)出分形特性。強度體積維數(shù)的值均是在此尺度范圍內(nèi)通過對統(tǒng)計點進行線性擬合得到。更進一步地,采用文獻[13]提出的BCANW算法分析上述3個加權(quán)網(wǎng)絡的分形特性,并將分析結(jié)果與利用強度體積維數(shù)得到的結(jié)果進行對比。采用BCANW算法分析的結(jié)果如圖6所示,對比結(jié)果如表3所示。

表3 強度體積維數(shù)與盒維數(shù)對比Tab.3 The results comparison between the volume dimensions and the box dimensions

從表3對兩種維數(shù)的比較中可以看出,對于不同的實際網(wǎng)絡,兩個維數(shù)值的差異性表現(xiàn)差別很大。 其中美國航空網(wǎng)絡的強度體積維數(shù)和盒維數(shù)差別最小,差值為0.128 1。其次為線蟲神經(jīng)網(wǎng)絡,差值為0.303。最后為科學家合作網(wǎng)絡,差值達到0.703。強度體積維數(shù)與盒子覆蓋法的實質(zhì)都是在給定的盒子長度下去覆蓋網(wǎng)絡節(jié)點,不同之處在于強度體積維是以一個節(jié)點為中心節(jié)點然后以r為半徑覆蓋,每次覆蓋到的強度體積是一個確定的值,而在盒子覆蓋法中尋找覆蓋整個網(wǎng)絡所需的最少盒子數(shù)量是一個NP完全問題,無法得到一個精確的值,這也是導致實際網(wǎng)絡的強度體積維數(shù)值與盒維數(shù)值不一致的主要原因。

圖6 BCANW算法分析實際加權(quán)網(wǎng)絡Fig.6 Fractal scaling analysis of real-world networks by BCANW

在對實驗數(shù)據(jù)(lnr,lnVS(r))線性擬合時,本文采用的方法是最小二乘擬合法,其實質(zhì)是通過最小化誤差的平方和來尋找數(shù)據(jù)點的最佳函數(shù)匹配。為了考察直線的擬合效果,這里考慮最小二乘擬合法的均方誤差值Q,定義為

(9)

表4 強度體積維數(shù)和盒維數(shù)擬合結(jié)果對比Tab.4 The fitting results comparison between the volume dimensions and the box dimensions

從表4可以看出,對于科學家合作網(wǎng)絡和美國航空網(wǎng)絡,強度體積維數(shù)和盒維數(shù)計算過程中對應均方誤差值都比較小,利用這兩種維數(shù)均能發(fā)現(xiàn)其具有分形特性。對于線蟲神經(jīng)網(wǎng)絡,強度體積維數(shù)計算過程中對應的均方誤差值較小,為0.436 8,而盒維數(shù)計算過程中對應的均方誤差值則達到0.735 0,接近于1,從圖6c中也能發(fā)現(xiàn)其數(shù)據(jù)點較為分散,這說明加權(quán)線蟲神經(jīng)網(wǎng)絡的分形特性用盒維數(shù)不易度量出。

4 結(jié)論

本文以給定盒子長度下覆蓋到的節(jié)點強度和來定義加權(quán)網(wǎng)絡體積維數(shù)中“體積”的概念,提出了基于節(jié)點強度的加權(quán)網(wǎng)絡體積維數(shù)概念。對兩類構(gòu)造的加權(quán)分形網(wǎng)絡和3個實際加權(quán)網(wǎng)絡的分析結(jié)果表明強度體積維數(shù)能夠較好地度量加權(quán)網(wǎng)絡的分形特性。此外,在對實際加權(quán)網(wǎng)絡的分形分析中,同一網(wǎng)絡的強度體積維數(shù)值與盒維數(shù)值并不一致。這主要是因為在盒子覆蓋法中,尋找給定盒子長度下覆蓋網(wǎng)絡所需的最小盒子數(shù)量是一個NP完全問題,只能盡可能地找到最優(yōu)解。而強度體積維在給定盒子長度下覆蓋到的強度體積和是一個確定的值,有效地避免了NP完全問題。