復雜網絡在雙曲空間的節點動態擇優路徑研究

楊琳

(武漢大學土木建筑工程學院工程管理系,湖北武漢 430072)

1 引言

復雜網絡為日常生活中發生的許多物理過程提供了一個自然的抽象解釋,遍及人類生活的方方面面.網絡有大量的節點以及連接節點的邊所組成,節點表示真實生活中的個體,邊表示個體與個體之間的關系.復雜網絡中一個最重要的功能就是傳輸功能,例如,以信息為載體的計算機網絡、以人和貨物為載體的運輸交通網絡、新聞或者社區信息傳播的社會網絡等等都是具有動力學特征的復雜網絡.有一種廣泛存在于社會各個領域的網絡結構,其度分布服從冪律分布p(k)～k?γ(2<γ<3),這種網絡有很強的異質性,少量節點占據大量的邊,能夠展現一個界限清晰的網絡特質,這就是具有無標度的復雜網絡[1].無標度網絡區別于其他網絡模型的最獨特之處在于,它是一個不斷增長和演化的網絡模型,這與真實世界的復雜系統不斷演化的特征極好的吻合,能夠很好地刻畫真實網絡[2].

近幾年來,復雜網絡的研究集中在以下幾個方面:復雜網絡的節點影響力研究[3]、節點傳輸速率研究[4]、網絡拓撲模型研究[5]、網絡同步分析[6]以及無標度網絡在交通運輸網絡[7]、計算機網絡[8]以及無線傳感網絡[9]等領域的應用研究等.上述研究都是建立在一個網絡節點不變的靜態網絡下進行的,而真實世界的網絡節點之間構成一個動態網絡.具有無標度的復雜網絡拓撲具有兩個典型的特征:節點的度分布服從冪律分布,且該網絡有一個高的聚類系數,即在網絡拓撲圖中可以找到很多三角形[10].許多復雜網絡的冪律分布是由實際網絡的增長特性和優先連接特性所產生的,大量的網絡節點數量不是一個定值,而是隨著時間推移呈動態增長趨勢[11].因而,在沒有復雜網絡全局視圖只有節點位置信息的情況下,網絡節點之間如何搭建清晰的動態連接路徑是一個值得深思的問題.

Kleinberg首先對此進行了解釋:他認為每一個節點都嵌套在歐幾里德平面坐標空間的網格內,且每一個節點的坐標可以抽象為其位置信息,即可以代表該點的位置、相鄰節點的位置以及相連接節點的位置,因而可以通過選擇最鄰近節點來設計貪婪路線[12–14].很顯然,Kleinberg描述的貪婪路徑規劃算僅在網絡拓撲與底空間完全重合才能有效實現,因為這種貪婪路徑算法難以同樣有效的應用在任意一個給定底空間的網絡拓撲中.在此基礎上,Krioukov提出了一個基于雙曲空間的復雜網絡模型,這個模型給出了一個服從冪律分布的復雜網絡[15–19].Krioukov模型表明:貪婪路徑算法實現了100%的可達性和優路徑長度.而僅僅依靠位置信息,運用貪婪路徑算法,一個節點可以找到其他任何節點,且一個節點選擇相鄰節點作為下一連接節點是通過計算最近的雙曲距離來判斷的[20].Krioukov模型的結論尤為重要,但是由于Krioukov模型是靜態的,所以很難被用于現實復雜網絡中.

本文針對該靜態模型的提出及其存在的問題,創新地提出了網絡節點動態雙曲嵌套模型,通過模型分析和計算,深入分析復雜網絡的節點動態連接路徑和最優算法.

2 雙曲空間的節點連接

在二維空間里,只有三種類型的各向同性坐標空間,即歐幾里德坐標空間、球形空間以及雙曲空間,每種空間的參數可見下表1.

表1:三種不同類型的各向同性坐標空間的參數比較

假定雙曲空間內有N個節點,且圓半徑為R,由于圓面積是2π(coshR?1),因此節點N服從指數分布,即N～eR,因而圓半徑與網絡大小N滿足對數關系,即R～lnN.具有常負曲率的雙曲空間不能被等距嵌入任何歐式空間,因為它比歐式空間更大.以給定點為中心,通過其Euler坐標值測量其表面曲率,形式上可以被定義為

