基于強(qiáng)度信息維數(shù)的加權(quán)網(wǎng)絡(luò)分形特性分析

吳 鋒， 張 勝， 藍(lán)文祥， 劉厚忠

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

引 言

復(fù)雜系統(tǒng)可以通過復(fù)雜網(wǎng)絡(luò)來表示，復(fù)雜網(wǎng)絡(luò)能對(duì)復(fù)雜系統(tǒng)進(jìn)行較好的刻畫和描述，一直受到人們的廣泛關(guān)注[1]。復(fù)雜網(wǎng)絡(luò)是研究復(fù)雜性的一種優(yōu)秀的數(shù)學(xué)模型，被應(yīng)用于各種學(xué)科領(lǐng)域[2]。研究復(fù)雜網(wǎng)絡(luò)的拓?fù)涮卣鲗?duì)理解網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)動(dòng)態(tài)行為之間的關(guān)系具有重要意義。1998 年和1999年兩篇開創(chuàng)性的文章分別揭了復(fù)雜網(wǎng)絡(luò)的小世界[3]和無標(biāo)度特性[4]，這兩個(gè)特性被認(rèn)為是復(fù)雜網(wǎng)絡(luò)的兩個(gè)基本特性。隨著復(fù)雜網(wǎng)絡(luò)分形特性研究的興起，源于分形幾何的分形維數(shù)成為度量復(fù)雜網(wǎng)絡(luò)的新研究熱點(diǎn)，分形特性是復(fù)雜網(wǎng)絡(luò)繼小世界特性和無標(biāo)度特性之后的第三大拓?fù)涮匦訹1]。分形維數(shù)是衡量復(fù)雜網(wǎng)絡(luò)分形特性最基本也是最重要的量，它常被看成是網(wǎng)絡(luò)評(píng)價(jià)指標(biāo)[5-7]。

2007 年，Song 等[8]基于盒子覆蓋法提出了一種適用于復(fù)雜網(wǎng)絡(luò)的貪心著色盒覆蓋法，該算法將盒覆蓋問題轉(zhuǎn)換成了圖論中點(diǎn)的著色問題，此算法因?yàn)楹?jiǎn)單且易于操作而被廣泛應(yīng)用于計(jì)算復(fù)雜網(wǎng)絡(luò)的分形維數(shù)。Wei 等[9]考慮到覆蓋盒子中節(jié)點(diǎn)數(shù)量上的差異提出了復(fù)雜網(wǎng)絡(luò)信息維數(shù)法。Shanker等[10]最早提出了復(fù)雜網(wǎng)絡(luò)體積維數(shù)法。受Shanker等的啟發(fā)，Wei 等[11]考慮到節(jié)點(diǎn)度的信息，提出了復(fù)雜網(wǎng)絡(luò)度體積維數(shù)法。Lacasa 等[12]提出了一種計(jì)算復(fù)雜網(wǎng)絡(luò)關(guān)聯(lián)維數(shù)的方法，該算法僅適用于坐標(biāo)空間中的網(wǎng)絡(luò)，Wang 等[13]將這一方法推廣用于研究平面網(wǎng)絡(luò)中的關(guān)聯(lián)維數(shù)。上述方法都是針無權(quán)網(wǎng)絡(luò)，對(duì)加權(quán)網(wǎng)絡(luò)并不完全適用。受貪心著色盒覆蓋法的啟發(fā)，Wei 等[14]提出了適用于加權(quán)網(wǎng)絡(luò)的盒子覆蓋法(Box Covering Algorithm for Weighted Networks，BCANw)。黃等[15]受BCANw的啟發(fā)，提出了加權(quán)網(wǎng)絡(luò)體積維數(shù)法。Wen 等[2]受BCANw的啟發(fā)，提出了加權(quán)網(wǎng)絡(luò)信息維數(shù)法(Information Dimension Algorithm for Weighted Networks，IDANw)。受到BCANw和IDANw的啟法，本文提出了一種分析加權(quán)網(wǎng)絡(luò)分形特性的強(qiáng)度信息維數(shù)法。

1 加權(quán)網(wǎng)絡(luò)常用統(tǒng)計(jì)量

