基于分形特性的復雜網絡全局效率估計方法

張勝，戴維凱，吳鋒，藍文祥

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

1 引言

復雜網絡是具有非平凡拓撲特征的圖，能夠表征各種各樣的復雜系統。真實復雜系統的圖模型中常常表現出小世界、無標度等拓撲特征[1]。網絡科學中全局效率是衡量信息交換效率的指標[2]。最初提出全局效率是用來度量復雜網絡中的小世界特征，使“小世界性”有了明確的物理意義和定量分析的標準。后來這一概念逐漸應用到多個領域，如社會網絡中尋找疫情傳播過程中的重要節點[3]；生物網絡中發現高智商青年人的腦網絡具有更高的全局和局部網絡效率，以此評估腦網絡的完整性[4-5]；通信網絡中用于評估網絡拓撲的穩健性[6]；交通網絡中利用網絡全局效率分析地鐵系統的傳輸效率和規劃維護道路網絡[7-8]；Web 網絡中使用網絡效率解釋信息傳輸的方式[9]；電力網絡中用來分析系統結構的脆弱性[10]。在無權和加權的復雜網絡中，有研究者利用網絡效率計算節點中心性[11-12]。

盡管網絡全局效率作為信息交換效率的衡量指標應用廣泛、作用巨大，但其計算十分復雜、耗時，且計算過程中最短路徑矩陣的理論計算時間復雜度達到O(N3)[13]。

大量研究發現，許多復雜網絡在結構上具有分形特性，其直觀地表現為網絡的整體與局部間存在自相似性。Song 等[14-15]分析了各種真實的復雜網絡，并發現它們在所有長度尺度上都由自我重復的模式組成，揭示了復雜網絡的分形與自相似特性。在求得一定長度尺度信息后，通過其自相似性可以推測出其他尺度上的模式。此后，研究者們提出多種分形維數，用來定量分析網絡分形特性。例如通過Rényi 熵[16]、結構熵[17]、最大熵[18]、相關熵[19]等從信息論角度研究復雜網絡的分形特性；通過提出節點體積和網絡的黎曼ζ函數等概念完善體積維數，從而進行網絡分形特性分析[20-22]。

利用網絡的分形特性，不僅揭示了網絡全局的拓撲結構特征，還反映了節點的局部信息[23]，一些分形維數也逐漸得到應用。Pu 等[24]通過局部維數識別網絡中具有影響力的節點。同樣的信息維也對網絡中重要節點識別起到了關鍵的作用[25-26]。文獻[27]引入非廣延參數q，利用多重局部維度的方法提供了一個更通用的識別重要節點的方法。文獻[28]利用分形維數分析了互聯網中演化的拓撲特征。

本文針對網絡全局效率計算復雜度高、耗時長的問題，利用分形網絡具有整體與局部的自相似性特征，深入分析網絡關聯維數與網絡效率的關系，將網絡全局效率的計算由部分局部節點效率的計算來近似估計，大大降低了網絡全局效率計算的復雜度。具體實現過程如下：1)判斷復雜網絡是否具有分形特性；2)利用關聯維數與尺度距離的關系估計節點關聯和；3)通過節點關聯和與網絡效率的關系估算網絡全局效率。

2 理論基礎

設網絡G=(N,E)，其中，N表示節點的集合，E表示邊的集合。

2.1 距離

2 個節點間的距離d定義為一個節點到另一個節點的最短路徑的邊權和，即

其中，k、l、m為節點序號；dij表示節點i與節點j的距離；wik為節點i與節點；k的邊權值；min 值為從節點i到節點j所經過的所有可能中最小的邊權和，即最短路徑長度，可以通過Floyd[13]或Dijkstra算法[29]求得。當所有邊的權值為1 時即為無權網絡，此時距離表現為2 個節點間的最少跳數。

2.2 關聯維數

分形維數是定量分析復雜網絡分形特性的主要工具[14,30]。關聯維數是分形維數的一種，在復雜網絡中表示隨機節點對所占空間維數的度量[31]。在平面網絡關聯維數[32]計算中，距離小于或等于r的節點對數量所占總數的比例C(r)稱為關聯和，即

