郭虹，楊白薇，蘭巨龍，劉洛琨

（1. 國家數(shù)字交換系統(tǒng)工程技術(shù)研究中心，河南 鄭州 450002;

2. 信息工程大學(xué) 信息工程學(xué)院 通信工程系，河南 鄭州 450002）

1 引言

近些年來，Internet的商業(yè)化行為促使互聯(lián)網(wǎng)快速成長，現(xiàn)今 Internet已滲透到社會生活的方方面面。但是，人們對支撐各種網(wǎng)絡(luò)應(yīng)用的互聯(lián)網(wǎng)拓?fù)涞膬?nèi)在結(jié)構(gòu)特征和演化規(guī)律的理解卻遠(yuǎn)未成熟。當(dāng)前全球范圍內(nèi)正掀起重新規(guī)劃和設(shè)計(jì)新一代互聯(lián)網(wǎng)的熱潮，下一代互聯(lián)網(wǎng)的研究和設(shè)計(jì)將秉承繼承和發(fā)展的思路。需要對當(dāng)前互聯(lián)網(wǎng)的基礎(chǔ)設(shè)施和行為進(jìn)行充分、深入地認(rèn)識。

基于拓?fù)錅y量，對互聯(lián)網(wǎng)進(jìn)行拓?fù)涮卣鞣治?，從中提取出?biāo)識網(wǎng)絡(luò)內(nèi)在結(jié)構(gòu)的主要特征，是有效利用和進(jìn)一步指導(dǎo)網(wǎng)絡(luò)建設(shè)的重要前提；利用拓?fù)浞治鼋Y(jié)論模擬構(gòu)建出網(wǎng)絡(luò)拓?fù)洌転樵S多不便于在實(shí)體網(wǎng)絡(luò)上開展的實(shí)驗(yàn)和協(xié)議開發(fā)、研究提供準(zhǔn)確的網(wǎng)絡(luò)仿真環(huán)境；而將模型生成的拓?fù)涮卣髋c實(shí)際網(wǎng)絡(luò)進(jìn)行對比、評估，能進(jìn)一步加深人們對實(shí)際互聯(lián)網(wǎng)拓?fù)涞恼J(rèn)識和理解[1,2]。

互聯(lián)網(wǎng)拓?fù)浒床煌６葎澐譃槁酚善骷?RL,router-level)和自治域 (AS, autonomous system)級。與RL級相比，AS級位于更“高”一層，其特征與變化對互聯(lián)網(wǎng)的影響更為巨大，相關(guān)研究對下一代網(wǎng)絡(luò)的發(fā)展意義更為重大；而且AS 級規(guī)模相對RL級規(guī)模小得多，能夠進(jìn)行更深層次、更復(fù)雜的計(jì)算分析，以探究更為隱秘的客觀特性和規(guī)律[2]。

自 20世紀(jì)末復(fù)雜網(wǎng)絡(luò)研究興起后，許多拓?fù)浜晏卣鞅欢x以刻畫拓?fù)浣Y(jié)構(gòu)的內(nèi)在特性，包括節(jié)點(diǎn)度分布、平均路徑長度、聚集系數(shù)、同配系數(shù)和富人俱樂部系數(shù)等。為了向互聯(lián)網(wǎng)研究人員提供更準(zhǔn)確的網(wǎng)絡(luò)拓?fù)淠Ｐ停負(fù)浣Ｑ芯空呦群筇岢隽舜罅康耐負(fù)淠Ｐ突蛏伤惴?，如隨機(jī)網(wǎng)絡(luò)模型、層次模型、小世界模型、冪律模型、局域世界模型等。其中，Waxman、Transit-Stub[3]、WS、BA、LW[4]、PFP[5,6]等模型比較著名。但是，早期的互聯(lián)網(wǎng)拓?fù)浣Ｑ芯渴芟抻谕負(fù)鋽?shù)據(jù)的獲取，對拓?fù)涞膬?nèi)在機(jī)理認(rèn)識不足，且大多數(shù)模型側(cè)重于對度優(yōu)先偏好連接和冪律度分布的刻畫，對實(shí)際互聯(lián)網(wǎng)的其他拓?fù)涮卣骺坍嬤€存在一定的差距[7]。

“層次性”是互聯(lián)網(wǎng)中普遍存在的基本特性之一?；ヂ?lián)網(wǎng)的規(guī)劃建設(shè)及商業(yè)模式特點(diǎn)使其呈現(xiàn)出明顯的層次結(jié)構(gòu)。了解、量化網(wǎng)絡(luò)的層次性有助于人們更深入地認(rèn)識互聯(lián)網(wǎng)的內(nèi)在拓?fù)涮匦?，對于研究互?lián)網(wǎng)的演化機(jī)制非常重要。早期基于對“層次性”的直觀理解，將網(wǎng)絡(luò)劃分為 Stub域或 Transit域，提出了具有嚴(yán)格層次結(jié)構(gòu)的互聯(lián)網(wǎng)靜態(tài)拓?fù)淠Ｐ蚑ransit-Stub[3]。文獻(xiàn)[8]在研究了復(fù)雜網(wǎng)絡(luò)中的層次組織后提出了層次模塊性，并給出一種網(wǎng)絡(luò)層次性的數(shù)學(xué)刻畫——簇度相關(guān)性。為研究網(wǎng)絡(luò)核心結(jié)構(gòu)，文獻(xiàn)[9]提出了核數(shù)以及k-core分解以量化節(jié)點(diǎn)的中心程度。文獻(xiàn)[7,10]初步探討了節(jié)點(diǎn)度與核數(shù)之間的關(guān)系，建立了靜態(tài)的層次模型。

