基于節(jié)點加權(quán)和邊加權(quán)的重分形研究?

（桂林電子科技大學(xué)認(rèn)知無線電與信息處理教育部重點實驗室 桂林 541004）

1 引言

隨著時代和科技的發(fā)展，復(fù)雜網(wǎng)絡(luò)逐漸衍生成為一門交叉度很高的綜合學(xué)科，涉及到金融學(xué)、社會學(xué)、生態(tài)學(xué)、政治學(xué)、數(shù)學(xué)物理、系統(tǒng)科學(xué)、生物學(xué)等學(xué)科［1～3］，復(fù)雜網(wǎng)絡(luò)的應(yīng)用領(lǐng)域也越來越廣泛，已經(jīng)在購物系統(tǒng)、推薦系統(tǒng)［4］、地球物理、生物醫(yī)療、金融模型［5］、天氣預(yù)測、生物系統(tǒng)［6］、社交網(wǎng)絡(luò)等方面具有非常廣泛和深度的應(yīng)用，復(fù)雜網(wǎng)絡(luò)已經(jīng)成為數(shù)據(jù)科學(xué)的基石［7］，能夠充分揭示各種事物的本質(zhì)和演化規(guī)律［8～13］。復(fù)雜網(wǎng)絡(luò)具有各種各樣的性質(zhì)，其中關(guān)于復(fù)雜網(wǎng)絡(luò)的重分形特性是研究的熱點，引起了眾多學(xué)者的深入研究，目前已經(jīng)有學(xué)者對復(fù)雜網(wǎng)絡(luò)在單獨考慮節(jié)點權(quán)重和邊權(quán)重時所具有的重分形性質(zhì)進(jìn)行研究，但同時綜合了節(jié)點權(quán)重和邊權(quán)重的復(fù)雜網(wǎng)絡(luò)的重分形性質(zhì)則缺少相應(yīng)的研究，本文即是基于水平可視圖算法，利用改進(jìn)的沙箱算法對分形布朗運動時間序列映射而成的同時包含節(jié)點權(quán)重和邊權(quán)重的可視網(wǎng)絡(luò)進(jìn)行計算，探究網(wǎng)絡(luò)的重分形維數(shù)與節(jié)點權(quán)重和邊權(quán)重之間的關(guān)系。

2 水平可視圖算法

目前，將時間序列轉(zhuǎn)化為可視網(wǎng)絡(luò)從而研究復(fù)雜系統(tǒng)的性質(zhì)已經(jīng)成為了眾多研究者的熱點，并且已經(jīng)在股票交易、外匯匯率、能量擴(kuò)散、病情診斷、颶風(fēng)預(yù)測等領(lǐng)域得到了廣泛的應(yīng)用。Lacasa L等［14］提出了自然可視圖（Natural Visibility Graph，NVG）算法，NVG算法指如果時間序列x(tk)中任意兩個節(jié)點i、j之間存在的所有中間節(jié)點均在i、j兩點連接直線之下，則將i、j連接起來，否則i、j之間沒有連接邊，即：

這樣便可將時間序列x(tk)映射成為一個可視網(wǎng)絡(luò)。B.Luque等［15］基于NVG算法提出了水平可視圖（Horizontal Visibility Graph，HVG）算法，即如果時間序列x(tk)中任意兩個節(jié)點i、j之間的所有節(jié)點值均小于x(ti)、x(tj)，則節(jié)點i、j之間存在連接邊，否則不存在，即：

3 改進(jìn)的沙箱算法

