基于節點加權和邊加權的重分形研究?

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

1 引言

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

2 水平可視圖算法

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

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

3 改進的沙箱算法

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

1）根據網絡規模設置采樣節點個數，對網絡的最短路徑矩陣進行采樣。

2）對每個采樣節點與其他所有節點之間的距離進行等間距的采樣。

3）根據采樣結果，選擇最短路徑值最集中的區間作為盒子半徑范圍。

4）在所選擇的半徑范圍內等間距設置間隔，并將此作為各個盒子的半徑以傳統沙箱算法計算網絡的重分形維數。

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

圖1 改進的沙箱算法與Liu所提算法相比較

4 實驗結果分析

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

邊權重定義為相連接的兩個節點的函數值之差的絕對值，即：

節點權重定義為

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

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

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

圖3 同時包含節點和邊權重時的廣義分形維數D（q）

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

圖4 廣義分形維數D（q）隨邊權重變化情況

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

5 結語

本文主要通過利用改進的沙箱算法，對由H=0.1時的分形布朗運動基于HVG算法映射而成的同時包含節點權重和邊權重的可視網絡進行廣義分形維數D（q）計算，分析在同時包含節點權重和邊權重的情況時，復雜網絡的廣義分形維數D（q）的變化情況。結果表明，復雜網絡邊權重對于復雜網絡重分形特性的影響很大，且重分形特性的變化與邊權重系數的變化之間是不存在線性關系的，而節點權重對于復雜網絡的重分形特性的影響則較之邊權重小很多，可以說基本不受其影響。對于本文中所發現的這些重分形特性，與其背后所對應的網絡所具有的拓撲結構和其他統計特性之間是否存在聯系與如何定量分析兩者之間的聯系，值得進一步深入研究。

圖5 廣義分形維數D（q）隨節點權重變化情況