網(wǎng)絡(luò)科學(xué)原理與應(yīng)用第三章

網(wǎng)絡(luò)科學(xué)原理與應(yīng)用第三章第一頁，共51頁。什么是網(wǎng)絡(luò)科學(xué)？美國國家研究委員會給出最簡單和最直接的定義：“基于科學(xué)方法研究的有組織的網(wǎng)絡(luò)知識?！边@種定義意味著將網(wǎng)絡(luò)科學(xué)與各種使用它的技術(shù)區(qū)別開來，例如，將底層所隱含的網(wǎng)絡(luò)科學(xué)與互聯(lián)網(wǎng)等具體技術(shù)相區(qū)別開來。第二頁，共51頁。第一章主要講了網(wǎng)絡(luò)的概念和網(wǎng)絡(luò)的三個發(fā)展階段。第二章主要講了圖的屬性和圖的分類。圖的屬性：平均路徑長度、密度、熵、介數(shù)、緊度，度序列分布等都在第三章一一介紹。圖的分類：按照結(jié)構(gòu)分類，隨機圖具有隨機結(jié)構(gòu)，k-規(guī)則圖具有純的確定性的結(jié)構(gòu)。在這兩種階段之間存在的兩種重要的圖：小世界類（大部分結(jié)構(gòu)化的，部分隨機的）圖，無標(biāo)度類（大部分隨機的，部分結(jié)構(gòu)化的）圖。每一類都有自己的屬性：隨機圖服從泊松分布，無標(biāo)度類服從冪律分布，小世界圖具有高平均聚類系數(shù)，k-規(guī)則圖具有0熵值。第三頁，共51頁。第三章規(guī)則網(wǎng)絡(luò)

3.1直徑，中心性和平均路徑長度3.2二叉樹網(wǎng)絡(luò)3.2.1二叉樹網(wǎng)絡(luò)的熵3.2.2二叉樹網(wǎng)絡(luò)的路徑長度3.2.3二叉樹網(wǎng)絡(luò)的鏈路效率3.3超環(huán)形網(wǎng)絡(luò)3.3.1超環(huán)形網(wǎng)絡(luò)的平均路徑長度3.3.2超環(huán)形網(wǎng)絡(luò)的鏈路效率3.4超立方網(wǎng)絡(luò)3.4.1超立方網(wǎng)絡(luò)的平均路徑長度3.4.2超立方網(wǎng)絡(luò)的鏈路效率第四頁，共51頁。什么是規(guī)則網(wǎng)絡(luò)規(guī)則網(wǎng)絡(luò)是一種具有規(guī)則圖結(jié)構(gòu)（鏈路的重復(fù)模式）的網(wǎng)絡(luò)。我們把一維鏈，二維正方晶格等稱為規(guī)則網(wǎng)絡(luò)。規(guī)則網(wǎng)絡(luò)是指平移對稱性晶格，任何一個格點的近鄰數(shù)目都相同。從網(wǎng)絡(luò)科學(xué)的角度來研究規(guī)則網(wǎng)絡(luò)有多鐘原因：

（1）它們可以提供與隨機網(wǎng)絡(luò)的鮮明對比---大多數(shù)規(guī)則網(wǎng)絡(luò)具有零或非常小的熵。

（2）K-規(guī)則網(wǎng)絡(luò)是小世界生成過程的基礎(chǔ)。

（3）規(guī)則網(wǎng)絡(luò)屬性在研究任意網(wǎng)絡(luò)的同步中非常重要（第九章和第十章學(xué)習(xí)同步）

第五頁，共51頁。網(wǎng)絡(luò)也顯示出鏈路的經(jīng)濟性，據(jù)此每一個節(jié)點是相對較小的跳數(shù)到其他節(jié)點可達的。規(guī)則網(wǎng)絡(luò)成為研究實際網(wǎng)絡(luò)設(shè)計的最佳選擇的原因是什么？

（1）規(guī)則網(wǎng)絡(luò)是稀疏的，連通的，