1.1 節(jié)點(diǎn)強(qiáng)度

節(jié)點(diǎn)強(qiáng)度是加權(quán)網(wǎng)絡(luò)中比較常用的統(tǒng)計(jì)量之一，對(duì)于一個(gè)給定的加權(quán)網(wǎng)絡(luò)G， 節(jié)點(diǎn)i的強(qiáng)度記為si，si定義如下：

其中wij是 網(wǎng)絡(luò)G中 節(jié)點(diǎn)i和 節(jié)點(diǎn)j之間邊的權(quán)重值，Vi表示的是節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)組成的集合。節(jié)點(diǎn)強(qiáng)度和節(jié)點(diǎn)度的概念是密切相關(guān)的，實(shí)際上當(dāng)wij≡1時(shí)，節(jié)點(diǎn)強(qiáng)度就退化成了節(jié)點(diǎn)的度。

1.2 邊權(quán)

在加權(quán)網(wǎng)絡(luò)中邊權(quán)的定義有兩種[16]：

1）相似權(quán)。邊的權(quán)重值越大表示兩節(jié)點(diǎn)間的相關(guān)性越強(qiáng)，節(jié)點(diǎn)間的距離也就越近。

2）相異權(quán)。相異權(quán)和相似權(quán)相反，邊的權(quán)重值越大表示兩節(jié)點(diǎn)的相關(guān)性越弱，節(jié)點(diǎn)間的距離就越遠(yuǎn)。

由于加權(quán)網(wǎng)絡(luò)中邊的權(quán)重有兩種含義，從而導(dǎo)致節(jié)點(diǎn)間邊權(quán)值的定義更為復(fù)雜。本文將節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離記為dij，di j定義如下：

其中：i,h,k,l,j表 示節(jié)點(diǎn)序號(hào)，wih表示節(jié)點(diǎn)i和節(jié)點(diǎn)h間連邊的權(quán)重值。這里引入了參數(shù)q來區(qū)分相似權(quán)和相異權(quán)，q=1表明網(wǎng)絡(luò)權(quán)重是相異權(quán)，q=?1表明網(wǎng)絡(luò)權(quán)重是相似權(quán)。

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

2.1 算法思想

Wei 等[9]最早提出了BCANw，BCANw將網(wǎng)絡(luò)中所有的邊權(quán)值從小到大排序，對(duì)排序后的邊權(quán)值從最小值開始不斷累加得到盒子尺寸。Wen 等[2]受BCANw的啟發(fā)，提出了一種適用于加權(quán)網(wǎng)絡(luò)的信息維數(shù)法(IDANw)，IDANw只是簡(jiǎn)單的將無權(quán)網(wǎng)絡(luò)中的信息維數(shù)法結(jié)合了BCANw中盒子尺寸的變換規(guī)則，該算法沒有考慮加權(quán)網(wǎng)絡(luò)本身的固有屬性，依然是將盒子包含信息的概率定義為盒子中節(jié)點(diǎn)數(shù)與網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)的比值。實(shí)際上，在加權(quán)網(wǎng)絡(luò)中，節(jié)點(diǎn)間的連邊有真實(shí)的含義。在IDANw的基礎(chǔ)上，本文考慮到覆蓋盒子中節(jié)點(diǎn)間連邊的權(quán)重信息，重新定義盒子包含信息的概率，提出了一種分析加權(quán)網(wǎng)絡(luò)分形特性的強(qiáng)度信息維數(shù)法(Strength Information Dimension Algorithm for Weighted Networks，SIDANw)。

實(shí)際上節(jié)點(diǎn)強(qiáng)度si包含了節(jié)點(diǎn)的度以及節(jié)點(diǎn)相連的邊權(quán)wi j兩方面的特征，是節(jié)點(diǎn)局部信息的一種綜合表達(dá)方式。這說明用盒子中所有節(jié)點(diǎn)的強(qiáng)度和來衡量盒子包含信息的信息量是合理的。本文重新定義盒子i包含信息的概率記為pi，pi定義如下：