鑒于目前對AS級拓?fù)鋵哟涡苑治?、建模不足，本文基于對互?lián)網(wǎng)實(shí)測數(shù)據(jù)的層次性分析，提出了一種對真實(shí)互聯(lián)網(wǎng)AS級拓?fù)鋵哟翁卣鞣铣潭雀平慕７椒?，并通過計(jì)算機(jī)建模仿真分析說明其合理性及有效性。

2 AS級拓?fù)涞膶哟涡再|(zhì)

AS級拓?fù)淇沙橄鬄辄c(diǎn)和邊組成的無向簡單圖，節(jié)點(diǎn)代表自治域(AS)，邊則代表AS之間的BGP連接。AS級拓?fù)渚哂须S機(jī)性、小世界現(xiàn)象、冪律性、聚集性、層次性和富人俱樂部現(xiàn)象等性質(zhì)[1]。

2.1 度的高可變性

1999年，F(xiàn)aloutsos 3兄弟在對互聯(lián)網(wǎng)數(shù)據(jù)分析時(shí)發(fā)現(xiàn)其拓?fù)涞墓?jié)點(diǎn)度分布表現(xiàn)出形如P(k)∝k-λ的冪律，在雙對數(shù)坐標(biāo)中近似為一條斜率為-λ的直線。冪律分布的發(fā)現(xiàn)顛覆了稱霸多年的隨機(jī)網(wǎng)絡(luò)模型，揭示出互聯(lián)網(wǎng)拓?fù)涞囊粋€(gè)重要性質(zhì)——度的高可變性：即拓?fù)渲泄?jié)點(diǎn)度值的范圍很大，大部分節(jié)點(diǎn)的連接度較小，少部分節(jié)點(diǎn)的連接度很大。度的高可變性揭示出在AS級拓?fù)渲胁煌?jié)點(diǎn)扮演不同的角色：少數(shù)的高度值節(jié)點(diǎn)成為Hub節(jié)點(diǎn)，負(fù)責(zé)全網(wǎng)的連通性，網(wǎng)絡(luò)中存在層次性。

2.2 層次性

冪律是基于節(jié)點(diǎn)度對拓?fù)涞木植棵枋?，層次性則是對其的宏觀描述。1997年，Paxson基于拓?fù)鋵?shí)測數(shù)據(jù)，提出基于節(jié)點(diǎn)度值將AS級互聯(lián)網(wǎng)劃分為4個(gè)層次，初步揭示了兩者之間的內(nèi)在聯(lián)系。但是，度僅代表了最少的局部信息，基于節(jié)點(diǎn)度的層次性劃分方法存在一定的偏差和主觀性[11]。

2.3 簇度相關(guān)性

文獻(xiàn)[8]在對復(fù)雜網(wǎng)絡(luò)的實(shí)證研究中發(fā)現(xiàn)，受地理因素限制的網(wǎng)絡(luò)缺乏層次性，例如美國西部電力網(wǎng)和路由器層網(wǎng)絡(luò)；而AS級Internet中節(jié)點(diǎn)的地理位置因素不確定也不重要，具有明顯的層次性，并給出了網(wǎng)絡(luò)中層次性的定量刻畫——簇度相關(guān)性，發(fā)現(xiàn)AS級拓?fù)涞拇囟汝P(guān)系近似為

其中，＜m(k)＞表示度為k的所有節(jié)點(diǎn)的鄰居之間平均存在的邊數(shù)，C(k)表示度為k的節(jié)點(diǎn)的平均簇系數(shù)[12]。

2.4 核數(shù)

一個(gè)圖的k-核是指反復(fù)移除圖中所有節(jié)點(diǎn)度小于等于k的節(jié)點(diǎn)及其連接的邊，直到所有剩余節(jié)點(diǎn)的度都大于k所余下的子圖[13]。

定義1 節(jié)點(diǎn)的核數(shù)：如果一個(gè)節(jié)點(diǎn)屬于k-核，而不屬于(k+1)-核，則該節(jié)點(diǎn)核數(shù)為k。節(jié)點(diǎn)的核數(shù)越大，越意味著該節(jié)點(diǎn)位于拓?fù)鋱D的中心。

定義 2 圖的核數(shù)：圖中節(jié)點(diǎn)核數(shù)的最大值即為圖的核數(shù)。

由定義1和定義2知，節(jié)點(diǎn)/圖的核數(shù)能夠標(biāo)識出節(jié)點(diǎn)/子圖在拓?fù)鋱D中的深度，核數(shù)較節(jié)點(diǎn)度值具有更客觀的層次性刻畫能力。

3 AS級拓?fù)涞膶哟涡苑治?/h2>

本節(jié)基于AS級Internet拓?fù)涞膶?shí)測數(shù)據(jù)，對其進(jìn)行層次性分析。

3.1 數(shù)據(jù)來源

AS級拓?fù)鋽?shù)據(jù)獲取主要有2種方式：1) 基于BGP路由表和更新消息推測的被動測量方式，如量方式，將測量出的 IP路徑映射為 AS路徑，如但獲取的僅是控制層面的拓?fù)?，且由于ISP通常將BGP路由信息視作商業(yè)機(jī)密，通過推測BGP路由信息將無法獲得ISP未對外公開的私有連接。主動測量相對難實(shí)現(xiàn)，但展現(xiàn)的是數(shù)據(jù)層面的拓?fù)洹榭陀^分析AS級拓?fù)涞膶哟涡?，本文采集、綜合了取出2003年12月到2006年12月共7個(gè)真實(shí)的一個(gè)真實(shí)的AS級拓?fù)鋱D。

