CHP3 復(fù)雜網(wǎng)絡(luò)理論及應(yīng)用3.ppt

1、第3章 Internet拓?fù)涮匦约敖?3.1 引言 3.2 Internet的拓?fù)涮匦?3.3 隨機圖產(chǎn)生器 3.4 結(jié)構(gòu)產(chǎn)生器 3.5 基于連接度的產(chǎn)生器 3.6 多局域世界模型 3.7 各類模型的定性比較,3.1 引言,路由器層面： 自治系統(tǒng)(Autonomous System)層面：,在互聯(lián)網(wǎng)中，一個自治系統(tǒng)(AS)是一個有權(quán)自主地決定在本系統(tǒng)中應(yīng)采用何種路由協(xié)議的小型單位。 由單一行政部門所管理的子網(wǎng)絡(luò)，可由高達(dá)數(shù)以百計的路由器組成。,節(jié)點為路由器，邊為路由器之間的物理連接（如光纖）,（a） 路由器層 （b）AS層,自治系統(tǒng) AS間采用BGP協(xié)議,BGP 發(fā)言人,BGP 發(fā)言人,BG

2、P 發(fā)言人,BGP 發(fā)言人,BGP 發(fā)言人,AS1,AS3,AS2,AS5,AS4,針對AS層面的Internet拓?fù)浣Y(jié)構(gòu)Internet拓?fù)洚a(chǎn)生器（網(wǎng)絡(luò)拓?fù)淠Ｐ停?第1代： 20世紀(jì)80年代 隨即圖產(chǎn)生器 第2代： 20世紀(jì)90年代 結(jié)構(gòu)產(chǎn)生器 第3代： 2000年以來 基于網(wǎng)絡(luò)節(jié)點度的產(chǎn)生器,3.2 Internet的拓?fù)涮匦?A visualization of the network structure of the Internet,本節(jié)大部分關(guān)于Internet拓?fù)涮匦缘姆治鍪腔贠regon的數(shù)據(jù)，由NLANR每天采集一次BGP路由表的信息收集而成。,Skitter： 由CAID

3、A每天采集連續(xù)的基于Trace-route的Internet拓?fù)錅y量值。 WHOIS： 是一系列包含關(guān)于網(wǎng)絡(luò)運行者重要信息的數(shù)據(jù)庫；是一個用來查詢域名是否已經(jīng)被注冊，以及注冊域名的詳細(xì)信息的數(shù)據(jù)庫（如域名所有人、域名注冊商、域名注冊日期和過期日期等）。 人工維持的，不能及時更新。,3.2.1 冪律分布,Faloutsos 三兄弟,dv rvR 節(jié)點出度與該節(jié)點等級的R 次冪成比例 dv是節(jié)點v的度，rv是將網(wǎng)絡(luò)中節(jié)點按度降序排列節(jié)點v的序列號，R是秩指數(shù)常數(shù)。,Dd dD 度大于d 的節(jié)點在網(wǎng)絡(luò)拓?fù)渲兴及俜直扰c節(jié)點出度d 的D 次冪成比例 Dd表明度大于d的節(jié)點在整個網(wǎng)絡(luò)中所占的百分比，D是

4、度指數(shù)常數(shù)。可以推得R=1/D。,i i 特征值i 與其次序i 的次冪成比例. i為網(wǎng)絡(luò)對應(yīng)的連接矩陣的特征值，i為將特征值按降序排列時的序列號。特征值指數(shù)和連接度指數(shù)D間存在近似關(guān)系 0.5D。,P(h) hH (h時) P(h)為距離不超過h的節(jié)點對的數(shù)目(也稱為hop內(nèi)的節(jié)點對的數(shù)目)，H是hop指數(shù)常數(shù)。,c=N+2M, N、M和分別為網(wǎng)絡(luò)節(jié)點數(shù)、邊數(shù)和直徑,四種冪率指數(shù)的演化情況：,3.2.2 層次性,Internet可以被看作是由大量的相互連接的AS系統(tǒng)組成 每個AS系統(tǒng)可以被看作Stub域或Transit域 Stub域由一些相互連接的LAN組成 Stub域承載域內(nèi)的通信量 Tra

5、nsit域一般是WAN或MAN Transit域有效地連接Stub域 是區(qū)域或國家層主干網(wǎng)絡(luò),看作客戶。 客戶-供應(yīng)商關(guān)系,每個AS可以被看作屬于特定的層次(Tier) 最高層內(nèi)的AS屬于Transit域，稱為Tier-1供應(yīng)商 較低層次的Transit域或Stub域依賴于其上層的Transit節(jié)點與網(wǎng)絡(luò)內(nèi)的其他域進(jìn)行通信；也可以通過同一層內(nèi)的對等關(guān)系的其他Transit域發(fā)送信息 各層的平均度： Tier1：614.29 Tier2：19.30 Tier3：6.93 Tier4：4.30,3.2.3 富人俱樂部特性,3.2.3 富人俱樂部特性,Internet中少量節(jié)點具有大量的邊，這些節(jié)點