其中Hi表 示盒子i中 所有節(jié)點(diǎn)組成的集合，Sall表示在整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的強(qiáng)度總和。根據(jù)式(4)以及香農(nóng)信息熵的定義計(jì)算給定盒子尺寸r下網(wǎng)絡(luò)的信息熵I(r)，I(r)如下：

其中N(r)表 示盒子尺寸r時(shí)覆蓋網(wǎng)絡(luò)所需的最小盒子數(shù)。綜合式(3)和式(4)，計(jì)算復(fù)雜網(wǎng)絡(luò)的強(qiáng)度信息維數(shù)ds，ds如下：

在計(jì)算實(shí)際網(wǎng)絡(luò)強(qiáng)度信息維數(shù)的過程中，很難實(shí)現(xiàn)盒子尺寸r→0， 通常做法是擬合I(r)與 lnr的關(guān)系，若呈線性關(guān)系，則直線斜率的絕對(duì)值就是網(wǎng)絡(luò)的強(qiáng)度信息維數(shù)ds。

2.2 算法步驟

S IDANw算法詳細(xì)步驟如下：

步驟1 給定加權(quán)網(wǎng)絡(luò)G， 將G中邊的權(quán)重值按從小到大順序排序，排序結(jié)果記為[l1,l2,···,ln]。

步驟2 求解網(wǎng)絡(luò)G中任意兩節(jié)點(diǎn)間的距離值di j，網(wǎng)絡(luò)直徑D=max(dij)，設(shè)置盒子的初始尺寸r=l1。

步驟3 給定盒子尺寸r，利用改進(jìn)的貪心著色算法求解網(wǎng)絡(luò)G的最小覆蓋。

步驟4 對(duì)覆蓋所得的盒子進(jìn)行逐一編號(hào)，由式(4)計(jì)算盒子i包含信息的概率pi(r)，基于這組概率值，根據(jù)式(5)計(jì)算出盒子尺寸r下網(wǎng)絡(luò)G的信息熵I(r)。

步驟5 分別設(shè)置盒子尺寸r=l1+l2,r=l1+l2+l3,r=l1+l2+l3+l4+···，重復(fù)步驟3 和步驟4，直到盒子尺寸r≥D， 記錄每個(gè)盒子尺寸r對(duì)應(yīng)的信息熵I(r)。

步驟6 在直角坐標(biāo)系中刻畫出 ln(r)與I(r)對(duì)應(yīng)的數(shù)據(jù)點(diǎn)，通過最小二乘法擬合實(shí)驗(yàn)數(shù)據(jù)，若存在線性關(guān)系，表明G具有分形特性，直線斜率的絕對(duì)值就是網(wǎng)絡(luò)G的 強(qiáng)度信息維數(shù)ds。

實(shí)際上，步驟3 中改進(jìn)的貪心著色算法是針對(duì)加權(quán)網(wǎng)絡(luò)中BCANw的改進(jìn)算法，該算法推廣了無權(quán)網(wǎng)絡(luò)中改進(jìn)的貪心著色算法的思路，在無權(quán)網(wǎng)絡(luò)中，節(jié)點(diǎn)的著色過程主要是考慮到了對(duì)偶網(wǎng)絡(luò)中節(jié)點(diǎn)度的信息，對(duì)于孤立節(jié)點(diǎn)，選擇與對(duì)偶網(wǎng)絡(luò)中節(jié)點(diǎn)度最大的節(jié)點(diǎn)相同的顏色。而在加權(quán)網(wǎng)絡(luò)中，本文考慮網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的強(qiáng)度屬性，將對(duì)偶網(wǎng)絡(luò)中的節(jié)點(diǎn)按照節(jié)點(diǎn)強(qiáng)度的大小順序進(jìn)行編號(hào)，節(jié)點(diǎn)強(qiáng)度大的節(jié)點(diǎn)優(yōu)先編號(hào)，著色過程中按照編號(hào)順序依次著色，對(duì)于孤立節(jié)點(diǎn)，選擇與網(wǎng)絡(luò)中節(jié)點(diǎn)強(qiáng)度最大節(jié)點(diǎn)相同的顏色，這種做法同樣可以降低算法的隨機(jī)性，從而讓算法運(yùn)行結(jié)果更加穩(wěn)定。

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

