楊琳

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

1 引言

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

近幾年來,復(fù)雜網(wǎng)絡(luò)的研究集中在以下幾個方面:復(fù)雜網(wǎng)絡(luò)的節(jié)點影響力研究[3]、節(jié)點傳輸速率研究[4]、網(wǎng)絡(luò)拓?fù)淠Ｐ脱芯縖5]、網(wǎng)絡(luò)同步分析[6]以及無標(biāo)度網(wǎng)絡(luò)在交通運輸網(wǎng)絡(luò)[7]、計算機(jī)網(wǎng)絡(luò)[8]以及無線傳感網(wǎng)絡(luò)[9]等領(lǐng)域的應(yīng)用研究等.上述研究都是建立在一個網(wǎng)絡(luò)節(jié)點不變的靜態(tài)網(wǎng)絡(luò)下進(jìn)行的,而真實世界的網(wǎng)絡(luò)節(jié)點之間構(gòu)成一個動態(tài)網(wǎng)絡(luò).具有無標(biāo)度的復(fù)雜網(wǎng)絡(luò)拓?fù)渚哂袃蓚€典型的特征:節(jié)點的度分布服從冪律分布,且該網(wǎng)絡(luò)有一個高的聚類系數(shù),即在網(wǎng)絡(luò)拓?fù)鋱D中可以找到很多三角形[10].許多復(fù)雜網(wǎng)絡(luò)的冪律分布是由實際網(wǎng)絡(luò)的增長特性和優(yōu)先連接特性所產(chǎn)生的,大量的網(wǎng)絡(luò)節(jié)點數(shù)量不是一個定值,而是隨著時間推移呈動態(tài)增長趨勢[11].因而,在沒有復(fù)雜網(wǎng)絡(luò)全局視圖只有節(jié)點位置信息的情況下,網(wǎng)絡(luò)節(jié)點之間如何搭建清晰的動態(tài)連接路徑是一個值得深思的問題.

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

本文針對該靜態(tài)模型的提出及其存在的問題,創(chuàng)新地提出了網(wǎng)絡(luò)節(jié)點動態(tài)雙曲嵌套模型,通過模型分析和計算,深入分析復(fù)雜網(wǎng)絡(luò)的節(jié)點動態(tài)連接路徑和最優(yōu)算法.

2 雙曲空間的節(jié)點連接

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

表1:三種不同類型的各向同性坐標(biāo)空間的參數(shù)比較

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

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

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

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

一般來說,負(fù)曲率的雙曲空間比一般的歐式空間增長速度更快,如果歐式空間呈線性增長的話,雙曲空間會呈指數(shù)增長.這種關(guān)系表明,在切線方向的歐式距離對應(yīng)著呈指數(shù)增長的雙曲距離,因此復(fù)雜網(wǎng)絡(luò)可以進(jìn)行雙曲空間的嵌套,網(wǎng)絡(luò)節(jié)點通過雙曲空間可以找到優(yōu)化的動態(tài)路徑.

3 復(fù)雜網(wǎng)絡(luò)節(jié)點在雙曲空間的動態(tài)擇優(yōu)過程

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

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

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

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

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

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

4 網(wǎng)絡(luò)節(jié)點雙曲嵌套模型計算與分析

為了研究動態(tài)雙曲空間節(jié)點動態(tài)擇優(yōu)網(wǎng)絡(luò)的拓?fù)涮卣?首先計算位于環(huán)的節(jié)點的平均度k(i).為了簡單起見,考慮一個節(jié)點pik放在水平i,角坐標(biāo)定為(也就是k=0)在圖1中藍(lán)色陰影區(qū)域包含所有的點,從點pik到這些點的雙向距離小于或等于R.節(jié)點pik的平均度由下式給出

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

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

因此

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

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

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

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

復(fù)雜網(wǎng)絡(luò)的度分布Pk是有著度k復(fù)雜網(wǎng)絡(luò)的點的分?jǐn)?shù).為了獲得動態(tài)雙曲空間嵌套模型中的度分布Pk,需要得到每一個環(huán)i的兩個值:1)環(huán)i的節(jié)點分布;2)環(huán)i的度.前者由比率Ni/Nmax得到,而后者由

計算得到.模型中忽略了對于Pk的分析描述,但是它遵循一個冪律,顯示在無標(biāo)度網(wǎng)絡(luò)中,分析結(jié)果和實際情況吻合.

5 網(wǎng)絡(luò)節(jié)點動態(tài)連接路徑仿真

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

圖2:復(fù)雜網(wǎng)絡(luò)雙曲嵌套模型及節(jié)點連接路徑仿真示意圖

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

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

圖3:不同冪次分布下網(wǎng)絡(luò)拓?fù)渲笜?biāo)變化圖

6 結(jié)論

真實世界的網(wǎng)絡(luò)往往具有很強(qiáng)的異質(zhì)性,能夠展現(xiàn)一個界限清晰的網(wǎng)絡(luò)特質(zhì),且網(wǎng)絡(luò)是隨著時間的變化,其節(jié)點容量不斷發(fā)生變化.本文鑒于復(fù)雜網(wǎng)絡(luò)冪律分布是由實際網(wǎng)絡(luò)的增長特性和優(yōu)先連接特性所產(chǎn)生,大量網(wǎng)絡(luò)節(jié)點數(shù)量隨著時間推移呈動態(tài)增長趨勢的動態(tài)演化特質(zhì),從復(fù)雜網(wǎng)絡(luò)入手研究真實網(wǎng)絡(luò)節(jié)點動態(tài)連接規(guī)律進(jìn)而揭示網(wǎng)絡(luò)動態(tài)演化機(jī)理具有重要意義和實用價值.

本文通過回顧克林伯格的歐氏空間網(wǎng)絡(luò)拓?fù)淠Ｐ图柏澙仿窂剿惴?以及克萊爾科夫提出的靜態(tài)雙曲網(wǎng)絡(luò)模型,發(fā)現(xiàn)依靠節(jié)點的位置信息就可以找到其他節(jié)點這一重要結(jié)論,同時認(rèn)為靜態(tài)模型僅能作為網(wǎng)絡(luò)物理特征的研究方法,難以應(yīng)用到真實的復(fù)雜網(wǎng)絡(luò)中,因此本文提出了基于雙曲空間的節(jié)點動態(tài)擇優(yōu)路徑研究.

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

綜上所述,本文建立了復(fù)雜網(wǎng)絡(luò)雙曲嵌套模型,通過改變原有靜態(tài)模型依賴于連續(xù)雙曲空間的現(xiàn)狀,設(shè)計網(wǎng)絡(luò)節(jié)點在雙曲空間的優(yōu)化路徑,通過分析離散節(jié)點在雙曲空間動態(tài)擇優(yōu)過程,建立復(fù)雜網(wǎng)絡(luò)節(jié)點間最優(yōu)路徑算法,對真實世界復(fù)雜網(wǎng)絡(luò)的動態(tài)演化機(jī)理提供了理論借鑒.下一步,針對節(jié)點之間的連接緊密性和動態(tài)連接速率,建立真實世界的網(wǎng)絡(luò)容量有序增長模型,將是關(guān)注的重點.