其中，n為節點總數，H(x)為Heaviside 階躍函數[33]，如式(3)所示。

r與C(r)呈冪律關系，隨著半徑r的擴大，C(r)也相應增加，并且C(r)隨r以冪律的形式增長，即C(r)～rβ，則認為該網絡存在分形特性，冪指數β為關聯維數。通常C(r)～rβ并不是在所有尺度上都存在冪律增長的形式。在該冪律關系區間內，對r與C(r)取對數，擬合直線log(r)與log(C(r))，則該擬合直線斜率即為網絡的關聯維數值。

2.3 網絡全局效率

網絡的全局效率簡稱為網絡效率，表示整個網絡的平均效率，效率的度量允許對信息流進行精確的定量分析。數值上等于所有節點對距離倒數之和的平均值，定義為[34]

最初提出網絡效率的概念是用于定量分析復雜網絡中小世界的拓撲結構特征[2]，效率越高代表節點間的交互將消耗更少能量[35]。網絡效率的計算有助于識別網絡中有影響力的個體和改進網絡結果等功能[11]。

2.4 節點效率

節點效率Ik是指節點k到達其他所有節點的難易程度，數值上等于該節點與其他所有節點距離倒數之和的平均值[6]，如式(5)所示。

網絡效率刻畫的是整個網絡的平均接近程度，而節點效率則表示一個節點與其他所有節點信息交換的效率。節點效率越高，則該節點與其他節點的信息交換越容易，消耗的資源越少，同時也包含了網絡局部拓撲結構特征。從節點效率的定義中可看出，所有節點效率的平均值等于網絡效率E，因此網絡效率E也可通過式(6)求解[6]。

3 基于關聯維數的網絡效率估計方法

3.1 關聯維數與網絡效率分析

從式(6)可知，網絡效率可以轉換為求所有節點效率的均值。在計算所有節點效率時，會發現一些節點的效率實際上相差不大，如鄰居節點之間僅差一跳，那么它們具有近似的效率值，在規模較大的網絡中，鄰居節點之間效率值差距將更小。在關聯維數的計算中，需要計算一定距離下的節點對數量，并且關聯和C(r)也可以通過每個節點距離小于或等于r的數量再取平均得到。從式(2)可得，節點對距離小于或等于r的數量為

則距離等于r的節點對數量為

A(r)和S(r)是反映總體數量的。考慮單個節點的情況，以圖1 的網絡為例，以節點i為中心、r=1為半徑的范圍包含8 個鄰居節點，2 跳距離以內的節點數為21 個，與節點i在r跳以內的節點數記為Ai(r)。隨著r增大，Ai(r)也不斷增大，直到r達到網絡的半徑時，Ai(r)將等于除節點i外的總節點數。對所有節點求和，就可以得到以節點i為中心、r為半徑的節點的分布情況如表1 所示。

圖1 以節點i 為中心、r 為半徑的節點分布

表1 以節點i 為中心、r 為半徑的節點的分布情況

表1 中，Si(r)代表節點i的r階鄰居數，Si(1)=8表示直接（一階）與節點i相連的節點數量，當r=2時，2 階鄰居即鄰居的鄰居，與i的距離為2，因此Si(2)=13=Ai(2)-Ai(1)。同樣，總體的r階鄰居數量。此時通過式(5)計算i的節點效率是節點i到其他節點的距離倒數的平均值，共有Si(1)個一階鄰居，其距離倒數為1；共有Si(2)個二階鄰居，其距離倒數為；依次類推，可得

其中，L表示網絡的直徑，dik表示節點i與節點k的距離。式(9)表達的是以節點i為中心，i與其他節點距離倒數之和可等價于求節點i的r階鄰居數。所以網絡總的距離倒數之和為

將式(10)代入式(4)，可得網絡效率的另一種計算式，即