目前的研究結(jié)果表明復(fù)雜網(wǎng)絡(luò)主要具有無標(biāo)度、小世界以及自相似三大特性，尤其是自相似特性，目前已經(jīng)成為復(fù)雜網(wǎng)絡(luò)的研究熱點。目前針對揭示復(fù)雜網(wǎng)絡(luò)重分形維數(shù)的算法研究，已經(jīng)得到了越來越多的學(xué)者的關(guān)注。2017年Liu等［16］針對加權(quán)網(wǎng)絡(luò)中不同邊權(quán)重數(shù)量過少時難以計算網(wǎng)絡(luò)分形特性這一弊端，提出了一個提高的盒覆蓋算法，即從網(wǎng)絡(luò)最小權(quán)重值d0到網(wǎng)絡(luò)直徑d等間隔設(shè)置盒子的半徑，然而對于Liu提出的算法，通過一系列計算發(fā)現(xiàn)，Liu所提算法存在大量的計算浪費。因為盒覆蓋算法的最終核心思想是尋找到合適的作為線性擬合區(qū)間的盒子半徑集r并得到相應(yīng)最小覆蓋網(wǎng)絡(luò)所需盒子數(shù)，所以并沒有必要從最小邊權(quán)重值d0到網(wǎng)絡(luò)直徑d設(shè)置線性步長總數(shù)，只需要抓取核心適合于作線性擬合部分的盒子半徑即可。改進(jìn)的算法如下：

1）根據(jù)網(wǎng)絡(luò)規(guī)模設(shè)置采樣節(jié)點個數(shù)，對網(wǎng)絡(luò)的最短路徑矩陣進(jìn)行采樣。

2）對每個采樣節(jié)點與其他所有節(jié)點之間的距離進(jìn)行等間距的采樣。

3）根據(jù)采樣結(jié)果，選擇最短路徑值最集中的區(qū)間作為盒子半徑范圍。

4）在所選擇的半徑范圍內(nèi)等間距設(shè)置間隔，并將此作為各個盒子的半徑以傳統(tǒng)沙箱算法計算網(wǎng)絡(luò)的重分形維數(shù)。

以H=0.1的分形布朗運動時間序列基于HVG算法映射所生成的邊加權(quán)指數(shù)取k=-3的加權(quán)網(wǎng)絡(luò)為模型，將改進(jìn)的盒覆蓋算法與Liu所提出的算法進(jìn)行比較。圖1中，改進(jìn)的算法的盒子半徑是從1～1500，間隔為1，一共1500個盒子半徑，而Liu所提算法以盒子半徑間距為10取一共有69164個用于覆蓋網(wǎng)絡(luò)的盒子半徑。從圖1可以看出，改進(jìn)的算法可以很好地保留最后最適宜進(jìn)行線性擬合的盒子半徑區(qū)間，去掉了頭尾的不必要區(qū)間，將盒子半徑個數(shù)縮小至Liu所提算法的數(shù)十分之一左右，證明了改進(jìn)的算法在保持計算精度的前提下大大地提高了計算的速度。

圖1 改進(jìn)的沙箱算法與Liu所提算法相比較

4 實驗結(jié)果分析

本文中，利用Matlab軟件自帶的“wfbm”函數(shù)生成分形布朗運動時間序列，將Hurst指數(shù)H設(shè)置為0.1，此時的分形布朗運動具有較強(qiáng)的自相似性，節(jié)點總數(shù)N設(shè)置為5000，一共生成100個分形布朗運動時間序列。對于每一個時間序列，利用HVG算法生成相應(yīng)的可視網(wǎng)絡(luò)。

邊權(quán)重定義為相連接的兩個節(jié)點的函數(shù)值之差的絕對值，即：

節(jié)點權(quán)重定義為

在本文中，對于H=0.1所生成的100個節(jié)點加權(quán)和邊加權(quán)網(wǎng)絡(luò)均利用改進(jìn)的沙箱算法，計算各個網(wǎng)絡(luò)的廣義分形維數(shù)D（q），其中q從-10～10，間隔為1，最后對100個網(wǎng)絡(luò)的廣義分形維數(shù)取平均值＜D（q）＞，即為H=0.1下分形布朗運動映射而成的綜合節(jié)點加權(quán)和邊加權(quán)的可視圖網(wǎng)絡(luò)的廣義分形維數(shù)D（q）。圖2為最后ln(＜[M(r)]q-1＞)/(q-1) 與ln(r)進(jìn)行線性擬合，網(wǎng)絡(luò)選自100個可視網(wǎng)絡(luò)中的一個，q取0，2，4，6，8，10。

