， ，， ，

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

0 引言

復(fù)雜網(wǎng)絡(luò)作為復(fù)雜系統(tǒng)的高度抽象和研究工具,近十幾年來(lái)受到了來(lái)自計(jì)算機(jī)科學(xué)、信息科學(xué)、生物學(xué)、統(tǒng)計(jì)物理學(xué)、社會(huì)學(xué)等眾多不同學(xué)科領(lǐng)域研究人員的廣泛關(guān)注,成為科學(xué)研究的熱點(diǎn)。對(duì)復(fù)雜網(wǎng)絡(luò)拓?fù)湫再|(zhì)的準(zhǔn)確度量對(duì)于復(fù)雜網(wǎng)絡(luò)模型的建立以及復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)行為的研究具有十分重要的意義,因此復(fù)雜網(wǎng)絡(luò)拓?fù)湫再|(zhì)的研究也是復(fù)雜網(wǎng)絡(luò)理論研究的關(guān)鍵。20世紀(jì)末,科學(xué)家們揭示了復(fù)雜網(wǎng)絡(luò)的兩大基本拓?fù)涮匦?小世界特性和無(wú)標(biāo)度特性[1-2]。小世界特性是指網(wǎng)絡(luò)節(jié)點(diǎn)間的平均路徑短且平均聚集系數(shù)高,對(duì)應(yīng)于社交網(wǎng)絡(luò)中的“六度分割”現(xiàn)象。無(wú)標(biāo)度特性則是指網(wǎng)絡(luò)節(jié)點(diǎn)的度分布服從冪律分布,對(duì)應(yīng)于經(jīng)濟(jì)生活中的“馬太效應(yīng)”。隨后,2005年, Song等人開(kāi)創(chuàng)性地將重整化理論和分形理論中的盒子覆蓋法推廣應(yīng)用于復(fù)雜網(wǎng)絡(luò)的研究,揭示了大量實(shí)際網(wǎng)絡(luò)具有自相似性和分形特性[3],其中自相似性是指網(wǎng)絡(luò)度分布的冪律形式及冪指數(shù)在重整化過(guò)程中保持不變,分形特性則是指覆蓋整個(gè)網(wǎng)絡(luò)所需的最小盒子數(shù)量與盒子長(zhǎng)度呈冪律關(guān)系,即NB(lB)≈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ù)涮匦浴?/p>

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

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

1 前期工作

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

〈ρ(r)〉?krdf

(1)

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

VD(r)?kdrdd

(2)

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

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

2.1 算法思想

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

(3)

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

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

(4)

或者是

(5)

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

2.2 算法步驟

按照強(qiáng)度體積維的定義,算法設(shè)計(jì)如下:

步驟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è)置初始盒長(zhǎng)r=d1。

步驟2計(jì)算G中所有節(jié)點(diǎn)的強(qiáng)度值。

步驟3隨機(jī)選擇節(jié)點(diǎn)i為中心節(jié)點(diǎn),計(jì)算到節(jié)點(diǎn)i的距離小于r的所有節(jié)點(diǎn)的強(qiáng)度和,記為ViS(r)。

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

(6)

步驟5分別設(shè)置盒子長(zhǎng)度r=d1+d2,r=d1+d2+d3,r=d1+d2+d3+…dn,重復(fù)步驟3和4，直到r大于網(wǎng)絡(luò)的直徑，統(tǒng)計(jì)出每個(gè)r所對(duì)應(yīng)的VS(r)。

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

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

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

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

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

(7)

為了構(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ò)的生成過(guò)程,其中G0由單個(gè)節(jié)點(diǎn)構(gòu)成,將G0復(fù)制三次并用一個(gè)新的節(jié)點(diǎn)通過(guò)權(quán)重值為“1”的邊連接起來(lái)得到G1,如此重復(fù),后一次的邊權(quán)重值變?yōu)榍耙淮蔚摹?/2”,易知其自相似維數(shù)為lg3/lg2≈1.585 0。康托三角塵加權(quán)分形網(wǎng)絡(luò)的生成過(guò)程與此類(lèi)似。如圖2表示s=4,f=1/5的康托三角塵加權(quán)分形網(wǎng)絡(luò)的生成過(guò)程,其中初始網(wǎng)絡(luò)G0由一個(gè)三角形組成，將G0復(fù)制4次然后用一個(gè)新的節(jié)點(diǎn)通過(guò)權(quán)重值為“1”的邊連接起來(lái)得到G1,如此重復(fù),后一次的邊權(quán)重值變?yōu)榍耙淮蔚摹?/5”,易知其自相似維數(shù)為lg4/lg5≈0.861 3。

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

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

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

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

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

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

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

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

表1 s=3時(shí),不同f值的謝爾賓斯基網(wǎng)絡(luò)對(duì)應(yīng)的強(qiá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時(shí),不同f值的康托三角塵網(wǎng)絡(luò)對(duì)應(yīng)的強(qiá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可以看出,當(dāng)變化比例因子f取不同值時(shí),謝爾賓斯基加權(quán)網(wǎng)絡(luò)和康托三角塵加權(quán)網(wǎng)絡(luò)的強(qiáng)度體積維數(shù)值與理論計(jì)算的維數(shù)值十分接近,這充分說(shuō)明了強(qiáng)度體積維數(shù)在分析構(gòu)造加權(quán)網(wǎng)絡(luò)分形特性時(shí)的有效性。強(qiáng)度體積維數(shù)和理論的分形維數(shù)在數(shù)值上并不會(huì)嚴(yán)格相等,這是因?yàn)槎呔哂胁煌亩x,是從兩個(gè)不同的角度對(duì)同一個(gè)分形體的分形特征進(jìn)行考察。而不同定義的分形維數(shù)具有的性質(zhì)差別可能很大,即使是對(duì)很“規(guī)則”的分形體,不同定義的分形維數(shù)也不能給出相同的維數(shù)值[22],這也是強(qiáng)度體積維數(shù)和理論分形維數(shù)在數(shù)值結(jié)果上不會(huì)嚴(yán)格相等的重要原因。

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

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

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)

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

線(xiàn)蟲(chóng)神經(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)系越密切,距離就越近,因此加權(quán)線(xiàn)蟲(chóng)神經(jīng)網(wǎng)絡(luò)的權(quán)重類(lèi)型仍然是相似權(quán)。利用強(qiáng)度體積維數(shù)分析加權(quán)線(xiàn)蟲(chóng)神經(jīng)網(wǎng)絡(luò)分形特性的結(jié)果如圖5c所示。通過(guò)擬合計(jì)算得到直線(xiàn)的斜率值為1.088,即加權(quán)線(xiàn)蟲(chóng)神經(jīng)網(wǎng)絡(luò)的強(qiáng)度體積維數(shù)為1.088。

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

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

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

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

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

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

(9)

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

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

4 結(jié)論

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