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

1、第3章 Internet拓?fù)涮匦约敖?3.1 引言 3.2 Internet的拓?fù)涮匦?3.3 隨機(jī)圖產(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)中，一個(gè)自治系統(tǒng)(AS)是一個(gè)有權(quán)自主地決定在本系統(tǒng)中應(yīng)采用何種路由協(xié)議的小型單位。 由單一行政部門所管理的子網(wǎng)絡(luò)，可由高達(dá)數(shù)以百計(jì)的路由器組成。,節(jié)點(diǎn)為路由器，邊為路由器之間的物理連接（如光纖）,（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,針對(duì)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年以來(lái) 基于網(wǎng)絡(luò)節(jié)點(diǎn)度的產(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(cè)量值。 WHOIS： 是一系列包含關(guān)于網(wǎng)絡(luò)運(yùn)行者重要信息的數(shù)據(jù)庫(kù)；是一個(gè)用來(lái)查詢域名是否已經(jīng)被注冊(cè)，以及注冊(cè)域名的詳細(xì)信息的數(shù)據(jù)庫(kù)（如域名所有人、域名注冊(cè)商、域名注冊(cè)日期和過(guò)期日期等）。 人工維持的，不能及時(shí)更新。,3.2.1 冪律分布,Faloutsos 三兄弟,dv rvR 節(jié)點(diǎn)出度與該節(jié)點(diǎn)等級(jí)的R 次冪成比例 dv是節(jié)點(diǎn)v的度，rv是將網(wǎng)絡(luò)中節(jié)點(diǎn)按度降序排列節(jié)點(diǎn)v的序列號(hào)，R是秩指數(shù)常數(shù)。,Dd dD 度大于d 的節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)渲兴及俜直扰c節(jié)點(diǎn)出度d 的D 次冪成比例 Dd表明度大于d的節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中所占的百分比，D是

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

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

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

7、的節(jié)點(diǎn) 連接到度為k的節(jié)點(diǎn)的概率。 Internet統(tǒng)計(jì)結(jié)果可見， 一個(gè)節(jié)點(diǎn)的度越高， 它的鄰居的平均度就越低。,3.2.4 異配性,同配性系數(shù)(assortativity coefficient) ji和ki分別為第i條邊的兩個(gè)端點(diǎn)的度數(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ò)無(wú)相關(guān)性 技術(shù)網(wǎng)絡(luò)一般是異配的，包括AS層面的Internet網(wǎng)絡(luò) 社會(huì)網(wǎng)絡(luò)通常是同配的,3.2.4 異配性,Average neighbor connectivity as a functio

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

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

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

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

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

13、中相距最遠(yuǎn)的兩節(jié)點(diǎn)之間的歐式距離, 決定了邊的平均長(zhǎng)度。 如果增大，則邊的生成概率增大，使得最后生成的圖中邊的數(shù)目增加； 如果 增加，則使得最后生成的圖中較長(zhǎng)的邊相對(duì)于較短的邊出現(xiàn)的概率增加。,隨機(jī)圖產(chǎn)生器,Waxman圖中相距較遠(yuǎn)的兩節(jié)點(diǎn)存在邊的可能性較小，從而獲得連通圖的可能性也較小，通常用來(lái)對(duì)網(wǎng)絡(luò)中的最大連通子圖進(jìn)行研究。,隨機(jī)圖產(chǎn)生器,頻率fd表示網(wǎng)絡(luò)中度為d的節(jié)點(diǎn)的個(gè)數(shù)，其對(duì)數(shù)分布如上圖所示(5000個(gè)節(jié)點(diǎn)),由于在基于隨機(jī)圖的拓?fù)淠Ｐ椭?節(jié)點(diǎn)度數(shù)會(huì)隨著節(jié)點(diǎn)數(shù)量的增加而增加,因此,隨機(jī)圖拓?fù)淠Ｐ蜔o(wú)法生成節(jié)點(diǎn)眾多且節(jié)點(diǎn)平均度較小的網(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)這三個(gè)層次間的關(guān)系及內(nèi)部聯(lián)系。 在Tiers中需要指定MAN和LAN的目標(biāo)個(gè)數(shù)，其中LAN采用星形拓?fù)浣Y(jié)構(gòu)。,1 Tiers產(chǎn)生器,Tiers產(chǎn)生器的參數(shù)： WAN的個(gè)數(shù)Nw(一般把Nw設(shè)為1)； 每個(gè)WAN內(nèi)的節(jié)點(diǎn)的個(gè)數(shù)SW； MAN的個(gè)數(shù)NMSW； 每個(gè)MAN內(nèi)的節(jié)點(diǎn)的個(gè)數(shù)SM； 每個(gè)MAN內(nèi)LAN的個(gè)數(shù)NLSM； 每個(gè)LAN內(nèi)節(jié)點(diǎn)的個(gè)數(shù)SL； 節(jié)點(diǎn)總數(shù)：NSWNMSMNMNLSL。 WAN、MAN和LAN的內(nèi)部網(wǎng)絡(luò)冗余度，即一個(gè)節(jié)點(diǎn)到另一個(gè)相同類型節(jié)點(diǎn)的連接度，分別為RW、RM和RL。其數(shù)值通常分

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