（2）并且具有相對較小的直徑，小的中心節(jié)點半徑（3）小的平均路徑長度。其中（1）表現(xiàn)的是高性能，（2）（3）體現(xiàn)低成本，兩個指標(biāo)在網(wǎng)絡(luò)優(yōu)化設(shè)計中是一對矛盾，需要折中和平衡。第六頁，共51頁。3.1直徑，中心性和平均路徑長度總的來講，許多實際網(wǎng)絡(luò)設(shè)計的目標(biāo)是將n個節(jié)點以最便宜的方式相互連接起來。當(dāng)網(wǎng)絡(luò)拓撲具有最少的鏈路或當(dāng)穿越網(wǎng)絡(luò)需要的跳數(shù)最小時就是“最便宜的”。曼哈頓街布局—南北/東西矩形網(wǎng)格—已經(jīng)被許多城市采用，以便最小化從一個節(jié)點到另一個節(jié)點所需要的時間。但是一個接到網(wǎng)格需要很多鏈路—太多以至于不可能有這么多條鏈路將所有主要城市相互連接起來，因為這樣需要更少的鏈路。城內(nèi)街道網(wǎng)格使傳輸時間最小，但是城際道路網(wǎng)絡(luò)使得將城市連接起來的鏈路（道路）數(shù)量最小。

第七頁，共51頁。鏈路效率E定義如下：其中m是G中的鏈路數(shù)。注意E的取值范圍從零（當(dāng)平均路徑長度為m時）到100%（當(dāng)平均路徑長度為0時）。在極端情況下，E=1.0，每條鏈路都對鏈路效率做出了貢獻。當(dāng)E=0，平均路徑長度等于m,這是可能最差情況下的路徑長度。鏈路效率是一種鏈路在縮短路徑長度下的效率測量。對應(yīng)網(wǎng)絡(luò)的E值越高就越有效率。第八頁，共51頁。

第九頁，共51頁。表3-1列出了多種網(wǎng)絡(luò)類型及其鏈路效率。按照鏈路效率，表3-1中將線形和環(huán)形網(wǎng)絡(luò)列在最低，而超立方，隨機和完全網(wǎng)絡(luò)列在最高。隨機網(wǎng)絡(luò)是鏈路有效的。

可擴展性。隨著網(wǎng)絡(luò)規(guī)模的增加，我們對鏈路的有效利用率是否得到提高有興趣。如果隨著網(wǎng)絡(luò)規(guī)模n接近無窮大，鏈路效率接近100%，網(wǎng)絡(luò)就是可擴展的。否則，網(wǎng)絡(luò)是不可擴展的。表3-1中哪些網(wǎng)絡(luò)是可擴展的？二叉樹，超環(huán)形，超立方和完全網(wǎng)絡(luò)顯然是可擴展的，因為隨著網(wǎng)絡(luò)規(guī)模n接近無窮大，鏈路效率接近100%。但是隨機網(wǎng)絡(luò)如何？答案要取決于鏈路數(shù)m是否隨著n一起擴展。

第十頁，共51頁。

路徑長度,直徑，半徑，中心節(jié)點,中心性。鏈路效率和網(wǎng)絡(luò)中心性是路徑長度的函數(shù)，因此我們從設(shè)計一個計算任意網(wǎng)絡(luò)的路徑長度的算法開始。一旦我們知道了網(wǎng)絡(luò)的平均路徑長度，我們就能計算直徑、中心性和鏈路效率。這里設(shè)計的路徑長度算法也可以額外得出直徑、中心性和鏈路效率。特征路徑長度的定義:對于所有從節(jié)點v開始到節(jié)點w結(jié)束，從節(jié)點v到節(jié)點w的所有(最短)直接路徑的平均。對于所有的v和w的組合，路徑長度算法必須能夠計算沿著v和w之間的直接路徑的跳數(shù)。令t為路徑的總數(shù),ri,j

為節(jié)點vi到節(jié)點wj

之間的直接路徑長度。那么所有ri,j

的平均數(shù)為第十一頁，共51頁。

其中ri,j

是路徑矩陣中的元素，t為路徑總數(shù)，n為節(jié)點數(shù)，t=n(n-1),計算路徑矩陣的元素就等于找到了所有路徑。我們通過采用直接方法避免循環(huán)邏輯—簡單的計算所有n2

