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

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

1 引言

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

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

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

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

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

2 理論基礎

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

2.1 距離

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

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

2.2 關聯(lián)維數(shù)

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

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

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

2.3 網(wǎng)絡全局效率

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

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

2.4 節(jié)點效率

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

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

3 基于關聯(lián)維數(shù)的網(wǎng)絡效率估計方法

3.1 關聯(lián)維數(shù)與網(wǎng)絡效率分析

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

則距離等于r的節(jié)點對數(shù)量為

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

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

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

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

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

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

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

圖2 環(huán)形最近鄰耦合網(wǎng)絡中C(r)與r 的關系

r與C(r)的關系為

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

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

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

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

3.2 確定無標度區(qū)間

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

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

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

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

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

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

3.3 確定決定系數(shù)閾值

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

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

3.4 網(wǎng)絡效率的估計算法

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

算法1CDEE

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

輸出 網(wǎng)絡效率估計值E

1) function cal_scale_region(Ni,ListV)

2) fortinNido

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

4) 初始半徑r=1

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

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

7) 半徑r自增1

8) end while

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

10) end for

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

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

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

14) whilerv＞ 3 &R2(rv) ＜

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

16)rv=rv-1；

17) end while

18) 達到?jīng)Q定系數(shù)上限值時，區(qū)間(1,rv)即為無標度區(qū)間;

19) ifrv＜ 3 then

20) return None

21) else

22) returnrv

23) end if

24) end function

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

26) fori=1 to

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

28)rv=cal_scale_region(Ni,ListV)

29) ifrvthen

31) ifPf＞PyorPf ＜0.01 then

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

33) break

34) end if

35) end if

36) end for

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

38) returnE

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

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

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

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

4 實驗結果及分析

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

4.1 構造網(wǎng)絡的效率估計

4.1.1 分形網(wǎng)絡效率估計

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

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

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

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

表2 不同分形程度的構造網(wǎng)絡效率估計

圖5 β 與E 的關系

4.1.2 小世界網(wǎng)絡效率估計

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

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

4.2 真實世界網(wǎng)絡效率估計

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

表3 不同連邊概率p 的小世界網(wǎng)絡效率估計

表4 真實道路網(wǎng)絡效率估計

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

5 結束語

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