3.2 基本拓?fù)涮匦?/h3>

本節(jié)對上述數(shù)據(jù)集逐一進(jìn)行拓?fù)涮匦苑治?，如?所示。其中，N和E分別是拓?fù)鋱D中總的節(jié)點(diǎn)數(shù)和邊數(shù)；是平均節(jié)點(diǎn)度；是平均最短距離；＜C＞

由表1可知，隨著時(shí)間的演化，真實(shí)互聯(lián)網(wǎng)呈現(xiàn)指數(shù)的加速增長；網(wǎng)絡(luò)同時(shí)具有小的平均最短距離和大的平均聚集系數(shù)，具有小世界效應(yīng)；網(wǎng)絡(luò)的同配系數(shù) r≈-0.23，意味著低度值節(jié)點(diǎn)的鄰居中大部分是高度值節(jié)點(diǎn)，低度節(jié)點(diǎn)傾向于和高度節(jié)點(diǎn)連接；k≤3的節(jié)點(diǎn)占全網(wǎng)的絕大多數(shù)，網(wǎng)絡(luò)中不穩(wěn)定的部分主要是度值為1的葉子節(jié)點(diǎn)。表1的分析結(jié)果與文獻(xiàn)[20]的結(jié)論一致。

3.3 層次性分析

1) 拓?fù)鋱D的核數(shù)與最高核

拓?fù)鋱D的核數(shù)與最高核對于層次性分析具有重要意義。對上述數(shù)據(jù)集的核數(shù)與最高核情況進(jìn)行絡(luò)節(jié)點(diǎn)數(shù)，En為最高核內(nèi)的連接數(shù)，Ep(為與最高核相關(guān)連接的比例。由表2可知，隨著時(shí)間推移，Internet的網(wǎng)絡(luò)規(guī)模不斷增長，AS級拓?fù)鋱D的核數(shù)2004年以后逐漸趨于28；最高核所含節(jié)點(diǎn)數(shù)占全體節(jié)點(diǎn)數(shù)的比例在0.182%～0.511%之間；最高核內(nèi)連接數(shù)占全網(wǎng)總連接數(shù)的比例在 1.17%～3.05%之間；外部節(jié)點(diǎn)與最高核的相關(guān)連接占了全網(wǎng)總連接的很大一部分，在44.41%～54.95%之間。充分說明真實(shí) AS級互聯(lián)網(wǎng)中網(wǎng)絡(luò)的核心很少突然出現(xiàn)或消失，近年來一直趨于穩(wěn)定；最高核內(nèi)連接稠密，影響力滲透到全網(wǎng)，決定并影響著網(wǎng)絡(luò)的整體性能，非常重要。

表1 AS級Internet的基本拓?fù)涮匦?/p>

表2 AS級Internet的核數(shù)與最高核分析

2) 節(jié)點(diǎn)的核數(shù)-度分布

節(jié)點(diǎn)核數(shù)標(biāo)識節(jié)點(diǎn)在拓?fù)鋱D中的深度，拓?fù)鋱D中各節(jié)點(diǎn)的核數(shù)與其度值之間存在著一定的關(guān)系，了解拓?fù)鋱D中節(jié)點(diǎn)的核數(shù)-度分布是認(rèn)識AS級拓?fù)鋵哟涡缘囊粋€(gè)重要度量。圖1(a)給出ITDK0304數(shù)據(jù)集的節(jié)點(diǎn)核數(shù)-度分布，為雙對數(shù)坐標(biāo)。

圖1 ITDK0304拓?fù)鋱D的節(jié)點(diǎn)核數(shù)-度分布

由圖1(a)可以看出真實(shí)AS級拓?fù)渲懈骱藬?shù)內(nèi)節(jié)點(diǎn)的度值較為分散，度值越大的節(jié)點(diǎn)具有高核數(shù)的可能性越大，但是，即便一個(gè)節(jié)點(diǎn)的度數(shù)很高，它的核數(shù)也可能很小。為使兩者之間的關(guān)系明晰，對相同度值，取全體節(jié)點(diǎn)核數(shù)的平均值，得到簡化圖，如圖 1(b)所示。由簡化圖可以看出，AS級拓?fù)渲械投戎倒?jié)點(diǎn)(k＜20)的核數(shù)與度值呈正相關(guān)；高度值節(jié)點(diǎn)(k＞120)主要集中于高核區(qū)域內(nèi)，且隨著度值的增加，節(jié)點(diǎn)核數(shù)不再增加；但部分高度值節(jié)點(diǎn)(20＜k<120)的核數(shù)散落于其他層。

3) 拓?fù)鋱D的k-core分解

k-core分解是一種非常有效的提取網(wǎng)絡(luò)中心部分的方法。為進(jìn)一步研究AS級拓?fù)鋱D中各核的細(xì)節(jié)，對上述數(shù)據(jù)集逐一進(jìn)行k-core分解，記錄各核內(nèi)節(jié)點(diǎn)的數(shù)目 N(kc)、占全網(wǎng)節(jié)點(diǎn)數(shù)的比例 Np、平均度值＜k＞、平均連接數(shù)＜cn＞、各核所擁有的連接占全網(wǎng)總連接的比例E1、各核內(nèi)部連接占該核所擁有連接的比例E2、各核與最高核的連接占該核所擁有連接的比例E3。