節(jié)點對之間的路徑長度。理想的路徑長度算法能跟蹤整個網(wǎng)絡(luò)，同時小心避免產(chǎn)生回路和較長的替換路徑。這里建議的算法使用寬度優(yōu)先遞歸搜索，在聯(lián)通網(wǎng)絡(luò)中跟蹤從節(jié)點v到每個其他節(jié)點w之間的最短距離。任意網(wǎng)絡(luò)的寬度優(yōu)先搜索圍繞他的節(jié)點按層組織。寬度優(yōu)先訪問直接鄰居節(jié)點，然后是鄰居的鄰居等，直到達到一個已經(jīng)訪問過的節(jié)點，或到達一個沒有其他鄰居的節(jié)點，返回初始節(jié)點（回路）或到達目的地節(jié)點為止.第十二頁，共51頁。路徑長度,直徑和半徑，中心節(jié)點,中心性。直徑是網(wǎng)絡(luò)中最大的層號。節(jié)點的半徑是該節(jié)點到其他節(jié)點的最大距離。換句話講，節(jié)點v的半徑就是它到離它最遠節(jié)點的跳數(shù)。具有最小半徑的節(jié)點就是中心節(jié)點---它要比任何其他節(jié)點離所有節(jié)點都近或至少一樣近。因此，該過程也產(chǎn)生所有節(jié)點中心性的測量，并指出最中心的節(jié)點作為網(wǎng)絡(luò)的中心。中心性是一種等于網(wǎng)絡(luò)到所有節(jié)點的最小直徑的屬性。

第十三頁，共51頁。中心性定義為網(wǎng)絡(luò)中所有路徑中最大路徑長度中的最小值：Centrality(G)=minimumi{maxmumj,{length(vi,vj)}}從網(wǎng)絡(luò)中查找所有路徑時，我們也附帶計算了緊度。規(guī)則網(wǎng)絡(luò)非常均勻，對于所有節(jié)點來講緊度大致是相同的，但是也有例外，例如，線形網(wǎng)絡(luò)的端節(jié)點并不像中間結(jié)點那么近。

第十四頁，共51頁。這里將length(vi,vj)定義為連接vi,vj之間直接路徑的跳數(shù)。那么maxmumj

是這種路徑中最大的，又稱為節(jié)點的半徑。最后minimumi

是網(wǎng)絡(luò)中最大路徑長度中的最小值，又稱為網(wǎng)絡(luò)的中心。什么是最有效的規(guī)則網(wǎng)絡(luò)？

一個有效的網(wǎng)絡(luò)是稀疏的，具有小的直徑并且具有最短特稱路徑長度。

第十五頁，共51頁。3.2二叉樹網(wǎng)絡(luò)

線形圖用（n-1）條鏈路連接n個節(jié)點，但是它們的平均路徑長度為0（n）。線性網(wǎng)絡(luò)并非鏈路有效的，因為鏈路數(shù)與它的平均路徑長度中的跳數(shù)增長一樣快。二叉樹比線性網(wǎng)絡(luò)更加有效。它的平均路徑長度增長要比鏈路數(shù)的增長速度慢很多。二叉樹遞歸的定義為一個節(jié)點連接到兩個也是二叉樹的子樹。一個節(jié)點稱為根，它的度為2并且連接到兩個子數(shù)，后者同樣連接到兩個更多的子樹上，以此類推。這種遞歸結(jié)束于一組稱為葉子節(jié)點的節(jié)點上，葉子節(jié)點的度為1。所有中間節(jié)點經(jīng)過三條鏈路連接網(wǎng)絡(luò)，如圖3-2所示。因此，二叉樹包含的節(jié)點度僅可能是1，2，3。第十六頁，共51頁。

第十七頁，共51頁。平衡二叉樹包含k層，并且剛好具有n=

2k-1個節(jié)點，m=(n-1)條鏈路，對于k=1,2…。根節(jié)點位于第1層，葉子節(jié)點位于第k層。每一層對應(yīng)于從根到葉子節(jié)點的路徑上的一跳，因此平衡二叉樹的直徑為2（k-1）跳。根節(jié)點位于半徑=（k-1）的平衡二叉樹的中心。不平衡二叉樹的節(jié)點少于2k-1個。例如，在圖3-2a的平衡樹中，k=4,n=16-1=15節(jié)點，直徑=2(4-1)=6跳，m=15-1=14條鏈路。但是在圖3-2b的不平衡樹中具有較少的節(jié)點和鏈路：n=9<15,直徑=5跳，m=n-1=8條鏈路。在本章的其余部分僅研究平衡樹。