6、稱為“富節(jié)點(rich nodes)”；它們傾向于彼此之間相互連接，構(gòu)成“富人俱樂部(rich-club)”； (r/N)表示網(wǎng)絡(luò)中前r個度最大的節(jié)點之間，實際存在的邊數(shù)L與這r個節(jié)點之間總的可能存在的邊數(shù)r(r-1)/2的比值。 如果(r)=1，那么前r個最富有 的節(jié)點組成的富人俱樂部為一個 完全連接的子圖。,RCC(rich-clud connectivity)，只考慮節(jié)點度排名靠前的節(jié)點連接程度，是聚集系數(shù)的一種特殊情況。它反映了互聯(lián)網(wǎng)拓?fù)鋵哟涡?，描述了核心層的連接情況。,rich club connectivity,對于所有具有給定度的節(jié)點的鄰居節(jié)點的平均度分布 P(k|k)表示度為k

7、的節(jié)點 連接到度為k的節(jié)點的概率。 Internet統(tǒng)計結(jié)果可見， 一個節(jié)點的度越高， 它的鄰居的平均度就越低。,3.2.4 異配性,同配性系數(shù)(assortativity coefficient) ji和ki分別為第i條邊的兩個端點的度數(shù)，M為網(wǎng)絡(luò)中邊數(shù)。 若r0，則網(wǎng)絡(luò)是同配的(assortative)；-正相關(guān)的 若r0，則網(wǎng)絡(luò)是異配的(disassortative)。-負(fù)相關(guān)的 若r=0，則網(wǎng)絡(luò)無相關(guān)性 技術(shù)網(wǎng)絡(luò)一般是異配的，包括AS層面的Internet網(wǎng)絡(luò) 社會網(wǎng)絡(luò)通常是同配的,3.2.4 異配性,Average neighbor connectivity as a functio

8、n of node degree,3.2.5 核數(shù)和介數(shù),核數(shù)（coreness） 一個圖的k-核(k-core)是指反復(fù)去掉度小于或等于k的節(jié)點后，所剩余的子圖。 若一個節(jié)點存在于k-核，而在(k+1)-核中被移去，那么此節(jié)點的核數(shù)(coreness)為k。 度為1的節(jié)點的核數(shù)為0。 節(jié)點核數(shù)中最大值稱為圖的核數(shù),節(jié)點核數(shù)在某種程度上說是比節(jié)點度數(shù)更反映關(guān)聯(lián)性的度量指標(biāo)，可以表明節(jié)點在核中的深度。 一個節(jié)點的度數(shù)很高，它的核數(shù)也可能很小。這說明其關(guān)聯(lián)并不緊密，與鄰居節(jié)點的連通性容易破壞。,K=0,K=1 反復(fù)去掉度=1的節(jié)點,Internet 節(jié)點的度數(shù)與核數(shù)的關(guān)系： 當(dāng)度數(shù)較小時呈現(xiàn)冪率關(guān)

9、系 當(dāng)節(jié)點度數(shù)大于100時 核數(shù)基本保持不變,3.2.5 核數(shù)和介數(shù),Internet的節(jié)點核數(shù)與度數(shù)之間的關(guān)系,介數(shù)(betweenness centrality) 通常分為邊介數(shù)和節(jié)點介數(shù)兩種： 節(jié)點介數(shù)定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該節(jié)點的路徑的數(shù)目占最短路徑總數(shù)的比例. 邊介數(shù)定義為網(wǎng)絡(luò)中所有最短路徑中經(jīng)過該邊的路徑的數(shù)目占最短路徑總數(shù)的比例. 介數(shù)反映了相應(yīng)的節(jié)點或者邊在整個網(wǎng)絡(luò)中的作用和影響力，是一個重要的全局幾何量，具有很強的現(xiàn)實意義。 節(jié)點介數(shù)衡量了通過網(wǎng)絡(luò)中該節(jié)點的最短路徑的數(shù)目,反映了節(jié)點在網(wǎng)絡(luò)中的樞紐性,節(jié)點介數(shù)越大,說明這個節(jié)點的樞紐性越強,刪除這樣的節(jié)點會造成大量節(jié)點

