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

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

1 引言

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

2 水平可視圖算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在本文中，對(duì)于H=0.1所生成的100個(gè)節(jié)點(diǎn)加權(quán)和邊加權(quán)網(wǎng)絡(luò)均利用改進(jìn)的沙箱算法，計(jì)算各個(gè)網(wǎng)絡(luò)的廣義分形維數(shù)D（q），其中q從-10～10，間隔為1，最后對(duì)100個(gè)網(wǎng)絡(luò)的廣義分形維數(shù)取平均值＜D（q）＞，即為H=0.1下分形布朗運(yùn)動(dòng)映射而成的綜合節(jié)點(diǎn)加權(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個(gè)可視網(wǎng)絡(luò)中的一個(gè)，q取0，2，4，6，8，10。

圖2 最后不同q時(shí)的線性擬合

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

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

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

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

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

5 結(jié)語(yǔ)

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

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