其中l(R)表示以該點為中心,以R為半徑的圓周長.如果l(R)=2πR,則表面是平的;如果l(R)比2πR短,則表面是正曲的;如果l(R)比2πR長,則表面是負曲的.雙曲面的曲率不是恒定的,但是無限接近0.連接概率函數是一個極大熵分布[0,R],當雙曲距離在x≤R時每對節點連接.因為傳統的指數分布存在有界方差,當p(x)多項式快速衰減,當x→∞時,在概率密度演化圖中對于極值創造出一個“肥尾”.雙變量x和y通過冪次法則相關聯,當y(x)=Ax?γ時,正數經常被稱作指數,其中A和γ是正的常數.當概率密度函數是P(x)=Ax?γ,γ>1,且x>xmin時,則遵循冪次法則,即P(x)～k?3.復雜網絡節點存在于潛在的網絡拓撲空間,稱其為隱藏度量空間.網絡拓撲空間與隱藏度量空間的幾何耦合遵循以下的方式:即兩個節點之間的拓撲連接以一定的概率存在并依賴于兩個節點之間的隱含幾何距離.在這個假設前提下,真實的復雜網絡中,每一個互相連接的節點均處于具有負曲率的隱藏空間,且僅僅基于位置信息就能計算得到每個節點的隱藏坐標.給定一個網絡N,每個節點i首先被分配給一個隱藏變量hi,該變量服從某種概率分布,然后用連接概率p(i,j)連接節點對(i,j).隱藏空間的節點對的連接概率取決于雙曲空間的距離大小.因此,該雙曲網絡空間可以通過節點的度分布、節點的連接概率和雙曲曲率大小來描述一個無標度的復雜網絡.根據雙曲空間中定義的距離度量,如果這些網絡中的節點距離越接近,則被連接入網絡的可能性就越大.因此,首先要進行雙曲空間的選擇,然后確定節點的分布函數,最后選擇連接概率,即選擇節點之間雙曲線距離函數.本模型中,選擇[0,R]階梯函數作為連接概率函數,給出目標節點數N和平均度,根據N=keR/2(k是一個參數用來優化),確定雙曲線圓盤的半徑為R,并賦予每個節點分配一個角坐標θ,均勻的分布在[0,2π)之間,用如下概率函數給每個節點分配一個徑向坐標

假設任何時候相連的兩個節點之間的雙曲距離小于R,并定義兩個節點的極坐標分別為(γ,θ)和(γ0,θ0),那么這兩個節點之間的雙曲距離x被定義為

其中?θ=min(|θ?θ0|,2π?|θ?θ0|).利用這個模型,生成的復雜網絡服從冪律度分布,通過P(k)～k?γ得出

一般來說,負曲率的雙曲空間比一般的歐式空間增長速度更快,如果歐式空間呈線性增長的話,雙曲空間會呈指數增長.這種關系表明,在切線方向的歐式距離對應著呈指數增長的雙曲距離,因此復雜網絡可以進行雙曲空間的嵌套,網絡節點通過雙曲空間可以找到優化的動態路徑.

3 復雜網絡節點在雙曲空間的動態擇優過程

具有無標度的復雜網絡在雙曲空間建立節點路徑,保證了復雜網絡的拓撲結構與隱藏的雙曲空間的一致性.但是真實的復雜網絡往往是動態變化的,網絡內的節點數量有可能隨著時間的變化增加,因此需要一個隨著雙曲空間的增長而不斷擴大的無標度網絡模型.當網絡內有新的節點進入的時候,應該增加網絡的雙曲半徑,即令R=2ln(N/k).為了進一步表達動態過程,需要在新加入每一個節點之前就知道已存在的節點數量,需要一個全面覆蓋的復雜網絡.假設節點映射到一個半徑為R的雙曲圓盤上,R=2ln(Nmax/k),這里Nmax是網絡中節點數量的最大值.此外,節點被放在距離圓盤中心的某些固定的位置上,見圖1.

為了解釋這一點,把雙曲圓盤分割為環形NL(或者層),并且這些環形有外徑Ri和內徑Ri-1,在這里i∈{1,2,···,NL},并將其定義為