表3 ITDK0304數(shù)據(jù)集的k-core分解

由表3的k-core分解結(jié)果，可知以下幾點(diǎn)。

① 隨著 kc的增大，真實(shí)的 AS級拓?fù)鋱D中各核子圖的尺寸雖然有一些波動，但相較全網(wǎng)規(guī)模的增長各核節(jié)點(diǎn)比例幾乎是穩(wěn)定的；各核所擁有的連接占全網(wǎng)總連接的比例 E1也基本穩(wěn)定，只在 kc=1,2,3處波動大一點(diǎn)，說明網(wǎng)絡(luò)中不穩(wěn)定的部分主要是低核數(shù)（也是低度值）節(jié)點(diǎn)。

② 核數(shù)較低(kc=1,2,3)的節(jié)點(diǎn)占總節(jié)點(diǎn)數(shù)的大部分(74.47%)，其余核數(shù)(kc＞3)節(jié)點(diǎn)數(shù)較少。

③ 最高核包含了大量的“度”，意味著最高核雖然只包含著少數(shù)節(jié)點(diǎn)，但都為高度值節(jié)點(diǎn)，0.5%的最高度值節(jié)點(diǎn)都在最高核內(nèi)。

④ 與最高核有關(guān)的連接占據(jù)網(wǎng)絡(luò)連接中相當(dāng)大的一部分(58%)；最高核內(nèi)部的連接只占該核所擁有連接的5.26%，其余大部都分散在與其他各核之間的連接上。說明最高核的影響力巨大，滲透到網(wǎng)絡(luò)的各個(gè)核數(shù)內(nèi)。

⑤ 與低核數(shù)節(jié)點(diǎn)相關(guān)的連接也占據(jù)了網(wǎng)絡(luò)連接中的相當(dāng)一部分(44.62%)，而這些核內(nèi)部的連接只占核所擁有連接的的很小一部分(1.26%～4.3%)，其余部分均是與最高核的連接。

說明最高核影響力巨大，滲透到網(wǎng)絡(luò)的各個(gè)核數(shù)內(nèi)，對其的刻畫將決定整個(gè)層次模型的成敗。

4) 拓?fù)鋱D的簇度分布

圖2給出ITDK0304的簇度分布，表明在真實(shí)的互聯(lián)網(wǎng)AS級拓?fù)鋱D中C(k)與k之間確實(shí)存在著高度的負(fù)相關(guān)性，并隨著k的增加而遞減，遞減的斜率大致在-0.75左右。但目前很多互聯(lián)網(wǎng)拓?fù)淠Ｐ筒⒉荒芎芎玫卦佻F(xiàn)這一負(fù)相關(guān)性。

圖2 ITDK0304拓?fù)鋱D的簇度分布

4 AS級拓?fù)鋵哟谓?/h2>

按據(jù)層次性分析結(jié)論，建立基于核數(shù)劃分的AS級互聯(lián)網(wǎng)拓?fù)鋵哟蝿討B(tài)演化模型 IAT-HDEM(Internet AS-level topology hierarchical dynamic evolution model)。

4.1 層次模型的關(guān)鍵

層次模型的關(guān)鍵在網(wǎng)絡(luò)核心刻畫與層次劃分。

1) 網(wǎng)絡(luò)核心刻畫

網(wǎng)絡(luò)核心即網(wǎng)絡(luò)的最高核，盡管最高核內(nèi)節(jié)點(diǎn)數(shù)很少，但最高核的影響滲透到網(wǎng)絡(luò)的各個(gè)層次；且最高核隨互聯(lián)網(wǎng)演化已逐漸趨于穩(wěn)定。對網(wǎng)絡(luò)核心的刻畫決定著層次模型的成敗。如何刻畫網(wǎng)絡(luò)核心呢？按據(jù)上述數(shù)據(jù)集的 k-core分解統(tǒng)計(jì)結(jié)果，IAT-HDEM 模型的最高核數(shù)設(shè)為maxck=28；最高核內(nèi)的節(jié)點(diǎn)數(shù)為 N28=N×0.294 5%，連接平均數(shù)為E28=E×2.113 8%。

鑒于最高核內(nèi)都為高度值節(jié)點(diǎn)，由網(wǎng)絡(luò)演化視角看，隨著網(wǎng)絡(luò)演化，不斷進(jìn)入網(wǎng)絡(luò)的新節(jié)點(diǎn)按高概率與網(wǎng)絡(luò)的核心節(jié)點(diǎn)連接。所以，在基于度擇優(yōu)偏好連接概率的動態(tài)網(wǎng)絡(luò)演化模型中，初始網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)成長為高度值節(jié)點(diǎn)的概率很大，將網(wǎng)絡(luò)核心設(shè)為初始網(wǎng)絡(luò)。

2) 層次劃分

節(jié)點(diǎn)的核數(shù)與其地位、規(guī)模正相關(guān)；節(jié)點(diǎn)核數(shù)較度值具有更客觀的層次性刻畫能力。表3表明：低核數(shù)節(jié)點(diǎn)(kc≤3)占據(jù)了網(wǎng)絡(luò)中絕大部分節(jié)點(diǎn)數(shù)(74.47%)和連接數(shù)(44.62%)；最高核雖然節(jié)點(diǎn)比例很少(0.51%)，但與最高核相關(guān)的連接卻占了全網(wǎng)連接的一半強(qiáng)(58%)，將最高核單獨(dú)刻畫；4～27，各核節(jié)點(diǎn)所占比例極低，且隨著核數(shù)kc增加，影響力相當(dāng)，將中間核層合并處理。