為了驗(yàn)證本文算法的合理性以及可靠性，本文用S IDANw分析兩類構(gòu)造加權(quán)網(wǎng)絡(luò)的分形特性，以及在三個(gè)真實(shí)加權(quán)網(wǎng)絡(luò)中與IDANw和BCANw算法做對(duì)比實(shí)驗(yàn)。

3.1 分析構(gòu)造加權(quán)網(wǎng)絡(luò)的分形特性

加權(quán)分形網(wǎng)絡(luò)的概念是Carletti 等[17]首次提出的，實(shí)際構(gòu)造加權(quán)分形網(wǎng)絡(luò)的過程主要是利用迭代函數(shù)系統(tǒng)。構(gòu)造的加權(quán)分形網(wǎng)絡(luò)的豪斯多夫維數(shù)由兩個(gè)參數(shù)共同決定，一個(gè)是復(fù)制數(shù)s，另一個(gè)是比例因子f，其中s，f分別滿足s>0, 0

對(duì)于Cantor Dust 加權(quán)分形網(wǎng)絡(luò)，這里將圖形復(fù)制數(shù)目s設(shè)置為4，第六代Cantor Dust 加權(quán)分形網(wǎng)絡(luò)G6包 含的節(jié)點(diǎn)數(shù)為13 653。這里選用G6做實(shí)驗(yàn)，具體的實(shí)驗(yàn)步驟和Sierpinski 加權(quán)分形網(wǎng)絡(luò)類似，最終實(shí)驗(yàn)結(jié)果如圖1b 所示。

圖1a 和圖1b 中橫坐標(biāo)表示盒子尺寸的對(duì)數(shù)值，縱坐標(biāo)表示的是給定盒子尺寸下的信息熵。從圖1 可以看出，無論是Sierpinski 還是Cantor Dust加權(quán)分形網(wǎng)絡(luò)，本文算法在不同的比例因子f下，盒子尺寸的對(duì)數(shù)值與信息熵呈現(xiàn)很好的線性關(guān)系。

圖1 不同f 值下Sierpinski 和Cantor Dust 加權(quán)網(wǎng)絡(luò)的分形特性分析

當(dāng)s=3時(shí) ，給定f的值，Sierpinski 網(wǎng)絡(luò)的理論分形維數(shù)值可由式(6)計(jì)算：

當(dāng)s=4時(shí) ，給定f的值，Cantor Dust 網(wǎng)絡(luò)的理論分形維數(shù)值可由式(6)計(jì)算：

圖1 擬合所得的強(qiáng)度信息維數(shù)ds以及由式(7)和式(8)所求的Sierpinski 和Cantor Dust 加權(quán)網(wǎng)絡(luò)的理論維數(shù)df如表1 和表2 所示。

表1 s =3， Sierpinski 不同 f 值對(duì)應(yīng)的強(qiáng)度信息維數(shù)與理論維數(shù)

表2 s =4， Cantor Dust 不同 f 值對(duì)應(yīng)的強(qiáng)度信息維數(shù)與理論維數(shù)

為了更加直觀看到本文算法的實(shí)驗(yàn)效果，圖2給出了不同f值下兩類構(gòu)造網(wǎng)絡(luò)的理論維數(shù)曲線和實(shí)際計(jì)算的強(qiáng)度信息維數(shù)。

圖2 Sierpinski 和Cantor Dust 在不同 f 值下的理論曲線和強(qiáng)度信息維數(shù)

表1 和表2 以及圖2 可看出，對(duì)于Sierpinski和Cantor Dust 加權(quán)分形網(wǎng)絡(luò)，當(dāng)給定比例因子f的值時(shí)，S IDANw計(jì)算出的強(qiáng)度信息維數(shù)與網(wǎng)絡(luò)的理論維數(shù)十分接近，這表明本文算法可以很好地度量構(gòu)造加權(quán)網(wǎng)絡(luò)的分形特性。

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