放置在每層i上的節點數量Ni是在圓盤區間上所期望得到的節點數,Ni是由分布函數ρ(γ)確定的,如下所示,

圖1:半徑為R的雙曲平面及分層示意圖

在該模型中,每一層i的節點Ni都沿著環形圓周放置在環形i的中間,節點Ni的半徑為.因此在雙曲平面極坐標中任一個節點p在平面i中的坐標p(γi,θi)為

節點p的坐標p(γi,θi)被表示為pi,k.根據公式(7)和(8)得到,一個節點的徑向坐標γ和角坐標θ可以假設為離散的值,代表離散的位置信息,因此該模型可以被認為是離散化的模型.一旦一個新的節點進入雙曲空間,它就連接到雙曲距離小于的節點,也就是說所有節點都在紅色陰影形狀圖1內.

4 網絡節點雙曲嵌套模型計算與分析

為了研究動態雙曲空間節點動態擇優網絡的拓撲特征,首先計算位于環的節點的平均度k(i).為了簡單起見,考慮一個節點pik放在水平i,角坐標定為(也就是k=0)在圖1中藍色陰影區域包含所有的點,從點pik到這些點的雙向距離小于或等于R.節點pik的平均度由下式給出

式中,Nj是放在環j的節點的數量,fj是Nj的分數,從點pik到這些點的雙向距離小于或等于R(也就是說所有這些節點都在藍色陰影形狀圖1內),fj的一個簡單公式可以這樣給出,等于藍色陰影區域內的圓形角的分數,如下公式

對于j和i+j≤NL+1,φi,j等于2π(也就是所有在水平j的點到點Pi,k的雙向距離小于R).在其他情況下,它是由以下公式給出

因此

將公式(6)和(10)代入公式(9)中,得到

證明了對于每一個i,j,φi,j等于2π,如i+j≤NL+1,改寫公式(13),

公式(14)中的第一個求和是一個有限的冪級數,如下

公式(15)顯示了一個指數遞減的趨勢,意味著公式(12)中這一項的作用隨著j接近NL值而遞減,對應于最后的周長.這種現象很容易解釋,是由于項相關于完全包含的環,而且隨著目標點向NL水平移動,它的作用趨向于0.

復雜網絡的度分布Pk是有著度k復雜網絡的點的分數.為了獲得動態雙曲空間嵌套模型中的度分布Pk,需要得到每一個環i的兩個值:1)環i的節點分布;2)環i的度.前者由比率Ni/Nmax得到,而后者由

計算得到.模型中忽略了對于Pk的分析描述,但是它遵循一個冪律,顯示在無標度網絡中,分析結果和實際情況吻合.

5 網絡節點動態連接路徑仿真

從上述分析過程可以得出,復雜網絡中每個單點的位置在動態變化的過程中維持了度分布與模型的一致.在復雜網絡動態雙曲嵌套模型中,每個點的位置直接與它的度相關,在動態變化的過程中,節點的度分布與模型始終保持一致.只要這種情況能夠得到保證,則隨著時間的變化,即使無標度網絡節點不斷增多,該雙曲嵌套模型仍然有效.在模型構建及分析過程中,任意選擇一個節點,根據均勻分布函數,設角φ∈[0,2π],該角能夠定義一個理想的點P=(R,φ),這個點位于自由的位置,有著最大的半徑和隨機角度,且距離P有著最小的距離.然后選擇無標度網絡的節點,該節點通過任意選擇得到且不需要靠近理想點,但選擇的節點要有足夠的動力接近實際到達的理想點;此時,最接近的節點有著關于整個網絡節點的總信息,這些節點的雙曲距離小于R,能夠有效的為新來的節點分配正確的位置;當新增加的節點得到的分配位置時,則該節點的位置信息被占據且能夠與鄰近節點形成新的無標度網絡,形成了具有雙曲平面特征的嵌套網絡.為了保證新增加的網絡節點在無標度雙曲嵌套模型中是最新的,允許每一個點有著鄰近點的全部信息(也就是點和自由位置存在于距離它的雙向距離R內)是共享的.該網絡中的每一個點與它鄰近節點的當地信息保持最新.假設一個網絡大小N=104,平均度分布=6.5,鑒于節點N和平均度分布,模擬仿真如下:首先,依據N=keR/2,修正半徑為R的雙曲平面,其中參數k用來調整平均度分布到目標度分布,其中N～∞;然后,給每個節點分配一個坐標r∈[0,R],且概率ρ(r)=αeαr(eαR?1)?1,α ∈[1/2,1];連接每兩點之間的雙曲距離小于R的節點對,其中雙曲距離x通過坐標變換 (r,θ) 和r0,θ0,可得