層次劃分的設(shè)想如下：按照核數(shù)高低將網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)共劃分為6個(gè)層次：Ω1（核數(shù)kc=1的節(jié)點(diǎn)集），Ω2（核數(shù)kc=2的節(jié)點(diǎn)集），Ω3（核數(shù)kc=3的節(jié)點(diǎn)集），Ω4（核數(shù)kc=4,5的節(jié)點(diǎn)集），Ω5（對應(yīng)核數(shù)kc=6,7,…,maxck-1的節(jié)點(diǎn)集），Ω6（對應(yīng)核數(shù)maxck的節(jié)點(diǎn)集，為最高核集Ωmax）。

在確定6個(gè)層次后，各層次內(nèi)部的具體細(xì)節(jié)又如何？以ITDK0304數(shù)據(jù)集為例，對數(shù)據(jù)集進(jìn)行層次分析，如表4所示。由表4可得到IAT-HDEM模型的思想：新節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)按層次選擇概率 H，選擇相應(yīng)的層次加入；再按各層間連接概率p選擇目標(biāo)節(jié)點(diǎn)層次；按偏好擇優(yōu)概率從目標(biāo)層次中選擇相應(yīng)的宿主節(jié)點(diǎn)加邊連接，實(shí)現(xiàn)網(wǎng)絡(luò)的動態(tài)演化增長。

4.2 基于核數(shù)劃分的AS級層次動態(tài)演化模型

為建立IAT-HDEM模型，并獲得具體的模型參數(shù)，對上述數(shù)據(jù)集分別進(jìn)行層次分析，并對相應(yīng)參數(shù)進(jìn)行算術(shù)平均，得到層次建模參數(shù)，如表5所示。由表5知，節(jié)點(diǎn)加入各層次的概率不同，差別很大；網(wǎng)絡(luò)中各層內(nèi)、層間節(jié)點(diǎn)間有相互連接，連接概率不盡相同；各層與網(wǎng)絡(luò)核心層的連接相對于與其他層次的連接較多。

1) 模型算法

IAT-HDEM模型算法描述如下。

模型輸入：N，E（期望的網(wǎng)絡(luò)規(guī)模）。

模型輸出：網(wǎng)絡(luò)拓?fù)涞泥徑泳仃嘇。

模型初始化：建立6個(gè)層次集合Ωi，并按Hi確定各集合的最終大小：

網(wǎng)絡(luò)演化過程如下。

Step1 產(chǎn)生初始網(wǎng)絡(luò)。

m0=N×0.295%，e0=E×2.114%，初始網(wǎng)絡(luò)節(jié)點(diǎn)間隨機(jī)連接，并記錄到A中，形成Ω6=Ωmax。因e0相較 m0而言稠密得多，能確保初始網(wǎng)絡(luò)每個(gè)節(jié)點(diǎn)的度至少為1。

Step2 網(wǎng)絡(luò)增長。

① 在每一個(gè)時(shí)間步增加一個(gè)新節(jié)點(diǎn)vn。

② 按概率Hi，i=1,2,…,6，選擇新節(jié)點(diǎn)vn加入的層次i。當(dāng)且僅當(dāng)|Ωi|＜Ni時(shí)，新節(jié)點(diǎn)vn加入i層，vn∈Ωi；否則回到②。

例如，vn按概率選擇第6層，因?yàn)槌跏季W(wǎng)絡(luò)已構(gòu)建完成|Ω6|=N6，所以返回②重新選擇vn加入的層次；由于新節(jié)點(diǎn)加入第6層的概率很小(0.263%)，此事件基本不可能發(fā)生。但考慮到在網(wǎng)絡(luò)逐漸演化過程中，可能出現(xiàn)某一層次先加入完畢的情形，故做此處理。

③ 當(dāng) 1≤i≤5時(shí)，為新節(jié)點(diǎn)增添 m條連接。從 vn節(jié)點(diǎn)出發(fā)，引出 m條邊與宿主節(jié)點(diǎn)vhj(j=1,2,…,m)相連。對某個(gè)宿主節(jié)點(diǎn) vhj的選擇方法為：按概率pij選擇宿主節(jié)點(diǎn) vhj歸屬的目標(biāo)層次j，vhj∈Ωj；如果j層次的|Ωj|≤3，則視目標(biāo)層次節(jié)點(diǎn)集合為空，即刻為Ωj增加一個(gè)新節(jié)點(diǎn)vn'= vhj∈Ωj，連接vn與vn'，轉(zhuǎn)入④。否則，從Ωj中按非線性擇優(yōu)出宿主節(jié)點(diǎn) vhj，連接vn與 vhj。對vn節(jié)點(diǎn)重復(fù)此操作m次，完成新加入節(jié)點(diǎn)vn與不同層次不同節(jié)點(diǎn)間的m條連接。更新當(dāng)前網(wǎng)絡(luò)內(nèi)的節(jié)點(diǎn)數(shù)。

④ 當(dāng)③中目標(biāo)層次的節(jié)點(diǎn)集合視為空時(shí)，為Ωj增加了一個(gè)新節(jié)點(diǎn)vn'∈Ωj，并連接了vn與vn'。為使對新節(jié)點(diǎn)的操作一致，還需要對vn'增加m-1條邊。

重復(fù)上述過程，直至網(wǎng)絡(luò)增長到期望規(guī)模N。