10、對之間的最短路徑變長; 邊介數(shù)定義為在網(wǎng)絡(luò)的所有最短路徑中,通過某條邊的最短路徑的條數(shù),類似地,邊介數(shù)也同樣反映了該邊在網(wǎng)絡(luò)中的樞紐性. 例如，在社會關(guān)系網(wǎng)或技術(shù)網(wǎng)絡(luò)中，介數(shù)的分布特征反映了不同人員、資源和技術(shù)在相應(yīng)生產(chǎn)關(guān)系中的地位，這對于發(fā)現(xiàn)和保護關(guān)鍵資源、技術(shù)和人才具有重要意義。,介數(shù) 一個節(jié)點的介數(shù)衡量了通過網(wǎng)絡(luò)中該節(jié)點的最短路徑的數(shù)目。 Internet拓?fù)鋽?shù)據(jù)： 節(jié)點的度數(shù)和介數(shù)呈現(xiàn) 明顯的冪率關(guān)系。,Internet的節(jié)點的標(biāo)準(zhǔn)化介數(shù)與度數(shù)之間的關(guān)系,網(wǎng)絡(luò)拓?fù)渖?網(wǎng)絡(luò)拓?fù)渖?，是通過對現(xiàn)實網(wǎng)絡(luò)進(jìn)行建模，然后利用模型生成網(wǎng)絡(luò)拓?fù)涞姆椒ā?它與網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)是不同的，后者是從一臺設(shè)備出

11、發(fā)，探測周圍的網(wǎng)絡(luò)拓?fù)涞姆椒ā?目前的網(wǎng)絡(luò)拓?fù)渖赡Ｐ椭饕墙⒃陔S機模型、層次結(jié)構(gòu)模型或冪律模型的基礎(chǔ)上，常用的拓?fù)渖煞椒?模型有Waxman，Tiers，Transit-stub，BA，Inet等。其中Waxman為隨機模型，Tiers和Transit-stub建立在層次結(jié)構(gòu)的基礎(chǔ)上，BA和Inet都是基于冪律模型。Brite和Inet則是典型的拓?fù)渖善?拓?fù)渖善魇峭負(fù)渖伤惴ǖ能浖崿F(xiàn)，是生成拓?fù)涞墓ぞ?隨機型，即認(rèn)為網(wǎng)絡(luò)拓?fù)鋱D處于一個完全無序的狀態(tài),在大尺度上是均一的最早的隨機模型是由Waxman提出來的。Waxman認(rèn)為節(jié)點之間的連接概率與其距離相關(guān),服從泊松分布,距離越近,概

12、率越大。 層次型，來自對網(wǎng)絡(luò)結(jié)構(gòu)所具有的層次特征的認(rèn)識，在同一層上的節(jié)點出度接近，不同層間節(jié)點出度差別很大。對同一層上的節(jié)點布置借用Waxman模型方法。 冪律型，1999年，F(xiàn)aloutsos等人對NLANR(National Lab for Applied Network Research)在1997-1998年間的3份BGP數(shù)據(jù)以及1995年的一份tracerouter測量數(shù)據(jù)進(jìn)行分析,發(fā)現(xiàn)網(wǎng)絡(luò)拓?fù)渲写嬖谥鴥缏梢?guī)律。,3.3 隨機圖產(chǎn)生器,步驟： 在nn的平面上均勻放置N個節(jié)點； 兩節(jié)點u和v之間建立邊的概率為： 0, 1, d(u,v)是節(jié)點u和v之間的歐氏距離， 為平均連接度，L是圖

13、中相距最遠(yuǎn)的兩節(jié)點之間的歐式距離, 決定了邊的平均長度。 如果增大，則邊的生成概率增大，使得最后生成的圖中邊的數(shù)目增加； 如果 增加，則使得最后生成的圖中較長的邊相對于較短的邊出現(xiàn)的概率增加。,隨機圖產(chǎn)生器,Waxman圖中相距較遠(yuǎn)的兩節(jié)點存在邊的可能性較小，從而獲得連通圖的可能性也較小，通常用來對網(wǎng)絡(luò)中的最大連通子圖進(jìn)行研究。,隨機圖產(chǎn)生器,頻率fd表示網(wǎng)絡(luò)中度為d的節(jié)點的個數(shù)，其對數(shù)分布如上圖所示(5000個節(jié)點),由于在基于隨機圖的拓?fù)淠Ｐ椭?節(jié)點度數(shù)會隨著節(jié)點數(shù)量的增加而增加,因此,隨機圖拓?fù)淠Ｐ蜔o法生成節(jié)點眾多且節(jié)點平均度較小的網(wǎng)絡(luò).,3 .4 結(jié)構(gòu)產(chǎn)生器,Tiers產(chǎn)生器 Tran

