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

2、P 發(fā)言人,BGP 發(fā)言人,BGP 發(fā)言人,AS1,AS3,AS2,AS5,AS4,針對AS層面的Internet拓撲結構Internet拓撲產生器（網絡拓撲模型） 第1代： 20世紀80年代 隨即圖產生器 第2代： 20世紀90年代 結構產生器 第3代： 2000年以來 基于網絡節(jié)點度的產生器,3.2 Internet的拓撲特性,A visualization of the network structure of the Internet,本節(jié)大部分關于Internet拓撲特性的分析是基于Oregon的數據，由NLANR每天采集一次BGP路由表的信息收集而成。,Skitter： 由CAID

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

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

5、nsit域一般是WAN或MAN Transit域有效地連接Stub域 是區(qū)域或國家層主干網絡,看作客戶。 客戶-供應商關系,每個AS可以被看作屬于特定的層次(Tier) 最高層內的AS屬于Transit域，稱為Tier-1供應商 較低層次的Transit域或Stub域依賴于其上層的Transit節(jié)點與網絡內的其他域進行通信；也可以通過同一層內的對等關系的其他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)”；它們傾向于彼此之間相互連接，構成“富人俱樂部(rich-club)”； (r/N)表示網絡中前r個度最大的節(jié)點之間，實際存在的邊數L與這r個節(jié)點之間總的可能存在的邊數r(r-1)/2的比值。 如果(r)=1，那么前r個最富有 的節(jié)點組成的富人俱樂部為一個 完全連接的子圖。,RCC(rich-clud connectivity)，只考慮節(jié)點度排名靠前的節(jié)點連接程度，是聚集系數的一種特殊情況。它反映了互聯網拓撲層次性，描述了核心層的連接情況。,rich club connectivity,對于所有具有給定度的節(jié)點的鄰居節(jié)點的平均度分布 P(k|k)表示度為k

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

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

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

10、對之間的最短路徑變長; 邊介數定義為在網絡的所有最短路徑中,通過某條邊的最短路徑的條數,類似地,邊介數也同樣反映了該邊在網絡中的樞紐性. 例如，在社會關系網或技術網絡中，介數的分布特征反映了不同人員、資源和技術在相應生產關系中的地位，這對于發(fā)現和保護關鍵資源、技術和人才具有重要意義。,介數 一個節(jié)點的介數衡量了通過網絡中該節(jié)點的最短路徑的數目。 Internet拓撲數據： 節(jié)點的度數和介數呈現 明顯的冪率關系。,Internet的節(jié)點的標準化介數與度數之間的關系,網絡拓撲生成,網絡拓撲生成，是通過對現實網絡進行建模，然后利用模型生成網絡拓撲的方法。 它與網絡拓撲發(fā)現是不同的，后者是從一臺設備出

11、發(fā)，探測周圍的網絡拓撲的方法。 目前的網絡拓撲生成模型主要是建立在隨機模型、層次結構模型或冪律模型的基礎上，常用的拓撲生成方法/模型有Waxman，Tiers，Transit-stub，BA，Inet等。其中Waxman為隨機模型，Tiers和Transit-stub建立在層次結構的基礎上，BA和Inet都是基于冪律模型。Brite和Inet則是典型的拓撲生成器 拓撲生成器是拓撲生成算法的軟件實現，是生成拓撲的工具,隨機型，即認為網絡拓撲圖處于一個完全無序的狀態(tài),在大尺度上是均一的最早的隨機模型是由Waxman提出來的。Waxman認為節(jié)點之間的連接概率與其距離相關,服從泊松分布,距離越近,概

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

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

14、sit-Stub產生器,1 Tiers產生器,Tiers產生器用于表現廣域網、中域網和局域網這三個層次間的關系及內部聯系。 在Tiers中需要指定MAN和LAN的目標個數，其中LAN采用星形拓撲結構。,1 Tiers產生器,Tiers產生器的參數： WAN的個數Nw(一般把Nw設為1)； 每個WAN內的節(jié)點的個數SW； MAN的個數NMSW； 每個MAN內的節(jié)點的個數SM； 每個MAN內LAN的個數NLSM； 每個LAN內節(jié)點的個數SL； 節(jié)點總數：NSWNMSMNMNLSL。 WAN、MAN和LAN的內部網絡冗余度，即一個節(jié)點到另一個相同類型節(jié)點的連接度，分別為RW、RM和RL。其數值通常分

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、時，BRITE采用點隨機分布所產生的拓撲即為Waxman拓撲； 當PC=IG=1時，BRITE所產生的拓撲在冪率指數和特征路徑長度等方面最接近Internet的實際拓撲；,4.GLP模型,GLP模型 現實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、一個可調節(jié)參數，它表明新節(jié)點或新邊更傾向于受歡迎的節(jié)點。 以概率1-p增加一個新節(jié)點和此新節(jié)點的m條新邊。系統中已存在的節(jié)點i被選中的概率(ki)由以上公式確定。,5. PFP模型,PFP模型 AS層Internet存在“富人俱樂部”現象，正反饋優(yōu)先(positive feedback preferential, PFP)模型正是在研究此現象的基礎上提出的。 PFP模型是基于新節(jié)點和內部邊兩個方面的交互增長、非線性優(yōu)先連接兩個機理構建的。 每一步除了將新節(jié)點連接到已存在的host節(jié)點上，還會將host連接到其他已存在的節(jié)點上，從而產生內部邊。當選擇所要連接的已存在的節(jié)點時，采用非線性優(yōu)先連接概

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

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

33、反映此種情況，將p設為動態(tài)改變的。 設P(N)為“增加的內部邊”與“增加的所有邊”的平均比值，即P(N)=In/(N+In)，In=L-Nm， N是節(jié)點個數，L是邊數，In是1997年11月后所增加的內部邊數?？捎上旅婀接嬎愕玫竭呍黾痈怕剩?由經驗數據，令p(0)=0.3, =1，便可以產生在一定程度上與Internet接近的拓撲結構。,7. TANG模型,TANG模型 由于BA模型不是專門針對Internet建模而提出的，將其應用于Internet拓撲結構會有很多不足： BA模型中沒有葉子節(jié)點，而Internet中葉子節(jié)點比例約有30%； BA模型的冪率指數為3，而Internet的冪率指

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

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

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

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