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

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

（1）它們可以提供與隨機(jī)網(wǎng)絡(luò)的鮮明對(duì)比---大多數(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ì)性，據(jù)此每一個(gè)節(jié)點(diǎn)是相對(duì)較小的跳數(shù)到其他節(jié)點(diǎn)可達(dá)的。規(guī)則網(wǎng)絡(luò)成為研究實(shí)際網(wǎng)絡(luò)設(shè)計(jì)的最佳選擇的原因是什么？

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

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

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

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

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

第十頁，共51頁。

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

為節(jié)點(diǎn)vi到節(jié)點(diǎn)wj

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

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

其中ri,j

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

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

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

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

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

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

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

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

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

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

2k-1個(gè)節(jié)點(diǎn)，m=(n-1)條鏈路，對(duì)于k=1,2…。根節(jié)點(diǎn)位于第1層，葉子節(jié)點(diǎn)位于第k層。每一層對(duì)應(yīng)于從根到葉子節(jié)點(diǎn)的路徑上的一跳，因此平衡二叉樹的直徑為2（k-1）跳。根節(jié)點(diǎn)位于半徑=（k-1）的平衡二叉樹的中心。不平衡二叉樹的節(jié)點(diǎn)少于2k-1個(gè)。例如，在圖3-2a的平衡樹中，k=4,n=16-1=15節(jié)點(diǎn)，直徑=2(4-1)=6跳，m=15-1=14條鏈路。但是在圖3-2b的不平衡樹中具有較少的節(jié)點(diǎn)和鏈路：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é)點(diǎn)數(shù)

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

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

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

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

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

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

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

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

k2

條鏈路，圖3-4顯示了一個(gè)4*4網(wǎng)格，具有n=16個(gè)節(jié)點(diǎn)和m=32條鏈路。總的來講，超環(huán)形網(wǎng)絡(luò)的規(guī)模等于整數(shù)的平方（n=4,9,16,25,36…）,鏈路數(shù)是整數(shù)平方的兩倍。圖3-4的超環(huán)形網(wǎng)絡(luò)是完全非隨機(jī)的，因?yàn)樗撵貫榱?。這是由于實(shí)際上所有節(jié)點(diǎn)具有相同的度，他也缺乏聚類。第二十八頁，共51頁。

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

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

)增長的，這種近似隨著n的增加快速得到改進(jì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ò)的鏈路效率進(jìn)行比較，得出E（toroid）=1-1/16=93.8%,E(binarytree)=1-(8-6)/14=85.7%.第三十四頁，共51頁。小結(jié)：

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

和

vy

連接起來而形成。

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

XOR（010，100）=110

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

vy

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

vy

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

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