14、sit-Stub產(chǎn)生器,1 Tiers產(chǎn)生器,Tiers產(chǎn)生器用于表現(xiàn)廣域網(wǎng)、中域網(wǎng)和局域網(wǎng)這三個層次間的關(guān)系及內(nèi)部聯(lián)系。 在Tiers中需要指定MAN和LAN的目標(biāo)個數(shù)，其中LAN采用星形拓?fù)浣Y(jié)構(gòu)。,1 Tiers產(chǎn)生器,Tiers產(chǎn)生器的參數(shù)： WAN的個數(shù)Nw(一般把Nw設(shè)為1)； 每個WAN內(nèi)的節(jié)點的個數(shù)SW； MAN的個數(shù)NMSW； 每個MAN內(nèi)的節(jié)點的個數(shù)SM； 每個MAN內(nèi)LAN的個數(shù)NLSM； 每個LAN內(nèi)節(jié)點的個數(shù)SL； 節(jié)點總數(shù)：NSWNMSMNMNLSL。 WAN、MAN和LAN的內(nèi)部網(wǎng)絡(luò)冗余度，即一個節(jié)點到另一個相同類型節(jié)點的連接度，分別為RW、RM和RL。其數(shù)值通常分

15、別為3、2、1。 網(wǎng)絡(luò)間的冗余度：WAN和MAN間的連接個數(shù)RMW；MAN和LAN之間的連接個數(shù)RLM。,1 Tiers產(chǎn)生器,Tiers產(chǎn)生器的步驟： 創(chuàng)建WAN。隨機地在格子內(nèi)放置節(jié)點，如果一個節(jié)點與另一個節(jié)點距離非常近，就將其舍棄。 當(dāng)放置的節(jié)點的個數(shù)達(dá)到所需的目標(biāo)個數(shù)后，在這些節(jié)點間建立最小生成樹。 隨機地檢查每個節(jié)點，看它們是否滿足RW。一個節(jié)點與對等節(jié)點間邊的個數(shù)可能多于RW，則不需要再額外的邊。如果與對等節(jié)點間少于RW條邊，則需要添加它與網(wǎng)絡(luò)中最近的節(jié)點的邊。 類似地，可采用上述三步驟創(chuàng)建MAN網(wǎng)絡(luò)。只是當(dāng)兩節(jié)點相距很近時，不需舍棄其中之一。 創(chuàng)建LAN網(wǎng)絡(luò)。在每個LAN內(nèi)隨機選

16、擇一個節(jié)點作為星形拓?fù)涞闹行模賹AN內(nèi)其他的每個節(jié)點與它之間建立一條邊。若RL1則采用與步驟3類似的操作加邊。,1 Tiers產(chǎn)生器,建立網(wǎng)絡(luò)之間的連接： 將MAN連接到WAN上。從SW個WAN節(jié)點內(nèi)隨機選取NM個節(jié)點組成一個集合A，在A內(nèi)的每個節(jié)點和從每個MAN內(nèi)隨機選取的一個節(jié)點x間建立邊，所以，每個MAN就通過一條邊連接在WAN上。 如果RMW1，那么,對于每個MAN，在MAN的另外一個節(jié)點（也可能會再是x）和x已經(jīng)連接到A中的那個節(jié)點相距最近的節(jié)點間建立邊。 與上述步驟相類似，將LAN連接到MAN。, ,1 Tiers產(chǎn)生器,以上步驟所建立的網(wǎng)絡(luò)具有較大的網(wǎng)絡(luò)直徑：,2 Trans

17、it-Stub產(chǎn)生器,Transit-Stub產(chǎn)生器 產(chǎn)生具有三個層次的網(wǎng)絡(luò)：Transit層、Stub層、LAN層 每層上的節(jié)點被限制在一個個的矩形空間內(nèi)，其中不同層次的限制空間是不同的，最下層的LAN空間最小。,產(chǎn)生器有兩組控制參數(shù)： 控制域的相對大小的參數(shù)： T：所有Transit域的個數(shù)，T1； NT：每個Transit域的平均節(jié)點個數(shù)，NT1； S：每個Transit域的平均Stub域個數(shù)，S1； NS：每個Stub域的平均節(jié)點個數(shù)，NS1； L：每個Stub域的平均LAN數(shù)，L1； NL：每個LAN的平均主機個數(shù)，NL1； 路由器節(jié)點和主機總是分別記為NR和NH，滿足： NR=TN

18、T(1+SNS)，NH=TNTSNSLNL。,Transit-Stub產(chǎn)生器,控制域內(nèi)和域間的連通性的參數(shù)： ET：一個Transit域節(jié)點和本域其他節(jié)點間邊的平均數(shù)，ET2； ES：一個Stub域節(jié)點和本域其他節(jié)點間邊的平均數(shù)，Es2； ETT：一個Transit域節(jié)點和其他Transit域之間邊的平均數(shù)，ETT2； EST：一個Stub域和一個Transit域間邊的平均數(shù)，EST1；每個Stub域至少和一個Transit域相連。 ELS：一個LAN域和一個Stub域之間邊的平均數(shù)，ELS1；每個LAN域至少和一個Stub域相連。 所有參數(shù)必須足夠大，使得層內(nèi)和層間是連通的。,Transit

