Internet AS層拓?fù)涔?jié)點(diǎn)度分布特性的演化規(guī)律

鄧曉衡, 許華嵐, 張連明*

(1. 中南大學(xué)信息科學(xué)與工程學(xué)院, 中國 長沙 410083;2. 湖南師范大學(xué)物理與信息科學(xué)學(xué)院, 中國 長沙 410081)

近年來, 國內(nèi)外有關(guān)Internet拓?fù)淠Ｐ秃吞匦缘拇罅垦芯勘砻? 不同層次的Internet拓?fù)渚哂邢嗤⑾嘟虿煌奶匦訹1]. 例如, Internet AS (Autonomous System)層, 路由器層和應(yīng)用層的WWW拓?fù)涞墓?jié)點(diǎn)度均具有冪律分布特性和小世界效應(yīng)[2]; AS層拓?fù)浜蚖WW拓?fù)渚@示匹配特性[3], 而很少有關(guān)于路由器層拓?fù)涫欠窬哂衅ヅ涮匦缘南嚓P(guān)報道; AS層拓?fù)涑尸F(xiàn)富人俱樂部特性[4], WWW拓?fù)渚哂凶韵嗨铺匦訹5], 而路由器層拓?fù)涫欠翊嬖诟蝗司銟凡刻匦曰蜃韵嗨铺匦? 以及AS層拓?fù)涫欠翊嬖谧韵嗨铺匦院蚖WW是否具有富人俱樂部特性等有待進(jìn)一步研究[6]. 為深入揭示潛在的AS層拓?fù)涮匦? 理解實(shí)際AS層拓?fù)涞难莼?guī)律與趨勢. 本文基于節(jié)點(diǎn)度閾值重整化算法研究Internet AS層拓?fù)涞墓?jié)點(diǎn)度分布特性及其演化規(guī)律.

1 Internet AS層拓?fù)涔?jié)點(diǎn)度分布特性及其演化規(guī)律分析方法

1.1 節(jié)點(diǎn)度分布特性

在Internet AS層拓?fù)鋱D中, 1個AS代表拓?fù)渚W(wǎng)絡(luò)的一個節(jié)點(diǎn), 2個ASes之間的互聯(lián)關(guān)系代表拓?fù)渚W(wǎng)絡(luò)的一條鏈路. 研究表明, Internet AS層拓?fù)涞墓?jié)點(diǎn)度k與節(jié)點(diǎn)度概率密度函數(shù)p(k)滿足冪律關(guān)系[7], 即

p(k)∝k-γ，

(1)

其中,γ稱為冪指數(shù), 式(1)稱為節(jié)點(diǎn)度冪律分布函數(shù). 一般情況下, 滿足冪律分布特性的實(shí)際網(wǎng)絡(luò)冪指數(shù)的取值范圍為: 2<γ<3.

節(jié)點(diǎn)度冪律分布是Internet AS層拓?fù)涞囊粋€重要特征, 它表現(xiàn)為網(wǎng)絡(luò)中存在大量的低度節(jié)點(diǎn)(擁有少量連接的節(jié)點(diǎn))和少量的高度節(jié)點(diǎn)(擁有大量連接的節(jié)點(diǎn)), 冪指數(shù)是這一類節(jié)點(diǎn)度分布規(guī)律的一個量化指標(biāo). 在實(shí)際應(yīng)用中, 為了更好地體現(xiàn)網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)度冪律分布特性, 一般使用補(bǔ)累積度分布函數(shù)P(k)來替代概率密度分布函數(shù)p(k).P(k)與節(jié)點(diǎn)度k和冪指數(shù)γ存在如下關(guān)系:

P(k)∝k-γ+1.

(2)

顯然, 公式(2)可以由公式(1)兩邊對k積分得到.

1.2 演化規(guī)律分析方法

上述研究結(jié)果同時也表明, 這些復(fù)雜網(wǎng)絡(luò)在重整化前后的度分布p(k′)具有不變特性, 即

p(k)→p(k′)∝(k′)-γ.

(3)

最近, 文獻(xiàn)[9]對復(fù)雜網(wǎng)絡(luò)重整化前后的自相似特性和無標(biāo)度節(jié)點(diǎn)度分布的不變特性進(jìn)行深入研究, 指出式(3)缺乏嚴(yán)格的數(shù)學(xué)證明和大量的數(shù)據(jù)驗證, 進(jìn)而推導(dǎo)出如下公式:

(4)

從公式(4)可知, 當(dāng)Ct>1和t約等于網(wǎng)絡(luò)的平均距離時,C0…Ct-1為網(wǎng)絡(luò)平均距離的指數(shù)函數(shù), 這也暗示網(wǎng)絡(luò)規(guī)模為平均距離的一個指數(shù)函數(shù), 此時網(wǎng)絡(luò)不具有自相似特性. 不過到目前為止, 這一結(jié)果還沒有得到實(shí)際數(shù)據(jù)的驗證.

對于一個復(fù)雜網(wǎng)絡(luò)可能存在多種粗粒度化方法, 在不同粗粒度化過程下獲得的復(fù)雜網(wǎng)絡(luò)拓?fù)涮匦院脱莼?guī)律不盡相同[10]. 最近, 文獻(xiàn)[11]提出了節(jié)點(diǎn)度閾值方法. 與盒覆蓋方法相比, 節(jié)點(diǎn)度閾值方法不但消除了不同粗粒度帶來的影響, 而且更能真實(shí)刻畫實(shí)際復(fù)雜網(wǎng)絡(luò)演化的逆過程.

本文在節(jié)點(diǎn)度閾值方法的基礎(chǔ)上, 給出一種重整化新算法來分析研究Internet AS層拓?fù)涔?jié)點(diǎn)度分布的不變特性和演化規(guī)律.

2 節(jié)點(diǎn)度閾值重整化算法

節(jié)點(diǎn)度閾值方法是指: 給定一個節(jié)點(diǎn)度閾值kT, 剔除網(wǎng)絡(luò)G中節(jié)點(diǎn)度小于和等于kT的所有節(jié)點(diǎn), 得到一個全新網(wǎng)絡(luò)G′. 使用節(jié)點(diǎn)度閾值方法針對Internet AS和PGP(Pretty Good Privacy)等復(fù)雜網(wǎng)絡(luò)進(jìn)行分析[11], 發(fā)現(xiàn)網(wǎng)絡(luò)G和網(wǎng)絡(luò)G′的節(jié)點(diǎn)度分布和節(jié)點(diǎn)度-度相關(guān)是自相似的, 但聚集系數(shù)是非自相似的. 為了探討Internet AS層拓?fù)涔?jié)點(diǎn)度分布特性的演化規(guī)律, 本文利用節(jié)點(diǎn)度閾值方法來對Internet AS層拓?fù)溥M(jìn)行重整化研究, 給出了一種新的節(jié)點(diǎn)度閾值重整化算法. 該算法的基本思想是: 給定一個原始Internet AS層拓?fù)銰和節(jié)點(diǎn)度閾值kT(=0,1, …,kmax-1), 一次性剔除拓?fù)銰中節(jié)點(diǎn)度小于和等于kT的所有節(jié)點(diǎn)以及與這些節(jié)點(diǎn)相連接的鏈路, 剩下的節(jié)點(diǎn)與鏈路所構(gòu)成的拓?fù)銰′(>kT)稱為kT次重整化Internet AS層拓?fù)? 這里kmax為原始Internet AS層拓?fù)涞淖畲蠊?jié)點(diǎn)度. 顯然, 當(dāng)kT=0時, 有G′(>kT)=G, 這說明0次重整化Internet AS層拓?fù)錇樵糏nternet AS層拓?fù)? 當(dāng)kT>kmax時, 則有G′(>kT)=Φ, 即kmax次重整化Internet AS層拓?fù)錇榭占? 節(jié)點(diǎn)度閾值重整化算法的具體實(shí)現(xiàn)如下:

(i) 給原始Internet AS層拓?fù)涞拿總€節(jié)點(diǎn)分配一個唯一標(biāo)號id, 且id=1, …,n, 其中n為網(wǎng)絡(luò)規(guī)模, 同時給出節(jié)點(diǎn)度閾值kT.

(ii) 利用一個二維數(shù)A[xi,yi]組存儲原始Internet AS層拓?fù)涞逆溌穢i→yi, 其中xi和yi分別代表第i條鏈路的2個節(jié)點(diǎn), 這里1≤i≤m,m為網(wǎng)絡(luò)的總鏈路數(shù).

(iii) 對數(shù)組進(jìn)行排序. 先按照第1列xi值對每一行數(shù)據(jù)進(jìn)行升序排列; 如果xi值相等, 則按照第2列yj值對每一行數(shù)據(jù)進(jìn)行升序排列.