為進(jìn)一步驗(yàn)證本文算法的合理性，本文選擇了3 個(gè)真實(shí)的加權(quán)網(wǎng)絡(luò)來做實(shí)驗(yàn)。3 個(gè)真實(shí)網(wǎng)絡(luò)分別是Lemis 演員合作網(wǎng)絡(luò)，USAir 美國(guó)航空網(wǎng)絡(luò)以及Netscience 科學(xué)家合作網(wǎng)絡(luò)。演員合作網(wǎng)絡(luò)包含77 個(gè)節(jié)點(diǎn)和254 條邊?？茖W(xué)家合作網(wǎng)絡(luò)包含1589 個(gè)節(jié)點(diǎn)和2742 條邊。美國(guó)航空網(wǎng)絡(luò)包含332 個(gè)節(jié)點(diǎn)和2126 條邊。

為了更加直觀的看到實(shí)驗(yàn)效果，將S IDANw與BCANw和IDANw算法所得的結(jié)果進(jìn)行對(duì)比。以上3 個(gè)實(shí)際網(wǎng)絡(luò)在不同算法下的擬合效果如圖3a～圖3c 所示。

BCANw，IDANw和S IDANw計(jì)算所得的分形維數(shù)分別記為db，di，ds，計(jì)算結(jié)果如表3。

BCANw，IDANw和S IDANw計(jì)算所得的均方誤差分別記為Qb，Qi，Qs，計(jì)算結(jié)果如表4。

從表3 可以看出BCANw，IDANw以 及S IDANw所求解出的維數(shù)很接近。對(duì)于演員合作網(wǎng)絡(luò)，分別為1.169，1.148 和1.185。對(duì)于美國(guó)航空網(wǎng)絡(luò)，分別為1.174，1.182 和1.168。對(duì)于科學(xué)家合作網(wǎng)絡(luò)，分別為1.763，1.778 和1.784。從圖3 和表4 可知這3 個(gè)算法都能度量這3 個(gè)實(shí)際加權(quán)網(wǎng)絡(luò)的分形特性，但是本文算法的擬合誤差和擬合效果比IDANw和BCANw更優(yōu)。

表3 B CANw ， I DANw和S IDANw的擬合結(jié)果

表4 B CANw ， I DANw和S IDANw的擬合誤差

圖3 B CANw ， I DANw和S IDANw分析3 個(gè)真實(shí)網(wǎng)絡(luò)的分形特性

4 結(jié) 論

現(xiàn)實(shí)生活中的網(wǎng)絡(luò)有很多是加權(quán)網(wǎng)絡(luò)，加權(quán)網(wǎng)絡(luò)能更加細(xì)膩地表達(dá)出復(fù)雜系統(tǒng)各單元間的相互關(guān)系，完善有關(guān)加權(quán)網(wǎng)絡(luò)的分形特性分析能夠幫助人們更好的認(rèn)識(shí)復(fù)雜系統(tǒng)，所以本文主要是研究加權(quán)網(wǎng)絡(luò)。

1）針對(duì)現(xiàn)有算法在分析加權(quán)網(wǎng)絡(luò)的分形特性不足之處，提出了相應(yīng)的解決方案；針對(duì)BCANw算法，將無權(quán)網(wǎng)絡(luò)中改進(jìn)貪心著色算法的思路推廣應(yīng)用于BCANw算法，具體做法是對(duì)于對(duì)偶網(wǎng)絡(luò)中的孤立節(jié)點(diǎn)，選擇與網(wǎng)絡(luò)中節(jié)點(diǎn)強(qiáng)度最大節(jié)點(diǎn)相同的顏色，這種做法降低了算法運(yùn)行過程的隨機(jī)性，保證了算法運(yùn)行結(jié)果穩(wěn)定性。

2）針對(duì)IDANw算法未能考慮到盒子中的邊權(quán)信息，提出了一種基于強(qiáng)度信息維數(shù)的加權(quán)網(wǎng)絡(luò)分形分析方法。

3）將該算法運(yùn)用在了二類構(gòu)造加權(quán)網(wǎng)絡(luò)和3 個(gè)實(shí)際加權(quán)網(wǎng)絡(luò)中，實(shí)驗(yàn)結(jié)果表明本文算法能很好地度量加權(quán)網(wǎng)絡(luò)分形特性。