宿主節(jié)點(diǎn)的選擇思想為：先選擇宿主節(jié)點(diǎn)的層次，再從目標(biāo)集合中按非線性擇優(yōu)概率選擇宿主節(jié)點(diǎn)。為了突出和說明基于核數(shù)劃分層次建模的有效性和合理性，IAT-HDEM模型簡化了網(wǎng)絡(luò)演化過程中存在的節(jié)點(diǎn)和邊的消亡的模擬。

表4 ITDK0304數(shù)據(jù)集的層次分析

表5 IAT-HDEM模型層次建模參數(shù)

2) m的取值與概率

在IAT-HDEM模型中，對新加入各層的節(jié)點(diǎn)，為其分配的連接數(shù)為m。如果m的取值為固定值，則將導(dǎo)致各層次節(jié)點(diǎn)度值過于平均，違背了圖1(a)所反映出的節(jié)點(diǎn)核數(shù)-度分布的散落性。為避免各層次節(jié)點(diǎn)度值過于平均，m的取值應(yīng)與節(jié)點(diǎn)歸屬的層次有關(guān)且為變值。即使不同時(shí)間步內(nèi)加入同一層次的不同新節(jié)點(diǎn)，其m連接數(shù)也應(yīng)按概率有所不同。

以ITDK0304數(shù)據(jù)集為例。在第1層，核數(shù)kc=1，這層中99.11%的節(jié)點(diǎn)度都為1，但是該層也含有少量的度大于1的節(jié)點(diǎn)（0.77%的節(jié)點(diǎn)度為2，剩余節(jié)點(diǎn)度為3或其他）。這意味著，進(jìn)入第1層的節(jié)點(diǎn)其連接數(shù)有可能為2或3，但還是以大概率可能為1。按次類推，能分析、計(jì)算出各層節(jié)點(diǎn)的度分布，進(jìn)而得出進(jìn)入各層的節(jié)點(diǎn)應(yīng)以怎樣的概率擁有怎樣的連接數(shù)。據(jù)此處理，不僅能確保各層節(jié)點(diǎn)的平均連接數(shù)能與期望值接近，還能避免各層各節(jié)點(diǎn)連接數(shù)過于同一的情形。

具體IAT-HDEM模型中m的參數(shù)按據(jù)來自對上述數(shù)據(jù)集的統(tǒng)計(jì)平均。例如，第1層m的取值為1、2、3，對應(yīng)概率分別為98.30%、1.60%、0.10%；第 2層 m的取值為 2、3、4、5、6、7，對應(yīng)概率分別為 90.80%、5.60%、1.60%、0.70%、0.70%、0.60%；第3層m的取值為3～15；第4層m的取值為4～29；第5層m的取值為6～60。每一層m的取值范圍，盡可能取到剩余節(jié)點(diǎn)所占概率和小于1%。

3) 擇優(yōu)連接概率

現(xiàn)有的大多拓?fù)淠Ｐ?，都以?yōu)先連接理論為基礎(chǔ)，不同的是各模型的優(yōu)先連接概率的計(jì)算公式。IAT-HDEM模型中在選定目標(biāo)層次后，采用優(yōu)先連接方法選擇宿主節(jié)點(diǎn)，擇優(yōu)連接概率[7]為

現(xiàn)有的多種優(yōu)先連接概率公式多以節(jié)點(diǎn)度值為計(jì)算基數(shù)，與之相比略有不同的是，式(2)的基數(shù)選取為節(jié)點(diǎn)度值與節(jié)點(diǎn)歸屬層次的＜m＞（各層的平均連接數(shù)）之差。這是因?yàn)椋趯觾?nèi)優(yōu)先連接開始時(shí)，各層內(nèi)節(jié)點(diǎn)的度值相差不大，基本接近＜m＞，這使得一般的擇優(yōu)概率難以發(fā)揮作用，故要去除各層相應(yīng)的＜m＞值后再進(jìn)行擇優(yōu)。為確保選擇概率不為0，選擇二者之差+1作為計(jì)算基數(shù)。

4.3 算法復(fù)雜度分析

IAT-HDEM模型算法主要分為3步：新節(jié)點(diǎn)按層次選擇概率選擇相應(yīng)的層次加入；再按各層間連接概率選擇目標(biāo)層次和在目標(biāo)層次內(nèi)按偏好擇優(yōu)概率選擇相應(yīng)的宿主節(jié)點(diǎn)；新節(jié)點(diǎn)與宿主節(jié)點(diǎn)間連邊，實(shí)現(xiàn)網(wǎng)絡(luò)的動態(tài)演化增長。所以其算法時(shí)間復(fù)雜度和空間復(fù)雜度均與網(wǎng)絡(luò)規(guī)模相關(guān)。由于引入了一些概率模型，算法的復(fù)雜度分析較為復(fù)雜，但仍可以粗略地進(jìn)行估算。

時(shí)間復(fù)雜度介于O(N)和O(N2)之間。該算法需要輸出拓?fù)涞泥徑泳仃嘇；在算法執(zhí)行過程中，需要存儲相應(yīng)的層次集合以及各節(jié)點(diǎn)對應(yīng)的度和連接數(shù)等信息。所以，其空間復(fù)雜度約為 O(N2+N+2N)= O(N2+3N)。

可見，隨著網(wǎng)絡(luò)不斷演化，每個(gè)時(shí)間步內(nèi)新加入節(jié)點(diǎn)的處理耗時(shí)不斷增加；當(dāng)網(wǎng)絡(luò)規(guī)模很大時(shí)，IAT-HDEM算法輸出整體耗時(shí)在指數(shù)增長，與計(jì)算機(jī)仿真實(shí)驗(yàn)的結(jié)果一致。