19、-Stub產(chǎn)生器,Transit-Stub產(chǎn)生器的建模步驟： 在指定的位置上生成所有的Transit域?？捎扇魏我环N隨機方法（一般用Waxman方法）生成一張隨機圖，圖中每個節(jié)點代表一個Transit域；并保證生成的圖是連通的； 為每一個Transit域生成節(jié)點，將節(jié)點放置在環(huán)繞Transit域位置的子域內(nèi)，使得Transit域平均含有NT個節(jié)點；在每個Transit域內(nèi)連接邊，使得此域連通，滿足NT2,ER2. 在每一個Transit域中隨機選取合適的節(jié)點作為Transit域間連接邊的端點。,4. 為每一個Transit節(jié)點的Stub域選擇合適的位置，并在這個位置周圍生成相應(yīng)Stub域的節(jié)點

20、，使每個Stub域內(nèi)包含NS個節(jié)點，并將其連接起來。 5. 每個Stub域都要和Transit域相連。如果EST1，那么隨機增加額外的從Stub域到Transit域的邊，并從Stub域中選擇一個節(jié)點與相應(yīng)的Transit節(jié)點間加一條邊。 6. 生成LAN，以星形結(jié)構(gòu)設(shè)置主機節(jié)點。 7. 把每個LAN連接到相應(yīng)的Stub節(jié)點的中心路由器上；若ELN1，則額外地增加中心路由器和Stub節(jié)點間的連接。,Transit-Stub產(chǎn)生器,Transit-Stub產(chǎn)生器 生成的節(jié)點度的頻率fd的對數(shù)分布圖：,3.5 基于連接度的產(chǎn)生器,1. 靜態(tài)模型Inet（不考慮增長性） 在建模過程中采用非線性優(yōu)先的連

21、接方式,通過初始放置所有節(jié)點,并對每個節(jié)點分配連接度,從而有層次地添加邊。 盡管Inet 無法反應(yīng)Internet 的動態(tài)變化,但對于某種特定規(guī)模的Internet 網(wǎng)絡(luò),能夠較為真實地反應(yīng)某些拓?fù)涮匦?如度分布遵循冪律分布,且最大度也接近真實網(wǎng)絡(luò)的實際值等。 Winick 和Jamin提出Inet 模型可模擬3037 個節(jié)點的實際網(wǎng)絡(luò),即1997 年Internet 網(wǎng)絡(luò)中的自治域數(shù)目,線性優(yōu)先,回歸模型,1. Inet,Inet 從用戶那里獲得節(jié)點個數(shù)N和N個節(jié)點中度為1的節(jié)點所占的比例k。 根據(jù)下式計算Internet從1997年11月份的節(jié)點個數(shù)增長到N所需的月份數(shù)t： N=exp(0

22、.0298t + 7.9842) 定義V1,Vtop3和V： V1是度為1的節(jié)點的集合， Vtop3為前三個最大度的節(jié)點的集合， V為除去V1,Vtop3中節(jié)點以外的其他節(jié)點。,代入t，根據(jù)F(d)=ecdat+b來計算V中節(jié)點的度分布，其中 ，a、b、c為常數(shù)。 Internet上度為1的節(jié)點所占比例基本上維持在30%左右。根據(jù)度秩指數(shù)增長律d=ept+qrR來計算Vtop3中節(jié)點的度分布，其中p、q為已知常數(shù)。 在度大于1的節(jié)點間構(gòu)建一個生成樹：令G為所要產(chǎn)生的圖，初始為空集；不在G中的度大于1的節(jié)點i與G中的一個節(jié)點j相連的概率為： 其中 di為節(jié)點i的度，f(di)為度的頻率。,按概率

23、公式，將V1中的kN個節(jié)點連接到G中的節(jié)點上。 從具有最大度的節(jié)點開始，連接G中仍剩余的自由度；在進(jìn)行這些連接時，以概率公式隨機的選取有著自由度的節(jié)點。,2.AB模型,動態(tài)模型BA: 是第一個演化網(wǎng)絡(luò)模型,由Barabasi 和Albert 等人提出,現(xiàn)在拓?fù)浣Ｑ芯恐衅毡閷⑵渥鳛闊o標(biāo)度網(wǎng)絡(luò)基本模型.BA 模型也是第一個從動態(tài)增長觀點研究復(fù)雜網(wǎng)絡(luò)具有冪律度分布特性的模型,并論證了生成無標(biāo)度網(wǎng)絡(luò)的兩條重要機理:增長和擇優(yōu)。 但是,BA 模型對初始網(wǎng)絡(luò)沒有完全設(shè)定,只說明開始給定n0 個節(jié)點,但這n0 個節(jié)點間如何建邊尚未討論,而對于不同的初始網(wǎng)絡(luò),其后演化的結(jié)果網(wǎng)絡(luò)并不相同; 并且,BA 模型的