(iv) 排除自環(huán)鏈路(即第1列和第2列相等的那行數(shù)據(jù)), 也就是刪除xi=yi的那些行; 排除平行鏈路, 即刪除滿足xi=yi和yi=xi中的其中一條鏈路. 生成一個新的數(shù)組B[xi,yi].

(v) 計算原始Internet AS層拓?fù)涞淖畲蠊?jié)點(diǎn)度kmax.

(vi) 設(shè)置數(shù)組行r=1, 另外再設(shè)置2個新的空數(shù)組, 即C=[]和D=[]. 循環(huán)下列步驟, 直到行r等于數(shù)組B[]的長度為止.

a) 計算數(shù)組B[]的第1列中與B[r,1]相等的元素個數(shù), 記為num1; 計算數(shù)組B[]的第2列中與B[r,2]相等的元素個數(shù), 記為num2.

b) 若num1≤kT和num2≤kT, 則把數(shù)組元素B[r,:]追加到數(shù)組C[]中, 形成重整化Internet AS層拓?fù)銰(>kT).

c)r增加1.

3 實(shí)驗結(jié)果與分析

3.1 數(shù)據(jù)來源和實(shí)驗過程

本文采用的Internet AS層拓?fù)鋽?shù)據(jù)來源于文獻(xiàn)[12]中的AS1, AS2, AS3和AS4 4組數(shù)據(jù).

實(shí)驗過程如下: 首先對4組數(shù)據(jù)AS1, AS2, AS3和AS4做簡單圖預(yù)處理, 即去掉自環(huán)鏈路和平行鏈路, 得到AS1, AS2, AS3和AS4的節(jié)點(diǎn)數(shù)n分別為12 694, 7 690, 8 689和8 904, 鏈路數(shù)m分別為26 559, 15 413, 17 709和17 653, 最大節(jié)點(diǎn)度kmax分別為2 566, 1 713, 1 911和1 921. 然后, 運(yùn)用第2節(jié)給出的節(jié)點(diǎn)度閾值重整化算法對AS1, AS2, AS3和AS4數(shù)據(jù)所對應(yīng)的Internet AS層拓?fù)溥M(jìn)行重整化, 得到節(jié)點(diǎn)度閾值分別為kT=0, 1, 2, …,kmax-1的重整化Internet AS層拓?fù)?

3.2 Internet AS層拓?fù)涔?jié)點(diǎn)度分布特性及其演化規(guī)律

為了尋找Internet AS層拓?fù)涞墓?jié)點(diǎn)度分布特性及其在演化過程中的變化規(guī)律或趨勢, 我們考查了i(i=0, 1, 2, …,kmax-1)次重整化Internet AS層拓?fù)涔?jié)點(diǎn)度分布情況. 圖1(a)～(h)顯示了數(shù)據(jù)AS1, AS2, AS3和AS4所對應(yīng)的Internet AS層拓?fù)淝夜?jié)點(diǎn)度閾值kT分別取0, 1, 2, 5, 10, 25, 50, 100和200時的重整化Internet AS層拓?fù)涞难a(bǔ)累積度分布概率P(k)與節(jié)點(diǎn)度k之間的關(guān)系(雙對數(shù)坐標(biāo)圖)(見公式(2)). 從圖1(a), 圖1(c), 圖1(e)和圖1(g)可以看出, 當(dāng)節(jié)點(diǎn)度閾值較小(比如kT<10)時, 重整化Internet AS層拓?fù)涔?jié)點(diǎn)度具有冪律分布特性(即節(jié)點(diǎn)度與補(bǔ)累積度分布概率為近似直線關(guān)系). 從圖1(b), 圖1(d), 圖1(f)和圖1(h)可以看出, 當(dāng)節(jié)點(diǎn)度閾值較大(比如kT>10)時, 重整化Internet AS層拓?fù)涔?jié)點(diǎn)度分布大致可分為2個階段, 即較小節(jié)點(diǎn)度節(jié)點(diǎn)滿足冪指數(shù)較小的冪律分布, 而較大節(jié)點(diǎn)度節(jié)點(diǎn)滿足冪指數(shù)較大的冪律分布.

圖1 重整化Internet AS層拓?fù)涞难a(bǔ)累積度分布