第十八頁，共51頁。3.2.1二叉樹網(wǎng)絡(luò)平衡二叉樹網(wǎng)絡(luò)是規(guī)則的，但是它的熵不為零，熵是度序列分布的函數(shù)，并且二叉樹具有不平滑的度序列分布。例如，圖3-2a中二叉樹的度序列分布為g`=[53%,7%,40%]這樣就得出熵I為：I（平衡二叉樹，k=4）=1.27比特度序列總是包含三種頻率：

p1=度為1的節(jié)點數(shù)

/n;這是葉子結(jié)點P2=度為2的節(jié)點數(shù)/n;這是根結(jié)點p3

=度為3的節(jié)點數(shù)/n;這是內(nèi)部結(jié)點第十九頁，共51頁。接近半數(shù)的節(jié)點是葉子結(jié)點，一個節(jié)點為根節(jié)點，其余節(jié)點時內(nèi)部節(jié)點：p1=（n/2）

/n=n/2n=1/2;葉子結(jié)點頻率P2=1/n；根節(jié)點頻率p3=[n-(n-2)-1]/n=(n-2)/2n;內(nèi)部節(jié)點頻率通過直接將上述值插入到熵的方程中得到熵I：平衡二叉樹網(wǎng)絡(luò)幾乎都是（但不完全是）規(guī)則網(wǎng)絡(luò)。它在根和葉子節(jié)點是不規(guī)則的。這些“不規(guī)則性”解釋了1比特的“隨機性”。不規(guī)則性隨著n的增加反而減少，該屬性在估計一般平衡二叉樹網(wǎng)絡(luò)的平均路徑長度時會很有用。第二十頁，共51頁。3.2.2二叉樹網(wǎng)絡(luò)的路徑長度網(wǎng)絡(luò)的中心是半徑為r=k-1的根節(jié)點，葉子結(jié)點位于直徑頂端節(jié)點上，直徑D=2（k-1）跳。直徑隨著網(wǎng)絡(luò)規(guī)模n呈對數(shù)增長，因為k=O(log2n)。但是平均路徑長度也是按對數(shù)增長的，如圖3-3所示。因此，二叉樹的平均路徑長度與他的直徑成正比，如下圖所示。圖3-3中畫出了平均路徑長度和（D-4）與層k之間的關(guān)系圖，n=2k-1,D=直徑=2（k-1）。對于高的k值來講，將平均路徑長度和（D-4）合并。這樣一來，平均路徑長度漸進于（D-4）：第二十一頁，共51頁。第二十二頁，共51頁。隨著二叉樹規(guī)模的增加，更多的葉子節(jié)點的影響遠遠超過接近根的極少數(shù)節(jié)點。葉子結(jié)點以及其鄰居占主導(dǎo)地位，以至于相對較少的接近根的節(jié)點的影響減少到零。事實上，接近四分之一的節(jié)點離網(wǎng)絡(luò)中一半以上的節(jié)點的距離為1跳。詳細的講，所在層（k-2）的節(jié)點連接到約八分之一其“上層”的節(jié)點，連接到約二分之一其“下層”的節(jié)點。顯然，葉子節(jié)點和它們的直接鄰居的影響主導(dǎo)著大的二叉樹網(wǎng)絡(luò)的平均路徑長度。因此隨著n的增加，平均路徑長度漸進于（D-4）跳。漸進于（D-4）如圖3-3中的點畫線所示，對于大的k值來講，接近于平均路徑長度。第二十三頁，共51頁。顯然，隨著網(wǎng)絡(luò)規(guī)模的提高，近似程度得到了提高。

對于較小的k（k<9）值來講，近似不成立。相反，我們使用如圖3-3所示的近似。隨著k值的增加，近似的非線性部分呈指數(shù)減少---當(dāng)（D-4）占主導(dǎo)時達到零：這里A=10.67，B=0.45給出對數(shù)據(jù)的最佳擬合。D=2（k-1）,k=log2(n+1),代入其他數(shù)據(jù)，我們就得到圖3-3中將這種近似顯示成經(jīng)過avg_path_length實際值的實線。對于所有k>1值，具有相當(dāng)?shù)木取＠?，?dāng)k=1時，實際路徑長度為零，近似路徑長度為0.15；當(dāng)k=4時，實際值和近似值兩者相同，為3.15；當(dāng)k=12,實際值為18.02.近似值為18.05。第二十四頁，共51頁。3.2.3二叉樹網(wǎng)絡(luò)的鏈路效率既然我們知道平衡二叉樹的平均路徑長度方程，我們可以將它插入到鏈路效率的方程中并加以簡化。平衡二叉樹具有m=n-1條鏈路?！按蟮摹逼胶舛鏄涞逆溌沸÷房梢院喕桑杭俣╪>>1,因此（n+1）和（n-1）都近似于n,鏈路效率近似為第二十五頁，共51頁。例如，如果n=127,那么近似的E=0.890，但是實際的鏈路效率為0.934.但是如果n=2047，近似公式得出E=0.990,實際的鏈路效率為0.992，實際和近似效率僅有0.2%的差異。對于大的n,這種差異幾乎不存在。隨著n無限的增長，二叉樹的鏈路效率接近100%。因此，平衡二叉樹用于構(gòu)造多處理器的互連或公司的組織圖會顯得非常有效率。在這兩個應(yīng)用中，每條鏈路需要更短的平均路徑長度。平衡二叉樹能以最佳效率利用鏈路嗎？在3.3節(jié)中，我們將探索該問題并說明甚至還有比平衡樹網(wǎng)絡(luò)更有效的網(wǎng)絡(luò)。第二十六頁，共51頁。3.3超環(huán)形網(wǎng)絡(luò)對于二叉樹，為了從一個葉子節(jié)點到達另外一個葉子節(jié)點，信息必須沿著樹到達它的根，然后再向下到達目的地。兩個葉子結(jié)點越遠，路徑就越有可能通過樹根。或許通過二叉樹同一層節(jié)點之間插入橫向鏈路，可以減少平均路徑長度。這些捷徑將不需要遍歷所有的路徑到根節(jié)點，而是簡單的從屬的一側(cè)到達另外一側(cè)。但是，增加鏈路會降低鏈路效率。因此，在不增加更多的鏈路是如何縮短路徑？一種設(shè)計在網(wǎng)格狀的拓撲中將一般鏈路分給水平連接，另外一半分給垂直連接。換句話來講，假設(shè)映射函數(shù)連接直接前驅(qū)和后繼結(jié)點，另外一個映射連接節(jié)點v到另外一個距離為+n1/2和-n1/2

跳的節(jié)點。第二十七頁，共51頁。圖3-4所示的網(wǎng)絡(luò)是一個n1/2*n1/2

的網(wǎng)狀，并附加了一個條件：邊沿節(jié)點“圍繞”到相對的邊沿節(jié)點，因此每一行和列構(gòu)成一個環(huán)形。

當(dāng)像這樣環(huán)繞起來時，環(huán)的集合就構(gòu)成一個超環(huán)形網(wǎng)絡(luò)，這種網(wǎng)絡(luò)故此得名。典型的超環(huán)形網(wǎng)絡(luò)具有n=k2

個節(jié)點，以k*k網(wǎng)格布局。每個節(jié)點的度為4，因此有m=2n=2

k2

條鏈路，圖3-4顯示了一個4*4網(wǎng)格，具有n=16個節(jié)點和m=32條鏈路?？偟膩碇v，超環(huán)形網(wǎng)絡(luò)的規(guī)模等于整數(shù)的平方（n=4,9,16,25,36…）,鏈路數(shù)是整數(shù)平方的兩倍。圖3-4的超環(huán)形網(wǎng)絡(luò)是完全非隨機的，因為它的熵為零。這是由于實際上所有節(jié)點具有相同的度，他也缺乏聚類。第二十八頁，共51頁。

圖3-4顯示了一個n=16，m=32的超環(huán)形網(wǎng)絡(luò)

第二十九頁，共51頁。3.3.1超環(huán)形網(wǎng)絡(luò)的平均路徑長度下面我們演示超環(huán)形網(wǎng)絡(luò)的平均路徑長度會隨著網(wǎng)絡(luò)規(guī)模n按照O(n1/2)增加。這比二叉樹網(wǎng)絡(luò)的路徑長度要小，從而導(dǎo)致更好的鏈路效率。例如，4*4超環(huán)形網(wǎng)絡(luò)的平均路徑長度為2.133跳，而n=15個節(jié)點的二叉樹具有3.5跳。任意k*k超環(huán)形網(wǎng)絡(luò)的平均路徑長度是多少？為了回答該問題，考慮表3-2.第三十頁，共51頁。表3-2是通過枚舉規(guī)模為n=4,9,16,…的超環(huán)形網(wǎng)絡(luò)的路徑長度從路徑矩陣構(gòu)造的。這些是完全平方數(shù)，因此n1/2=2,3,4,…。平均路徑長度等于路徑矩陣的所有n(n-1)個元素的平均，但是路徑矩陣的所有行的和都等于同一數(shù)，因此很容易計算所有行的平均值。圖3-2的第3列包含每個超環(huán)形規(guī)模的行總和，第四列也是行總和，但是以因數(shù)分解形式表示。例如，一個4*4超環(huán)形路徑矩陣的行之和等于32，他的因素分級為4（8）。第四列可以被分解成(ns)1/2,這里當(dāng)n為奇數(shù)時，s為（n-1）/2;當(dāng)n為偶數(shù)時，s為n/2。對于n=16，s=16/2=8,因為n為偶數(shù)。對于n=25,s=(25-1)/2=12,因為n為奇數(shù)。第三十一頁，共51頁。這樣一來，行總和（表3-2中第4列）的因數(shù)分級額的一般形式為：接下來，觀察表3-2的最后一列，包含以分?jǐn)?shù)形式a/b表示的平均路徑長度。其中分子a=行總和，分母b=(n-1)。例如，當(dāng)n=16時，分子a=32，分母b=(16-1)=15。因此，4*4超環(huán)形網(wǎng)絡(luò)的平均路徑長度等于32/15=2.13。通過推導(dǎo)，平均路徑長度的公式為：第三十二頁，共51頁。我們可以驗證該公式適用于任何規(guī)模的超環(huán)形網(wǎng)絡(luò)。奇數(shù)規(guī)模的超環(huán)形網(wǎng)絡(luò)稍微緊湊一些，但是偶數(shù)和奇數(shù)網(wǎng)絡(luò)的平均路徑長度都是按照O(n1/2

)增長的，這種近似隨著n的增加快速得到改進。第三十三頁，共51頁。3.3.2超環(huán)形網(wǎng)絡(luò)的鏈路效率之前學(xué)習(xí)過鏈路效率的公式如下：

超環(huán)形網(wǎng)絡(luò)鏈路數(shù)m=2n,n=k2

帶入鏈路效率公式得：

E（G）=[m-n1/2/2]/m=1-n1/2/2n=1-n1/2/4n

=1-1/4n1/2

將n=16的超環(huán)形網(wǎng)絡(luò)與n=15的二叉樹網(wǎng)絡(luò)的鏈路效率進行比較，得出E（toroid）=1-1/16=93.8%,E(binarytree)=1-(8-6)/14=85.7%.第三十四頁，共51頁。小結(jié)：

對于較小的n來講，百分比之差下降了。例如，隨著n=100時，超環(huán)形網(wǎng)絡(luò)的鏈路效率是97.5%，二叉樹鏈路效率接近于92.6%，只有5%的差距。但是，超環(huán)形需要二叉樹兩倍的鏈路。第三十五頁，共51頁。3.4超立方網(wǎng)絡(luò)超立方網(wǎng)絡(luò)是以節(jié)點間相距只有一個海明距離的方式連接節(jié)點。兩個二進制數(shù)x和y之間的海明距離h(x,y)定義成x中的比特與y中對應(yīng)比特不同的個數(shù)。因此，僅對于h(x,y)=1的節(jié)點，超立方通過將節(jié)點vx

和

vy

連接起來而形成。

第三十六頁，共51頁。表3-3列出了整數(shù)0~7（列）的二進制表示和整數(shù)0~4（行）的二進制表示之間的海明距離。例如，整數(shù)2的二進制表示為010，4的二進制表示為100，它們的比特位中有兩個二進制位數(shù)不同，因此海明距離為2。海明距離還可以通過將由XOR(異或)操作符產(chǎn)生的比特加起來計算。當(dāng)輸入比特不同時XOR產(chǎn)生“1”比特，當(dāng)輸入相同時XOR產(chǎn)生“0”比特：

XOR（010，100）=110

SUM（110）=2第三十七頁，共51頁。為了構(gòu)建一個超立方簡單的將相鄰節(jié)點對vx和

vy

連接起來，如果h(x,y)=1,就在vx和

vy

之間畫一條鏈路。假設(shè)n=4,那么節(jié)點索引范圍為0~3，以二進制表示為00，01，10和11.我們使用相差一比特位的二進制索引將所有節(jié)點對連接起來。在這種情況下，h(00,01)=1,h(00,10)=1,h(01,10)=2,h(01,11)=1,h(10,11)=1,因此我們將等于1的節(jié)點對連接起來如下：第三十八頁，共51頁。超立方的維數(shù)等于每一個節(jié)點的度，D（H）=log2（n）,這里n=2D

。二維超立方的所有節(jié)點具有度2，三維超立方的所有節(jié)點具有度3，以此類推。超立方的直徑也等于節(jié)點的度。超立方的維數(shù)=直徑=節(jié)點的度超立方網(wǎng)絡(luò)中包含超立方網(wǎng)絡(luò)，維數(shù)為D的超立方包含兩個維數(shù)為D/2的超立方，如圖3-5所示。從D=1的超立方開始，圖3-5a的一維杠鈴很容易從兩個節(jié)點構(gòu)造—一個序號為0，另一個序號為1.D=2的超立方如圖3-5b所示，通過用兩條新的鏈路將兩個杠鈴超立方結(jié)合起來構(gòu)造。第三十九頁，共51頁。第四十頁，共51頁。更高維數(shù)超立方的二進制節(jié)點索引是通過在一個杠鈴的節(jié)點索引添加二進制0，在另外一個杠鈴的節(jié)點索引添加二進制1獲得的。在3-5b中，節(jié)點索引00，01是通過在索引號為0和1的節(jié)點添加前綴“1”獲得的。一般來講，更高維數(shù)的超立方的建立方法是通過復(fù)制兩個（D-1）維超立方，在一個副本的節(jié)點索引前加前綴二進制0，另一個副本的幾點索引前加前綴二進制1，并在索引僅差一個海明距離的節(jié)點添加鏈路。第四十一頁，共51頁。超立方的每一個節(jié)點連接到D=log2（n）的其他節(jié)點上，每條連接只有一個海明距離。例如，當(dāng)n=4時，那么log2（4）=2，因此節(jié)點00連接到節(jié)點01和10.這兩個鄰接節(jié)點距離00節(jié)點僅有一個海明距離。鄰接節(jié)點索引是通過翻轉(zhuǎn)00的每一位比特計算的，每次一位，這樣節(jié)點索引為01和10.相似的，對于n=8,D=log2（8）=3,在000和100，010，001之間插入了三條鏈路。通過翻轉(zhuǎn)000的第1，2，3，比特位，一次一位，相鄰節(jié)點索引為100，010，001。第四十二頁，共51頁。超立方的生成過程：超立方生成過程簡單，對于超立方中的每一個節(jié)點vi，在vi和所有其他節(jié)點之間插入鏈路，節(jié)點索引時從i的每一比特翻轉(zhuǎn)獲取的，每次一位，從左到右直到所有的log2（n）比特翻轉(zhuǎn)完成為止。第四十三頁，共51頁。3.4.1超立方網(wǎng)絡(luò)的平均路徑長度回顧一下，任何網(wǎng)絡(luò)的鏈路數(shù)目等于節(jié)點度總和的一半：2m=d1+d2+…+dn。超立方網(wǎng)絡(luò)的每個節(jié)點具有相同的度，D=log2(n).這樣一來，m=nlog2(n)/2,這里n>1。在圖3-5d的4D超立方中m=16(4/2)=32條鏈路。在5D超立方中m=32（4/2）=64條鏈路，因此，鏈路數(shù)隨著超立方規(guī)模而擴展。超立方中的每一個節(jié)點都可以以1，2，…,D=log2(n)跳從任何一個其他節(jié)點到達