24、算法可能導(dǎo)致重復(fù)建邊.另外,優(yōu)先連接也并不適用于所有出現(xiàn)冪律分布的情形,即便是對于某些無標(biāo)度網(wǎng)絡(luò),利用優(yōu)先連接來解釋冪律的形成機理也很不合理.,AB 模型: 是Albert 和Barabasi 對BA 模型的修正, 該模型采用了線性優(yōu)先的連接方式,通過概率增加點和邊,并對內(nèi)部邊重新配置,保證了孤立節(jié)點建立新連接的可能性,逐步生成動態(tài)的AS 級拓?fù)淠Ｐ? AB模型的連接度分布呈現(xiàn)冪律,且冪律指數(shù)接近真實網(wǎng)絡(luò).但是,它在聚類系數(shù)和特征路徑長度上存在著很強的負(fù)相關(guān)性,其聚類系數(shù)嚴(yán)重低于網(wǎng)絡(luò)實際值;并且,在最大連接度和次最大連接度等方面也都和實際網(wǎng)絡(luò)存在較大的偏差.,AB模型的構(gòu)建過程： 初始有m0個

25、孤立節(jié)點，每一步執(zhí)行下面三個步驟中的一個： 以概率p增加m(mm0)條新的內(nèi)部連接，即在已存在的節(jié)點間添加新的邊：隨機選取一個節(jié)點作為新的邊的起點，邊的另一個端點由以下概率決定： 重復(fù)此過程m次。,2. 以概率q重新配置m條邊。隨機選取節(jié)點i和連接到i的一個邊lij，然后移走此邊，以連接節(jié)點i和節(jié)點j的新邊lij取代。每次根據(jù)公式的概率選取j來配置一條邊，并重復(fù)此過程m次。 3. 以概率1-p-q增加一個新節(jié)點。根據(jù)以上公式所示概率分別與網(wǎng)絡(luò)中已存在的m個節(jié)點連接。 其中，0p1，0q1-p； 概率公式采用(ki+1)，保證了孤立節(jié)點可以建立新邊,3. BRITE 模型,BRITE 模型: 是

26、一種采用Waxman 概率與線性優(yōu)先相結(jié)合方式的動態(tài)自治域級拓?fù)淠Ｐ?其特點在于反映實際Internet 拓?fù)涞亩嗝嫘?如層次性和連接度分布等,對于不同的參數(shù)及不同的節(jié)點分布方式,BRITE 會產(chǎn)生不同的拓?fù)涮匦?另外,在建模過程中,它將當(dāng)時已存在的Waxman, AB, Inet 都融合其中,并提供了更好的接口界面供仿真使用.,3. BRITE 模型,BRITE： BRITE期望能構(gòu)建一個具有代表性、包容性和交互性的拓?fù)洚a(chǎn)生器： 代表性： 指期望反映Internet實際拓?fù)涞亩鄠€方面，如層次性、連接度分布等 包容性： 指將多個已存在的拓?fù)洚a(chǎn)生器的功能融合在一個拓?fù)洚a(chǎn)生器之中 交互性： 指為廣

27、泛使用的仿真應(yīng)用提供更好的接口界面。,Table: Parameters of BRITE,Figure 6: Snapshot of BRITEs GUI main window,BRITE模型的構(gòu)建過程： 在平面上放置節(jié)點； 在節(jié)點間建立內(nèi)部邊； 為每個拓?fù)湓卦O(shè)置屬性； 以一定的形式輸出此拓?fù)浣Y(jié)構(gòu)。 將平面分成HSHS個正方形，每個正方形被進(jìn)一步分成LSLS個小的正方形，每個小正方形內(nèi)最多分配一個節(jié)點。 平面上節(jié)點的隨機放置：根據(jù)一致隨機分布或者Pareto重尾(haevy-tailed)分布來分配每個大正方形內(nèi)的節(jié)點個數(shù)。隨機選取一個小正方形，在避免沖突的情況下，將一個節(jié)點放入其中。,

28、初始產(chǎn)生一個有著m0個節(jié)點的隨機圖作為主干，然后添加其他的節(jié)點。 如果參數(shù)IG(incremental growth)為0，則將所有節(jié)點一次全部放置在平面上，然后隨機選取一個節(jié)點，與其他節(jié)點建立m條邊； 如果IG為1，則每步添加一個節(jié)點，將其與網(wǎng)絡(luò)中的已存在的節(jié)點間建立m條邊，m越大拓?fù)湓矫堋?4. 節(jié)點間連接概率的確定： 如果參數(shù)PC(preferential connectivity)為0，則按Waxman概率式 ，將所考慮的新節(jié)點v與節(jié)點i相連 如果PC為1，則v與i相連的概率為BA線性優(yōu)先連接概率； 如果PC為2，則v與i相連的概率為： 其中，wi為Waxman概率。,當(dāng)PC=IG=0