根據(jù)節(jié)點(diǎn)度分布函數(shù)(公式(1))與補(bǔ)累積度分布函數(shù)(公式(2))之間的關(guān)系, Internet AS層拓?fù)涞膬缰笖?shù)γ的值等于1減去補(bǔ)累積度分布函數(shù)曲線的擬合直線的斜率(-γ+1)的值. 通過計算, 我們得到了AS1, AS2, AS3和AS4數(shù)據(jù)在重整化過程中對應(yīng)的所有重整化Internet AS層拓?fù)涞膬缰笖?shù). 表1給出了節(jié)點(diǎn)度閾值kT分別取0, 1, 2, 5, 10, 25, 50, 100和200時對應(yīng)的冪指數(shù)γ的值.

表1 重整化Internet AS層拓?fù)涞膬缰笖?shù)值

從表1可知, 當(dāng)kT=0, 1, 2, 5, 10, 25, 50, 100和200時, AS1, AS2, AS3和AS4數(shù)據(jù)對應(yīng)的原始拓?fù)?kT=0)冪指數(shù)值的平均值分別為2.070 9, 2.071 6, 2.061 5, 2.048 8, 2.046 1, 2.047 8, 2.054 1, 2.095 8和2.169 0. 顯然, 0次和1次重整化Internet AS層拓?fù)涔?jié)點(diǎn)度分布的冪指數(shù)基本相等.

圖2 重整化Internet AS層拓?fù)涞墓?jié)點(diǎn)度冪指數(shù)隨節(jié)點(diǎn)度閾值的變化趨勢

圖2顯示了重整化Internet AS層拓?fù)涞膬缰笖?shù)γ隨節(jié)點(diǎn)度閾值kT的變化趨勢, 其中AVE為AS1, AS2, AS3和AS4數(shù)據(jù)所對應(yīng)節(jié)點(diǎn)度分布的冪指數(shù)的平均值. 從圖2可以看出, 當(dāng)節(jié)點(diǎn)度閾值取值范圍位于[1,10]區(qū)間內(nèi), Internet AS層拓?fù)湓谥卣昂蟮膬缰笖?shù)隨節(jié)點(diǎn)度閾值的增加呈現(xiàn)銳減趨勢; 當(dāng)節(jié)點(diǎn)度閾值取值范圍位于[10,50]區(qū)間內(nèi), Internet AS層拓?fù)湓谥卣昂蟮膬缰笖?shù)隨節(jié)點(diǎn)度閾值的增加而緩慢增加; 當(dāng)節(jié)點(diǎn)度閾值取值范圍位于[50,200]區(qū)間內(nèi), Internet AS層拓?fù)湓谥卣昂蟮膬缰笖?shù)隨節(jié)點(diǎn)度閾值的增加而快速增加.

綜上所述, 我們可以得出如下結(jié)論: (1)當(dāng)今Internet AS層拓?fù)涞墓?jié)點(diǎn)度分布具有冪律特性, 其冪指數(shù)約為2.070 9, 這說明在Internet AS層拓?fù)渲写嬖诖罅康牡投裙?jié)點(diǎn)和少許高度節(jié)點(diǎn); (2)在最近一次節(jié)點(diǎn)度閾值重整化過程中(即kT=1), Internet AS層拓?fù)涔?jié)點(diǎn)度的冪律分布特性基本保持不變, 由拓?fù)溲莼侵卣哪孢^程可知, Internet AS層拓?fù)湓谧罱难莼^程中具有節(jié)點(diǎn)度冪律分布的不變特性; 隨著節(jié)點(diǎn)度閾值的增大, 節(jié)點(diǎn)度冪律分布的冪指數(shù)隨節(jié)點(diǎn)度閾值的增加而銳減, 這反映Internet AS層拓?fù)湓谶@個階段的演化過程中節(jié)點(diǎn)度冪律分布的冪指數(shù)急劇增加; 當(dāng)節(jié)點(diǎn)度閾值為10到50時, 冪指數(shù)隨著節(jié)點(diǎn)度閾值的增加而緩慢增加, 這說明Internet AS層拓?fù)湓谠撾A段的演化過程中節(jié)點(diǎn)度冪律分布特性具有自相似特性; 當(dāng)節(jié)點(diǎn)度閾值為50到200時, 冪指數(shù)隨著節(jié)點(diǎn)度閾值的增加而快速增加, 這反映了Internet AS層拓?fù)湓谠撾A段的演化過程中節(jié)點(diǎn)度冪律分布特性減弱, 從圖1(b), 圖1(d), 圖1(f)和圖1(h)又可以看出, 此時節(jié)點(diǎn)度具有兩段分布特性, 從總體上看, 該階段的冪律分布特性增強(qiáng)了; 當(dāng)節(jié)點(diǎn)度閾值接近Internet AS層拓?fù)涔?jié)點(diǎn)度的最大值時, 由于拓?fù)涔?jié)點(diǎn)總數(shù)目較少, Internet AS層拓?fù)錇楹唵尉W(wǎng)絡(luò)而不具有復(fù)雜網(wǎng)絡(luò)特性, 即Internet AS層拓?fù)涔?jié)點(diǎn)度分布無冪律特性; 由此可以斷定在Internet AS層拓?fù)涞难莼l(fā)展過程中, 節(jié)點(diǎn)度分布的冪律特性的演化規(guī)律如下: 首先從無到有, 然后從大冪指數(shù)到小冪指數(shù), 最后又從小冪指數(shù)到大冪指數(shù); (3)基于節(jié)點(diǎn)度閾值重整化算法研究Internet AS層拓?fù)涞墓?jié)點(diǎn)度分布特性的演化規(guī)律是非常有效的.