考慮一個網絡具有強分形特性，如構造一個環形的最近鄰耦合網絡，即為 Newman-watts 和Watts-Strogatz 小世界網絡模型的初始規則網絡。在雙對數坐標軸上，畫出C(r)與r的關系如圖2 所示，log(r)與log(C(r))能完美地擬合成一條直線。

圖2 環形最近鄰耦合網絡中C(r)與r 的關系

r與C(r)的關系為

根據式(7)與式(8)可得

將式(12)代入式(13)可得

將式(14)代入式(11)可得

此時，計算網絡效率僅需要網絡的直徑L和關聯維數β這2 個參數，便可以求出準確答案。對于關聯維數，可通過得出。

3.2 確定無標度區間

雖然環形的最近鄰網絡中，C(r)能在所有尺度r中都存在冪律關系，但實際上大部分網絡中C(r)與r只能在部分尺度范圍存在冪律關系。如圖3所示，整個線性區間(r1,rm)稱為無標度區間。式(14)只能在區間(r1,rm)成立，將其代入式(10)后變為

圖3 分形網絡C(r)與r 的關系

當r數值較小時，較大，這會導致節點對數量S(r)的誤差對整體造成更大的偏差，因此具有分形特性的網絡在區間(r1,rm)使用關聯維數與r的冪律關系來代替S(r)，可以降低在無標度區間網絡效率估計的敏感性，使誤差值減小。

由上述分析可知，網絡效率并不能單純地通過網絡直徑和關聯維數求得。需要先確定網絡是否存在著分形特性和無標度區間范圍。因此本文提出一種節點關聯和的方法來判斷復雜網絡是否存在分形特性。定義單個節點的關聯和為

則C(r)與Vk(r)的關系為

總體關聯和等于各節點關聯和的平均值。對于C(r)的求解，并不需要計算所有的節點平均，只需要在每求得一個節點關聯和時計算累積當前關聯和平均值，如果出現了無標度區間，則可認為不必繼續計算更多的節點關聯和。

3.3 確定決定系數閾值

無標度區間經常由人工判斷，后來Clauset 等[36]提出冪律分布的參數估計方法，同時也給出了可以用于估計無標度區間的方法。其中區間確認使用的是調整權重KS（Kolmogorov Smirnov）統計量的方法，通過2 個經驗分布之間的最大差值達到最小來確定區間范圍。當區間(r1,rm)的rm值越接近r1時，KS 統計量的差值通常就會越小，導致無標度區間的估計偏小。為了避免無標度區間過小，本文使用區間縮減的決定系數來確定無標度區間范圍。在區間縮減過程中，當決定系數值達到閾值上限，則表明有較好的擬合優度，當前的區間即為無標度區間。設共有w個觀測值x1,…,xw，當區間縮減至(1,q)時，通過數據(x1,…,xw)中的前q個數據來估計數值則前q個數的決定系數值為

q值從w遞減到q=rm，當R2(rm)首次大于閾值且rm足夠大時，(1,rm)為無標度區間，該網絡具有分形特性。由式(16)可知，網絡效率由關聯維數估計部分與區間外通過式(19)的r階鄰居2 個部分組成。關聯維數估計的部分所占網絡效率整體的比重越大，則該網絡的分形特性越強，估計方法將更準確。無標度區間關聯維數估計部分占整體的比重為

3.4 網絡效率的估計算法

本文提出的基于關聯維的網絡效率估計（CDEE,correlation dimension for efficiency estimation）算法主要包括3 個步驟：選取部分節點通過廣度優先遍歷的方法求取關聯和；確定無標度區間范圍；當無標度區間的權重達到閾值時，進行網絡效率的估計，否則重復上述步驟。算法的具體流程如算法1 所示。

算法1CDEE

輸入網絡圖G=(N,E)的鄰接矩陣A∈Rn×n，計算關聯維所需的最小節點數tmin，決定系數上限值，無標度區間權重閾值Py

輸出 網絡效率估計值E

1) function cal_scale_region(Ni,ListV)

2) fortinNido

3) 遍歷集合Ni的所有節點；

4) 初始半徑r=1

5) whileVt(r+1)-Vt(r) do