16、擇一個(gè)節(jié)點(diǎn)作為星形拓?fù)涞闹行?，再將LAN內(nèi)其他的每個(gè)節(jié)點(diǎn)與它之間建立一條邊。若RL1則采用與步驟3類似的操作加邊。,1 Tiers產(chǎn)生器,建立網(wǎng)絡(luò)之間的連接： 將MAN連接到WAN上。從SW個(gè)WAN節(jié)點(diǎn)內(nèi)隨機(jī)選取NM個(gè)節(jié)點(diǎn)組成一個(gè)集合A，在A內(nèi)的每個(gè)節(jié)點(diǎn)和從每個(gè)MAN內(nèi)隨機(jī)選取的一個(gè)節(jié)點(diǎn)x間建立邊，所以，每個(gè)MAN就通過(guò)一條邊連接在WAN上。 如果RMW1，那么,對(duì)于每個(gè)MAN，在MAN的另外一個(gè)節(jié)點(diǎn)（也可能會(huì)再是x）和x已經(jīng)連接到A中的那個(gè)節(jié)點(diǎn)相距最近的節(jié)點(diǎn)間建立邊。 與上述步驟相類似，將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)生具有三個(gè)層次的網(wǎng)絡(luò)：Transit層、Stub層、LAN層 每層上的節(jié)點(diǎn)被限制在一個(gè)個(gè)的矩形空間內(nèi)，其中不同層次的限制空間是不同的，最下層的LAN空間最小。,產(chǎn)生器有兩組控制參數(shù)： 控制域的相對(duì)大小的參數(shù)： T：所有Transit域的個(gè)數(shù)，T1； NT：每個(gè)Transit域的平均節(jié)點(diǎn)個(gè)數(shù)，NT1； S：每個(gè)Transit域的平均Stub域個(gè)數(shù)，S1； NS：每個(gè)Stub域的平均節(jié)點(diǎn)個(gè)數(shù)，NS1； L：每個(gè)Stub域的平均LAN數(shù)，L1； NL：每個(gè)LAN的平均主機(jī)個(gè)數(shù)，NL1； 路由器節(jié)點(diǎn)和主機(jī)總是分別記為NR和NH，滿足： NR=TN

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、反映此種情況，將p設(shè)為動(dòng)態(tài)改變的。 設(shè)P(N)為“增加的內(nèi)部邊”與“增加的所有邊”的平均比值，即P(N)=In/(N+In)，In=L-Nm， N是節(jié)點(diǎn)個(gè)數(shù)，L是邊數(shù)，In是1997年11月后所增加的內(nèi)部邊數(shù)?？捎上旅婀接?jì)算得到邊增加概率： 由經(jīng)驗(yàn)數(shù)據(jù)，令p(0)=0.3, =1，便可以產(chǎn)生在一定程度上與Internet接近的拓?fù)浣Y(jié)構(gòu)。,7. TANG模型,TANG模型 由于BA模型不是專門針對(duì)Internet建模而提出的，將其應(yīng)用于Internet拓?fù)浣Y(jié)構(gòu)會(huì)有很多不足： BA模型中沒(méi)有葉子節(jié)點(diǎn)，而Internet中葉子節(jié)點(diǎn)比例約有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個(gè)節(jié)點(diǎn)，每一步增加一個(gè)新節(jié)點(diǎn)和m條邊。一條外部邊將新節(jié)點(diǎn)與已存節(jié)點(diǎn)相連，而在已存網(wǎng)絡(luò)中增加m-1條內(nèi)部邊，其中已存節(jié)點(diǎn)被選作邊的一端的概率為： 其中，0時(shí)為超線性優(yōu)先連接。,GDTANG模型具體步驟（有向地理區(qū)域模型） 定義l個(gè)不同的地理區(qū)域，每一步增加一個(gè)新節(jié)點(diǎn)

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

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

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