5 計(jì)算機(jī)建模仿真分析

本文在MATLAB中實(shí)現(xiàn)了IAT-HDEM模型，將建模結(jié)果與實(shí)際網(wǎng)絡(luò)進(jìn)行比較以評價(jià)建模方法的優(yōu)劣。

5.1 IAT-HDEM模型的宏特征

由于節(jié)點(diǎn)選擇層次和宿主節(jié)點(diǎn)連接按概率發(fā)生，每次仿真得到的網(wǎng)絡(luò)拓?fù)溆兴煌?，本文采取多次?shí)驗(yàn)取平均的方法來統(tǒng)計(jì) IAT-HDEM 模型拓?fù)涞暮晏卣?。文中仿真結(jié)果均為 10次獨(dú)立實(shí)驗(yàn)取平均，如表6所示。

由表6可以看出，IAT-HDEM模型在相同的參數(shù)下，在平均節(jié)點(diǎn)度、平均最短距離、平均集聚系數(shù)、網(wǎng)絡(luò)的同配系數(shù)、Rich-club系數(shù)、圖的核數(shù)、度為1，2，3的節(jié)點(diǎn)在網(wǎng)絡(luò)中所占的比重方面與真實(shí)的AS級拓?fù)涞暮晏卣鹘咏?/p>

表6 真實(shí)AS級拓?fù)鋱D與IAT-HDEM模型的宏特征比較

5.2 IAT-HDEM模型的冪律特性

冪律特性是衡量拓?fù)淠Ｐ托阅艿闹匾笜?biāo)之一，圖3為IAT-HDEM模型的節(jié)點(diǎn)度分布。

圖3 I IAT-HDEM模型的節(jié)點(diǎn)度分布（N=5 000）

由圖3可見，IAT-HDEM模型的節(jié)點(diǎn)度分布也呈冪律，且冪律指數(shù)并不隨網(wǎng)絡(luò)規(guī)模的增長而變化，圖中直線為斜率-2.3的冪律曲線，IAT-HDEM模型在冪指數(shù)上擬合得也很好。這說明基于核數(shù)劃分的層次動態(tài)演化模型在冪律特性方面也有突出表現(xiàn)，也從另一個(gè)側(cè)面說明，增長與優(yōu)先連接并非唯一決定網(wǎng)絡(luò)拓?fù)鋬缏商匦缘闹匾蛩?，層次性也影響著網(wǎng)絡(luò)的冪律特性。

5.3 IAT-HDEM模型的層次特性

圖4給出IAT-HDEM模型的節(jié)點(diǎn)的核數(shù)-度分布，與圖1對比，IAT-HDEM模型呈現(xiàn)出類似的節(jié)點(diǎn)核數(shù)-度分布趨勢，略有不同的是，IAT-HDEM模型中高度值節(jié)點(diǎn)的核數(shù)整體偏小一些，這是由于實(shí)驗(yàn)網(wǎng)絡(luò)規(guī)模所致。

圖4 IAT-HDEM模型拓?fù)鋱D的節(jié)點(diǎn)核數(shù)-度分布（N=5 000）

圖5 給出IAT-HDEM模型的簇-度分布，與圖2對比，IAT-HDEM模型呈現(xiàn)出明顯的負(fù)的簇度相關(guān)性且斜率大致在-0.7左右，與文獻(xiàn)[8]結(jié)論一致。這說明即使基于核數(shù)劃分的 IAT-HDEM 模型也能呈現(xiàn)出傳統(tǒng)意義上的層次性。圖5進(jìn)一步說明簇度的負(fù)相關(guān)性是增長網(wǎng)絡(luò)模型內(nèi)在固有的特性之一[21]。

圖5 IAT-HDEM模型拓?fù)鋱D的簇度分布（N=5 000）

計(jì)算機(jī)建模仿真分析表明，IAT-HDEM 模型能較好地模擬真實(shí)互聯(lián)網(wǎng)AS級拓?fù)涞暮晏卣?、冪律特性和層次特性，是一種模擬互聯(lián)網(wǎng)AS級拓?fù)鋵哟蔚膭討B(tài)演化模型。該模型具有如下優(yōu)點(diǎn)：1) 以實(shí)測量數(shù)據(jù)為背景，優(yōu)化模型參數(shù)，對真實(shí)拓?fù)淠M較好；2) 模型既能夠反映出AS級拓?fù)涞膶哟涡蕴匦?，同時(shí)又保留了其他多種特征；3) 該模型的提出，能夠?yàn)镮nternet拓?fù)浣?gòu)建一個(gè)較為合理的框架，例如可以基于層次劃分對AS間的商業(yè)關(guān)系進(jìn)行建模。

6 結(jié)束語