圖2 最后不同q時的線性擬合

H=0.1時，利用改進(jìn)的沙箱算法，對分形布朗運動基于HVG算法映射而成的節(jié)點加權(quán)和邊加權(quán)的100個可視網(wǎng)絡(luò)計算得到的平均廣義分形維數(shù)＜D（q）＞如圖3所示。與Yu等［17］通過沙箱算法對H=0.1時分形布朗運動映射而成的原始可視網(wǎng)絡(luò)相比較，此時的廣義分形維數(shù)D（q）整體有所增大，但下降趨勢基本保持一致，依然具有明顯的重分形特性。

圖3 同時包含節(jié)點和邊權(quán)重時的廣義分形維數(shù)D（q）

圖4為H=0.1時，分形布朗運動基于HVG算法映射而成的可視網(wǎng)絡(luò)隨邊權(quán)重值變化時，廣義分形維數(shù)D（q）的變化情況，均取自100個網(wǎng)絡(luò)的平均值。從圖4（a）可以觀察到，在-1 ≤k ≤1的范圍內(nèi)，D（q）隨著邊權(quán)重系數(shù)k的增加而增加，在-1 ≤k ≤0.5時，增加部分集中在q＞-3部分，q＜-3部分基本不變；在k從0.5增加到1的過程中，增加部分主要是q＜0部分，q＞0部分保持平穩(wěn)。從圖4（b）可以觀察到在k從1增加到2的過程中，D（q）隨著k的增加而增加，在q＞0部分，則顛倒過來變成隨著k的增加而減小；在k從2增加到3的過程中，D（q）則是隨著k的增加而逐漸減小的，尤其是q＞0的部分，迅速減小至接近于0。

圖4 廣義分形維數(shù)D（q）隨邊權(quán)重變化情況

圖5為節(jié)點權(quán)重變化時D（q）的變化情況。從圖5可以觀察到，此時的廣義分形維數(shù)D（q）隨著k的增加而逐漸減小，但整體的變化情況很小，遠(yuǎn)沒有邊權(quán)重變化時D（q）的變化大，也由此可以說明網(wǎng)絡(luò)的廣義分形維數(shù)D（q）主要與節(jié)點是否被盒子覆蓋有關(guān)，而與節(jié)點本身的權(quán)重值關(guān)系不大。

5 結(jié)語

本文主要通過利用改進(jìn)的沙箱算法，對由H=0.1時的分形布朗運動基于HVG算法映射而成的同時包含節(jié)點權(quán)重和邊權(quán)重的可視網(wǎng)絡(luò)進(jìn)行廣義分形維數(shù)D（q）計算，分析在同時包含節(jié)點權(quán)重和邊權(quán)重的情況時，復(fù)雜網(wǎng)絡(luò)的廣義分形維數(shù)D（q）的變化情況。結(jié)果表明，復(fù)雜網(wǎng)絡(luò)邊權(quán)重對于復(fù)雜網(wǎng)絡(luò)重分形特性的影響很大，且重分形特性的變化與邊權(quán)重系數(shù)的變化之間是不存在線性關(guān)系的，而節(jié)點權(quán)重對于復(fù)雜網(wǎng)絡(luò)的重分形特性的影響則較之邊權(quán)重小很多，可以說基本不受其影響。對于本文中所發(fā)現(xiàn)的這些重分形特性，與其背后所對應(yīng)的網(wǎng)絡(luò)所具有的拓?fù)浣Y(jié)構(gòu)和其他統(tǒng)計特性之間是否存在聯(lián)系與如何定量分析兩者之間的聯(lián)系，值得進(jìn)一步深入研究。

圖5 廣義分形維數(shù)D（q）隨節(jié)點權(quán)重變化情況