吳 鋒， 張 勝， 藍文祥， 劉厚忠

（南昌航空大學 信息工程學院，南昌 330063）

引 言

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

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

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

1.1 節(jié)點強度

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

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

1.2 邊權(quán)

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

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

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

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

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

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

2.1 算法思想

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

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

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

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

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

2.2 算法步驟

S IDANw算法詳細步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 s =3， Sierpinski 不同 f 值對應的強度信息維數(shù)與理論維數(shù)

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

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

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

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

3.2 對實際加權(quán)網(wǎng)絡的分形分析

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

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

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

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

從表3 可以看出BCANw，IDANw以 及S IDANw所求解出的維數(shù)很接近。對于演員合作網(wǎng)絡，分別為1.169，1.148 和1.185。對于美國航空網(wǎng)絡，分別為1.174，1.182 和1.168。對于科學家合作網(wǎng)絡，分別為1.763，1.778 和1.784。從圖3 和表4 可知這3 個算法都能度量這3 個實際加權(quán)網(wǎng)絡的分形特性，但是本文算法的擬合誤差和擬合效果比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 個真實網(wǎng)絡的分形特性

4 結(jié) 論

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

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

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

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