29、時，BRITE采用點隨機分布所產(chǎn)生的拓?fù)浼礊閃axman拓?fù)洌?當(dāng)PC=IG=1時，BRITE所產(chǎn)生的拓?fù)湓趦缏手笖?shù)和特征路徑長度等方面最接近Internet的實際拓?fù)洌?4.GLP模型,GLP模型 現(xiàn)實Internet中的節(jié)點比BA線性優(yōu)先連接更傾向于連接到高連接度的節(jié)點上 廣義線性優(yōu)先(generalized linear preference, GLP)模型正是基于此觀察而提出的，使其滿足小世界性。 其建模步驟如下：,通過m0-1條邊，將m0個節(jié)點連接起來，其中每一步執(zhí)行下面兩個操作中的其一： 以概率p0,1增加m條新邊(mm0)，節(jié)點i被選作為一條邊的端點的概率為： 其中(-, 1)是

30、一個可調(diào)節(jié)參數(shù)，它表明新節(jié)點或新邊更傾向于受歡迎的節(jié)點。 以概率1-p增加一個新節(jié)點和此新節(jié)點的m條新邊。系統(tǒng)中已存在的節(jié)點i被選中的概率(ki)由以上公式確定。,5. PFP模型,PFP模型 AS層Internet存在“富人俱樂部”現(xiàn)象，正反饋優(yōu)先(positive feedback preferential, PFP)模型正是在研究此現(xiàn)象的基礎(chǔ)上提出的。 PFP模型是基于新節(jié)點和內(nèi)部邊兩個方面的交互增長、非線性優(yōu)先連接兩個機理構(gòu)建的。 每一步除了將新節(jié)點連接到已存在的host節(jié)點上，還會將host連接到其他已存在的節(jié)點上，從而產(chǎn)生內(nèi)部邊。當(dāng)選擇所要連接的已存在的節(jié)點時，采用非線性優(yōu)先連接概

31、率： 其中，0, 1,以概率p增加一個新節(jié)點，它與一個host節(jié)點建立一條外部邊；同時，此host節(jié)點與網(wǎng)絡(luò)中已存在的一個對等節(jié)點間建立一條新的內(nèi)部邊； 以概率q增加一個新節(jié)點，它與一個host節(jié)點建立一條外部邊；同時此host節(jié)點與兩個對等節(jié)點建立兩條內(nèi)部邊； 以概率1-p-q將新節(jié)點連接到兩個host節(jié)點上；同時其中一個host節(jié)點與一個對等節(jié)點建立一條內(nèi)部邊。 這里p0, 1, q0, 1-p,6. DP模型,DP模型 Internet的不同AS間具有消費者-供應(yīng)商關(guān)系或?qū)Φ汝P(guān)系，當(dāng)存在其中一種關(guān)系時，彼此間建立邊。 動態(tài)優(yōu)先(dynamic and preferential, DP)模

32、型正是對這種情況的建模，模型建立的兩個假設(shè)前提為： 兩個存在的AS間，連接度較低的為消費者，連接度較高的為供應(yīng)商 消費者決定將要連接到哪個供應(yīng)商上，即由消費者來選擇供應(yīng)商,令i是消費者，將由它產(chǎn)生一個新邊，ki是i的頂點度。V(ki+)是連接度較高的一組節(jié)點，為一常數(shù)。那么i選擇j為供應(yīng)商的概率為： 即i所選擇的供應(yīng)商的連接度總是要比ki+大，且在其中優(yōu)先選擇那些具有較大連接度的節(jié)點。,DP模型 以概率p在已存在的節(jié)點中產(chǎn)生一條新的內(nèi)部邊，即隨機選擇一個節(jié)點作為消費者，按概率將其連接到一個供應(yīng)商上。,以概率1-p增加一個新節(jié)點和外部的m條邊。由于Internet的平均連接度隨時間連續(xù)變化，為了

33、反映此種情況，將p設(shè)為動態(tài)改變的。 設(shè)P(N)為“增加的內(nèi)部邊”與“增加的所有邊”的平均比值，即P(N)=In/(N+In)，In=L-Nm， N是節(jié)點個數(shù)，L是邊數(shù)，In是1997年11月后所增加的內(nèi)部邊數(shù)。可由下面公式計算得到邊增加概率： 由經(jīng)驗數(shù)據(jù)，令p(0)=0.3, =1，便可以產(chǎn)生在一定程度上與Internet接近的拓?fù)浣Y(jié)構(gòu)。,7. TANG模型,TANG模型 由于BA模型不是專門針對Internet建模而提出的，將其應(yīng)用于Internet拓?fù)浣Y(jié)構(gòu)會有很多不足： BA模型中沒有葉子節(jié)點，而Internet中葉子節(jié)點比例約有30%； BA模型的冪率指數(shù)為3，而Internet的冪率指