圖2:復雜網絡雙曲嵌套模型及節點連接路徑仿真示意圖

從圖中可以看到網絡的度分布、關聯性及聚類狀態等,該網絡有很強的聚類系數,形成了大量的三角形.實際上,如果平面內的節點a與節點b緊鄰,且節點b又同時與節點c緊鄰,則依據三角形公理,節點a同樣與節點c緊鄰.因此整個網絡的每三個節點組abc都與其他節點組相鄰.為了驗證該網絡結構是否具有無標度特征,分別設定γ=2.1和γ=2.9,計算P(k)、和(k),如下圖3所示.

通過比較在兩種不同的冪次分布下無標度網絡雙曲嵌套模型的拓撲指標可以看出:由于網絡服從冪律分布p(k)～k?γ(2<γ<3),網絡中影響度分布的冪次γ越低,相連節點的聚類程度越高,網絡的節點三角形越密集.對于γ=3這樣一個極限值,該網絡會對應一個平均路徑長度的異常值α=1.0,每兩個節點的連接只需要兩次跳躍即可實現.即在真實網絡世界里,不論該網絡的大小,只要滿足雙曲嵌套模型的結構,則每一個節點都會連接到一個中心.

圖3:不同冪次分布下網絡拓撲指標變化圖

6 結論

真實世界的網絡往往具有很強的異質性,能夠展現一個界限清晰的網絡特質,且網絡是隨著時間的變化,其節點容量不斷發生變化.本文鑒于復雜網絡冪律分布是由實際網絡的增長特性和優先連接特性所產生,大量網絡節點數量隨著時間推移呈動態增長趨勢的動態演化特質,從復雜網絡入手研究真實網絡節點動態連接規律進而揭示網絡動態演化機理具有重要意義和實用價值.

本文通過回顧克林伯格的歐氏空間網絡拓撲模型及貪婪路徑算法,以及克萊爾科夫提出的靜態雙曲網絡模型,發現依靠節點的位置信息就可以找到其他節點這一重要結論,同時認為靜態模型僅能作為網絡物理特征的研究方法,難以應用到真實的復雜網絡中,因此本文提出了基于雙曲空間的節點動態擇優路徑研究.

本文首先比較了歐式空間、球面空間和雙曲空間這三種各向同性空間的物理參數,認為隱藏空間中兩兩節點對的連接概率由雙曲空間的距離確定,故而雙曲空間可以通過網絡節點的度分布、節點的連接概率和雙曲曲率的大小描述無標度網絡.根據雙曲空間的距離度量,網絡節點距離越接近,則被連接入網絡的可能性就越大;并通過分析得到在切線方向的歐式距離對應著呈指數增長的雙曲距離,因此具有無標度的復雜網絡可以進行雙曲空間的嵌套.然后,構建了雙曲嵌套模型,通過分析模型中嵌套環的分布規律和嵌套區間內節點的度分布,驗證模型符合無標度網絡的冪律分布特征.最后,通過一個給定的真實網絡,設定網絡相關參數,對其進行網絡節點動態連接仿真,仿真結果表明:網絡中每個單點的位置在動態變化的過程中維持了度分布與模型的一致;在網絡動態雙曲嵌套模型中,每個點的位置直接與它度相關,在動態變化的過程中,節點的度分布與模型始終保持一致.

綜上所述,本文建立了復雜網絡雙曲嵌套模型,通過改變原有靜態模型依賴于連續雙曲空間的現狀,設計網絡節點在雙曲空間的優化路徑,通過分析離散節點在雙曲空間動態擇優過程,建立復雜網絡節點間最優路徑算法,對真實世界復雜網絡的動態演化機理提供了理論借鑒.下一步,針對節點之間的連接緊密性和動態連接速率,建立真實世界的網絡容量有序增長模型,將是關注的重點.