4 結(jié)束語

為了尋找和了解潛在的Internet拓?fù)涞牟蛔兲匦院蛣討B(tài)演化規(guī)律, 本文首先歸納分析了基于盒覆蓋算法的重整化算法及其不足, 給出了基于節(jié)點(diǎn)度閾值的重整化算法, 對Internet AS層拓?fù)溥M(jìn)行重整化, 并在此基礎(chǔ)上分析研究重整化Internet AS層拓?fù)涞墓?jié)點(diǎn)度分布特性及其演化規(guī)律. 基于經(jīng)驗數(shù)據(jù)的研究結(jié)果表明, Internet AS層拓?fù)涞墓?jié)點(diǎn)度分布具有冪律特性且該特性在演化過程中具有不變特性或呈現(xiàn)自相似特性, 發(fā)現(xiàn)了Internet AS層拓?fù)涞墓?jié)點(diǎn)度冪律分布的冪指數(shù)大小的動態(tài)演化趨勢. 上述研究工作和結(jié)果不僅有利于理解實(shí)際Internet AS層拓?fù)涞牟蛔兲匦院蛣討B(tài)演化規(guī)律, 而且可用來對已存在的網(wǎng)絡(luò)模型進(jìn)行驗證與修正, 并進(jìn)一步提出更好的新型網(wǎng)絡(luò)模型.

參考文獻(xiàn)：

[1] COLIZZA V, FLAMINI A, SERANO M,etal. Detecting rich-club ordering in complex networks[J]. Nature Physics, 2006, 2:110-115.

[2] ALBERT R, JEONG H, BARABSI A L. Diameter of the world-wide web[J]. Nature, 1999, 401:130-131.

[3] NEWMAN M E J. Assortative mixing in networks[J]. Physical Review Letters, 2002, 89(20):208 701-208 704.

[4] ZHOU S, MONDRAGON R J. The rich-club phenomenon in the internet[J]. IEEE Communications Letters, 2004, 8(3):180-182.

[5] SONG C, HAVLIN S, HERNAN,etal. Self-similarity of complex networks[J]. Nature, 2005, 433:392-395.

[6] KIM J S, GOH K -I, SALVI G,etal. Fractality in complex networks: critical and supercritical skeletons[J]. Physical Review E, 2007, 75: 016 110-016 123.

[7] FALOUTSOS M, FALOUTSOS P, FALOUTSOS C. On Power-law relationship of the internet topology[J]. ACM SIGCOMM Computer Communication Review, 1999, 29(4): 251- 262.

[8] 汪小帆, 李 翔, 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M]. 北京: 清華大學(xué)出版社, 2006.

[9] XIAO W J, PENG L M, PARHAMI B. On general laws of complex networks[J]. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, 2009, 4:118-124.

[10] ITZKOVITZ S, LEVITT R, KASHTAN N,etal. Coarse-graining and self-dissimilarity of complex networks[J]. Physical Review E, 2005, 71: 016 127-016 136.

[11] SERRANO M A, KRIOUKOV D, BOGUNA M. Self-Similarity of complex networks and hidden metric spaces[J]. Physical Review Letters, 2008, 100:078 701-078 704.

[12] TSAPARAS P. Datasets[M/OL]. http://www.cs.helsinki.fi/u/tsaparas/MACN2006/data-code.html, 2008-8-9.