34、數(shù)約為2.2； BA模型不能產(chǎn)生Internet中的密集核心；,TANG模型能很好地刻畫以上拓?fù)涮匦?，其?gòu)建基于兩種思想： 增量加邊(incremental edge addition, InEd) 超線性優(yōu)先連接(super-linear preferential attachment, SliP)。 模型構(gòu)建步驟如下： 起始有m0個節(jié)點，每一步增加一個新節(jié)點和m條邊。一條外部邊將新節(jié)點與已存節(jié)點相連，而在已存網(wǎng)絡(luò)中增加m-1條內(nèi)部邊，其中已存節(jié)點被選作邊的一端的概率為： 其中，0時為超線性優(yōu)先連接。,GDTANG模型具體步驟（有向地理區(qū)域模型） 定義l個不同的地理區(qū)域，每一步增加一個新節(jié)點

35、和m條由客戶指向供應(yīng)商的有向邊。根據(jù)分布Pl隨機選擇一個地理區(qū)域，再用一條有向邊將新節(jié)點v與此區(qū)域中的一個節(jié)點i進(jìn)行相連，其中選擇節(jié)點i的概率為： 這里yi為節(jié)點i的出度 將v和i分別看作客戶和供應(yīng)商；,在已存節(jié)點間建立m-1條邊，節(jié)點i被選作客戶的概率為： 這里ki為節(jié)點i的入度 節(jié)點j被選作供應(yīng)商的概率有上面第一個公式?jīng)Q定，其中這m-1條邊中無向邊的概率為p，邊的兩個端點在同地理區(qū)域內(nèi)的概率為。令p=0.07，=0.5，便可得到在一定程度上與實際Internet值相接近的拓?fù)涮匦浴?3.6 多局域世界模型,模型構(gòu)造 在AS層面上，可以將Internet的層次分為國際連接、國家主干、區(qū)域網(wǎng)絡(luò)

36、和局域網(wǎng)。區(qū)域網(wǎng)內(nèi)的節(jié)點緊密連接使得此網(wǎng)絡(luò)內(nèi)具有很高的聚合系數(shù)，而這些高度聚合的區(qū)域網(wǎng)由國際連接或國家主干稀疏地相互聯(lián)系在一起。 當(dāng)一個新節(jié)點加入到一個區(qū)域網(wǎng)絡(luò)時，它對其他區(qū)域網(wǎng)中的節(jié)點影響非常小，而它反過來主要受本區(qū)域中的節(jié)點的影響。 將區(qū)域網(wǎng)看作一個“局域世界”，那么整個Internet可以看作是由很多區(qū)域世界組成的。 MLW,模型構(gòu)造： 起始為m個孤立的局域世界，在每個局域世界內(nèi)部均有m0個節(jié)點、e0條邊。,m0 e0,m0 e0,m0 e0,m0 e0,每一步隨機地進(jìn)行如下的一個操作： 新AS 的產(chǎn)生： 以概率p增加一個擁有m0個節(jié)點、e0條邊的局域世界 新節(jié)點的產(chǎn)生： 以概率q將一個

37、新節(jié)點加入到一個已存在的局域世界中，它與同一個局域世界中的節(jié)點建立m1條邊。 首先隨機地選取一個局域世界，此局域世界中，新節(jié)點將要連接的節(jié)點由如下概率選?。?重復(fù)此過程m1次。,新鏈接的產(chǎn)生： 以概率r增加m2條邊到一個選定的局域世界。 首先隨機地選取一個局域世界，邊的一端隨機選取，另一端根據(jù)以上概率公式選定。重復(fù)此過程m2次。 鏈接的消亡：為刻畫邊的消亡，以概率s在一個選定的局域世界內(nèi)去掉m3條邊。首先隨機選取一端，另一端由如下概率選定： 其中N(t)為局域世界內(nèi)的節(jié)點個數(shù)。重復(fù)此過程m3次。,局域世界間的連接： 以概率u在一個選定的局域世界與其他已存在的局域世界間建立m4條長程邊。 首先隨機選取一個局域世界，在其內(nèi)部根據(jù)上面第一個概率公式選定一個節(jié)點，作為邊的一端，邊的另一端位于另一個隨機選取的局域世界內(nèi)，選定概率仍為第一個概率公式。重復(fù)次過程m4次。 上述參數(shù)滿足：0q1, 0p, r, s, u1, p+q+r+s+u=1。,度分布分析,=1+1/ 若要求MLW模型冪率指數(shù)在23之間，還需滿足下列條件： 可以驗證，若另rm22sm3，那么上面的條件公式就能得到滿足