6) 節點t以r為半徑統計遍歷r范圍內的節點總數Vt(r)和Vt(r+1)

7) 半徑r自增1

8) end while

9)Vt(r)加入列表ListV中

10) end for

11) 循環停止后記錄下r的最大值記為rmax；

12) 計算ListV內所有節點關聯和平均值Vavg(r);

13) 區間縮減變量rv=rmax；

14) whilerv＞ 3 &R2(rv) ＜

15) 計算區間(1,rv)的縮減決定系數值R2(rv),直到達到預設上限值

16)rv=rv-1；

17) end while

18) 達到決定系數上限值時，區間(1,rv)即為無標度區間;

19) ifrv＜ 3 then

20) return None

21) else

22) returnrv

23) end if

24) end function

25) 將節點集合N分成份；

26) fori=1 to

27) 計算每份集合Ni的關聯和列表ListV，并獲取無標度區間；

28)rv=cal_scale_region(Ni,ListV)

29) ifrvthen

31) ifPf＞PyorPf ＜0.01 then

32) 當Pf大于閾值或者收斂時跳出循環

33) break

34) end if

35) end if

36) end for

37) 通過式(13)與式(16)求得網絡效率的估計E

38) returnE

CDEE 輸入4 個部分：圖G=(N,E)；計算關聯維數所需的最少節點數tmin，即每次最少選擇tmin個節點來求解關聯和的平均值；決定系數上限值無標度區間權重閾值Py。

算法1 的步驟1)～步驟24)為求取無標度區間函數，對象為列表ListV中所有節點的平均關聯和C(r)與r的關系。在每次調用該函數時，列表ListV都會存儲tmin個節點的關聯和。

步驟25)為代碼的第一個步驟，將集合N分成份。第一個循環求取第一份的無標度區間，第二個循環求取前兩份的節點集合的無標度區間，以此類推。

步驟26)～步驟36)開始的循環計算無標度區間權值，循環的終止條件為無標度區間權重值Pf超過閾值或者Pf收斂（Pf的變化小于0.01）。停止循環后開始進行最終的計算網絡效率的估計值。

4 實驗結果及分析

實驗將從構造生成的網絡（分形網絡和小世界網絡）和真實網絡（道路網絡）來驗證所提方法的有效性和準確性。

4.1 構造網絡的效率估計

4.1.1 分形網絡效率估計

迭代生成一個分形增長的復雜網絡，文獻[37]通過逆重整化的方法迭代生成分形網絡，生長過程由n、m、e這3 個參數控制，滿足

其中，N(t)和ki(t)分別表示t次迭代時的節點數量和節點i的度，節點i在逆重整化中將重新加入n-1 個節點數，其中m-1 個節點將連接到i上，剩余的n-m-2 個節點隨機連接到節點i的鄰居上。e∈[0,1]表示分形程度，e越接近1，則網絡的分形特性強度越低。在這里先構造n=6、m=3，并迭代4 次得到1 296 個節點數和1 295 條邊的分形網絡。對于不同e下生成的網絡進行驗證，這里取=0.998。圖4 為構造的分形網絡各參數e下C(r)與r的關系。對于e=0 時，無標度區間范圍最大；當e從0 變化到0.6 時，可以看出有明顯的分形特性。

圖4 構造的分形網絡各參數e 下C(r)與r 的關系

不同分形程度的構造網絡效率估計如表2 所示。由表2 可知，所有效率的估計誤差不超過1.2%，并且用于計算節點關聯和的節點數nk最大值為155，占總節點12%，其中參數e=0.2 和e=0.4時CDEE 僅需要計算8%的節點關聯和即可估計出誤差小于1.2%的全局效率，這意味著本文方法比傳統方法最高節省了92%的時間。e越小，表示該生成網絡的分形性越強，則無標度區間占比Pf也越大。關聯維數隨著網絡效率的增大而線性增長，這是因為網絡效率越高，則節點間信息交換效率越高，反映在局部中為小于r的節點對數量是增加的，導致C(r)隨著r更快增長，因此關聯維數也增大。在構造分形網絡中，β與E的關系如圖5 所示，它們有著明顯的線性關系。在這類分形網絡中，關聯維數與網絡效率的關系為