本文基于對AS級Internet拓?fù)鋵?shí)測數(shù)據(jù)的層次性分析，提出了一種基于核數(shù)劃分的AS級互聯(lián)網(wǎng)層次動態(tài)演化模型(IAT-HDEM)。該模型以節(jié)點(diǎn)核數(shù)作為層次劃分按據(jù)，是按照拓?fù)鋱D自身內(nèi)在的層次性進(jìn)行劃分，角度重更為合理、細(xì)致。計(jì)算機(jī)建模仿真分析表明，該模型能較好地模擬出真實(shí)互聯(lián)網(wǎng)AS級拓?fù)涞暮晏卣?、冪律特性和層次特性。模型的提出，對進(jìn)一步分析層次性質(zhì)對網(wǎng)絡(luò)拓?fù)涞闹匾饬x提出了思路；此外，該模型可以作為 AS級Internet網(wǎng)絡(luò)拓?fù)浣５囊粋€(gè)基本框架，在此框架基礎(chǔ)上，可以繼續(xù)刻畫其他拓?fù)涮匦裕鏏S級的商業(yè)關(guān)系；或者添加AS節(jié)點(diǎn)和邊的生、滅描述等，這將是下一步的研究工作?；跍y量建立拓?fù)淠Ｐ?，這正是互聯(lián)網(wǎng)拓?fù)浣Ｑ芯楷F(xiàn)階段被忽略的，本論文的工作做了良好嘗試，而模型參數(shù)的可測性會對模型價(jià)值產(chǎn)生重大影響，對于探究網(wǎng)絡(luò)的演化機(jī)理意義重大。

[1] 楊家海, 吳建平, 安常青. 互聯(lián)網(wǎng)絡(luò)測量理論與應(yīng)用[M]. 北京: 人民郵電出版社, 2009.299-324.YANG J H, WU J P, AN C Q. Internet Measurement Theory and Applications[M]. Beijing: Posts & Telecom Press, 2009.299-324.

[2] 周苗,楊家海,劉洪波等. Internet 網(wǎng)絡(luò)拓?fù)浣J].軟件學(xué)報(bào),2009,20(1):109-123.ZHOU M, YANG J H, LIU H B, et al. Modeling the complex Internet topology[J]. Journal of Software, 2009,20(1):109-123.

[3] ZEGURA E W, CALVERT K L, DONAHOO M L. A quantitative comparison of graph-based models for Internet topology[J].IEEE/ACM Transactions on Networking, 1997, 5(6): 770-783.

[4] LI X, CHEN G A. Local-world evolving network model[J]. Phys A,2003, 328: 274-286.

[5] ZHOU S, MONDRAGón R J. Accurately modeling the Internet topology[J]. Physical Review E, 2004, 70(6):8-15.

[6] ZHOU S. Characterising and modelling the Internet topology the rich-club phenomenon and the PFP model[J]. BT Technology Journal,2006, 24(3):108-115

[7] 張昕, 趙海, 王莉菲等. AS級Internet拓?fù)浞治鯷J]. 通信學(xué)報(bào), 2008,29(7): 50-61.ZHANG X, ZHAO H, WANG L F, et al. Analysis on the Internet AS-level topology[J]. Journal on Communications, 2008, 29(7): 50-61.

[8] RAVASZ E, BARABáSI A L. Hierarchical organization in complex networks[J]. Physical Review E, 2003, 67(2):12-20.

[9] GAERTLER M, PATRIGNANI M. Dynamic analysis of the autonomous system graph[A]. Proceedings of IPS 2004[C]. Budapest, Hungary,2004.

[10] 張君, 趙海, 周艷. Internet路由級節(jié)點(diǎn)的度與核數(shù)的關(guān)系[J]. 東北大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008, 29(5): 653-656.ZHANG J, ZHAO H, ZHOU Y. Relationship between degree and core number of internet nodes at router level[J]. Journal of Northeastern University(Natural Science), 2008, 29(5): 653-656.

[11] CHEN Q, CHANG H, GOVINDAN R, et al. The origin of power laws in Internet topologies revisited[A]. Proceedings of IEEE INFOCOM Conference[C]. New York, USA, 2002. 608-617.

[12] 張國強(qiáng),張國清.Internet網(wǎng)絡(luò)的關(guān)聯(lián)性研究[J]. 軟件學(xué)報(bào), 2006,17(3): 490-497.ZHANG G Q, ZHANG G Q. Research on Internet correlation[J].Journal of Software, 2006,17(3):490-497.

[13] HAMELIN A, LGNACIO J, LUCA D A, et al. Alessandro V k-core decomposition: a tool for the visualization of large scale networks[EB/OL]. http://arxiv.org/abs/cs. NI/0511007, 2005.

[14] Routeviews project [EB/OL]. http://www.routeviews.org,2008.

[15] DONNET B, FRIEDMAN T. Internet topology discovery: a survey[J].IEEE Communications Surveys & Tutorials, 2007, 9(4): 56-69.

[16] CAIDA[EB/OL]. http://www.caida.org,2008.

[17] MAHADEVAN P, KRIOUKOV D, FOMENKOV M, et al. The internet AS-level topology: three data sources and one definitive metric[EB/OL]. http://www.caida.org/outreach/papers/2006/as topology/as topology. pdf, 2006

[18] 張國強(qiáng), 張國清. 互聯(lián)網(wǎng) AS級拓?fù)涞木植烤蹐F(tuán)現(xiàn)象研究[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2006,3(3):34-41.ZHANG G Q , ZHANG G Q. Research on local clustering of the Internet AS level topology[J]. Complex Systems and Complexity Science, 2006,3(3):34-41.

[19] NEWMAN M E J. Assortative mixing in networks[J]. Physical Review Letters, 2002, 89(20):8701-8704.

[20] ZHANG G Q, ZHANG G Q, YANG Q F, et al. Evolution of the Internet and its cores[J]. New Journal of Physics, 2008, 10(12):3027-3038.

[21] LIANG T, CHEN P Z, DA N S, et al. Universal scaling behavior of clustering coefficient induced by deactivation mechanism[J]. Physical Review E, 2006, 74(4): 3-10.