表2 不同分形程度的構造網絡效率估計

圖5 β 與E 的關系

4.1.2 小世界網絡效率估計

生成構造小世界網絡模型為Newman-Watts 小世界模型，簡稱為NW 網絡。網絡模型由n、K和p控制，分別表示網絡節點數、初始節點的鄰居數量和節點間加邊的概率。同樣規模的網絡，K和p越大，理論上網絡效率越高。生成的NW 小世界網絡節點數為5 000，K=8 即初始網絡節點的鄰居數為8，=0.995。小世界網絡模型各參數p下C(v)與r的關系如圖6 所示。從圖6 可以看到，當p=0 時，分形特性最明顯。隨著p增加，關聯維數也增大，因此關聯維數在定量分析小世界網絡的性質上與網絡效率同樣有效。表3也表明了關聯維數與網絡效率呈現出p∝β的正相關。由表3 可知，所有效率估計誤差不超過0.3%，僅需不到10%的節點關聯和來進行效率的估計，比傳統方法至少節省90%的時間。

圖6 小世界網絡模型各參數p 下C(r)與r 的關系

4.2 真實世界網絡效率估計

上述通過2 種構造網絡驗證了所提方法的有效性，在真實世界的網絡中，本文選取在ICON 中公開的美國各州道路網絡數據集。隨機選取了3 個公路網絡，分別為猶他州、路易斯安那州和威斯康星州。數據中的每個道路網絡都存在多個連通子網，本文分析時取網絡中最大的連通子網（節點數最多）代表該州道路網絡進行效率估計，3 個最大連通子網的平均節點數為390 231 個，邊為469 217 條。圖7為真實道路網絡中C(r)與r的關系。真實道路網絡效率估計如表4 所示。效率的估計只通過了不到1%的節點關聯和，根據Tsave顯示，最高能節約99.6%的時間，同時估計出的絕對誤差值低于0.65%的網絡效率。估計的網絡效率顯示，猶他州為0.004 027，高于威斯康星州的0.003 625 和路易斯安那州的0.003 171；同樣地，猶他州的關聯維數2.02 也大于威斯康星州和路易斯安那州。結果基本符合U.S.News&World Report 公布的美國50 州交通排行，猶他州排第2 名，威斯康星州排第32 名，路易斯安那州排第45 名。本文所提方法允許并行計算節點的關聯和，能加速網絡效率的估計，并進一步縮減計算時間。

表3 不同連邊概率p 的小世界網絡效率估計

表4 真實道路網絡效率估計

圖7 真實道路網絡中C(r)與r 的關系

5 結束語

本文針對復雜網絡中網絡效率計算復雜度高、時間長的問題提出一種效率的估計方法。該方法考慮復雜網絡中存在著分形的拓撲結構特性，從分形維的角度推導與分析了其中的關聯維數與網絡效率的關系，并給出了一種檢測網絡分形特性的新方法。實驗分析發現，在2 種構造生成的網絡中，關聯維數隨網絡效率線性增長，這說明關聯維數也能在一定程度上衡量網絡中節點信息交換的效率和復雜網絡的小世界性。本文方法不僅對強分形網絡有效，在弱分形網絡中也同樣有效，只需要知道無標度區間占比的變化情況也能得到較準確的效率估計。在節點數小于5 000 的復雜網絡中，需要約10%的節點關聯和，與傳統計算方法相比，可節省90%的時間，并得到了誤差值小于1.2%的網絡效率估計值。在規模更大的網絡（節點數大于200 000）中，3 個道路網絡效率的估計最多用到了0.75%的節點關聯和就可以獲得誤差不超過0.65%的網絡效率估計值。本文方法更適用于大規模網絡，大大降低了計算網絡效率所需的時間，平均時間復雜度將縮減至O(N)。由于節點關聯和計算是獨立的，因此本文方法將允許并行化操作，能進一步縮短效率估計所需的時間。