誘導(dǎo)最大小世界效應(yīng)的最佳網(wǎng)絡(luò)結(jié)構(gòu)

摘 要：在文章中，一般效率是全局效率和局部效率的平均值，一般效率被用來測量一個網(wǎng)絡(luò)的通信效率。一個小世界網(wǎng)絡(luò)的一般效率相對于一個相應(yīng)規(guī)則網(wǎng)絡(luò)的一般效率的增長率被用來定量地測量小世界效應(yīng)。我們的研究結(jié)果表明，當網(wǎng)絡(luò)的節(jié)點數(shù)增加時，小世界效應(yīng)單調(diào)增長。誘導(dǎo)最大小世界效應(yīng)的最佳連接概率大約為0.02，并且當節(jié)點數(shù)目增加時最佳平均連接概率單調(diào)遞減。因此，誘導(dǎo)最大小世界效應(yīng)的最佳網(wǎng)絡(luò)結(jié)構(gòu)是具有大量節(jié)點數(shù)（N>500），最小連接概率（≈0.02）和最小平均連接概率（<0.1）的網(wǎng)絡(luò)。

關(guān)鍵詞：通信效率；網(wǎng)絡(luò)結(jié)構(gòu)；效應(yīng)

1 模型

復(fù)雜網(wǎng)絡(luò)行為的另一種定義由Vito Latora和Massimo Marchiori[1]提出，該定義是基于一個網(wǎng)絡(luò)的效率。在全局和局部范圍內(nèi)，網(wǎng)絡(luò)的特征是通過效率來有效傳遞信息，而不是用C和L。為了定義圖G[1]的效率，Vito Latora和Massimo Marchiori假設(shè)每個節(jié)點是通過網(wǎng)絡(luò)發(fā)送信息。一個加權(quán)網(wǎng)絡(luò)是由一個加權(quán)值與連接邊相關(guān)聯(lián)。加權(quán)網(wǎng)絡(luò)需要兩個矩陣來表示：一個是連接矩陣{aij}，表明兩個節(jié)點直接是否存在一個連接邊（對于無權(quán)網(wǎng)絡(luò)，如果有一條邊直接連接節(jié)點i和j，其項aij為1，否則為0。）；另一個表示物理距離的矩陣{lij}。數(shù)值lij可能是兩個頂點之間的空間距離或者是它們可能連接的長度：即使在圖G中兩個節(jié)點i和j之間沒有連接，lij也是被已知的[1]。例如，在傳輸網(wǎng)絡(luò)中l(wèi)ij可能是兩個站點之間的地理距離，可能是在英特網(wǎng)中兩個路由器之間信息包裹交換所花的時間，或者是生物系統(tǒng)中沿著一個直接的連接的化學(xué)反應(yīng)的倒轉(zhuǎn)速率。在一個無權(quán)網(wǎng)絡(luò)的特殊情況下，lij=1，？坌i，j。兩個一般頂點i和j之間的最短路徑長度dij是從i到j(luò)的圖G中的曲線的所有可能的路徑的物理距離最小的總數(shù)和。因此，矩陣{dij}能通過矩陣{aij}和矩陣lij的信息計算出來，dij？叟lij，？坌i，j，當節(jié)點i和節(jié)點j之間有直接連接邊時等號成立。他們[1]假設(shè)每個頂點通過它的邊沿著整個網(wǎng)絡(luò)不斷的傳遞信息，在傳遞過程中兩個節(jié)點i和j之間的傳遞效率？著ij是最短路徑dij的倒數(shù)，即？著ij=1/dij，？坌i，j。基于這個定義，當圖G中的節(jié)點i和節(jié)點j之間沒有任何路徑連通時，dij=+∞，然而？著ij=0。

圖G的全局效率能夠被定義為：

（1）

而局部效率，類似于聚類系數(shù)C，能被定義為局部子圖效率的平均值：

其中Gi，如先前所定義的，是節(jié)點i鄰居節(jié)點所構(gòu)成的子圖，子圖Gi由ki個節(jié)點和最多ki（ki-1）/2條邊組成。公式（2）中的數(shù)值d'lm是在圖Gi中節(jié)點l和m之間被計算出來的最短距離。上述給出的兩個定義有個重要的屬性：全局效率和局部效率已經(jīng)被規(guī)范化，即：0？燮Eglob？燮1和0？燮Eloc？燮1。

我們試圖定量測量小世界效應(yīng)，使用一般效率Egen去測量網(wǎng)絡(luò)的效率，Egen是全局效率和局部效率的平均值，定義為：

Egen=（Eglob+Eloc）/2。為了定量測量小世界效應(yīng)，我們需要選擇基量。由于規(guī)則網(wǎng)絡(luò)的Egen是遠遠大于一個相應(yīng)的稀疏的隨機網(wǎng)絡(luò)，我們選擇規(guī)則網(wǎng)絡(luò)的Egen作為測量的基礎(chǔ)，基點表示為E0。因此，我們可以使用一般效率的增加的百分比來測量小世界效應(yīng)，它被定義為：

？酌sw=■ （3）

2 結(jié)果

我們首先構(gòu)造一個與文獻[2]中所使用的相同的無權(quán)小世界網(wǎng)絡(luò)。構(gòu)造一個有N=2000和K=60的規(guī)則網(wǎng)絡(luò)，然后通過重連概率prewire來構(gòu)造小世界網(wǎng)絡(luò)，構(gòu)造的小世界網(wǎng)絡(luò)的Egen對應(yīng)于重連概率prewire繪制的曲線如圖1所示，Egen首先增加，隨著prewire的增加達到最佳值后然后開始下降，這就是所謂的小世界效應(yīng)。另外，從圖1中我們可以發(fā)現(xiàn)，當重連概率prewire≈0.02時，Egen值達到最大值，而根據(jù)Egen的定義可知，如果要構(gòu)造一個全局效率和局部效率均較大的小世界網(wǎng)絡(luò)，Egen值可以作為參考，即Egen最大值的點，其實可以看作是Eglob和Eloc均較大的小世界網(wǎng)絡(luò)。

構(gòu)造一個有N=2000和K=60的規(guī)則網(wǎng)絡(luò)，然后通過重連概率prewire來構(gòu)造小世界網(wǎng)絡(luò)。根據(jù)等式（3），我們計算小世界效應(yīng)的定量測量值，？酌sw，對應(yīng)于重連概率prewire，并且在圖2中顯示結(jié)果。從圖2中，我們能夠很清晰的發(fā)現(xiàn)小世界效應(yīng)，？酌sw首先增加，隨著prewire的增加達到最大值后開始下降。誘導(dǎo)最大小世界效應(yīng)的最近重連概率prewire大約是0.02，而且相應(yīng)的？酌sw達到了19.2%。

對于一個小世界網(wǎng)絡(luò)，這兒有三個參數(shù)去測量這個網(wǎng)絡(luò)，節(jié)點的數(shù)量N，每個節(jié)點的平均連接邊數(shù)（K）和這個重連概率prewire。除了參數(shù)K，我們能夠用平均連接概率pave來測量網(wǎng)絡(luò)的連接，pave值近似等于K/N。對于一個固定節(jié)點數(shù)N，我們研究pave和prewire對？酌sw的影響。類似于圖2和圖3，我們也設(shè)置N=2000。對于N=2000和一個確定的pave，當重連概率prewire大約為0.02時？酌sw達到最大值。對于N=2000和prewire=0.02，？酌sw對應(yīng)于pave曲線如圖3所示。隨著pave的增加，？酌sw開始增加，當pave在最佳值0.032時？酌sw開始下降。當pave等于0.032時，？酌sw達到最佳值而且高達20%。

根據(jù)上面的研究結(jié)果，我們試著找到最優(yōu)pave和prewire去誘導(dǎo)對應(yīng)與不同節(jié)點數(shù)N的最大值？酌sw，最優(yōu)prewire的幾乎是一個常量，其值大約是0.02。與節(jié)點數(shù)N相對的最佳的pave被記錄在圖4中。隨著N的增加，最優(yōu)pave單調(diào)下降。如果N=50，最優(yōu)pave高達0.24，如果N增加到3000，最優(yōu)pave減少到0.025。隨著最優(yōu)pave和prewire，與節(jié)點數(shù)N相對的最大？酌sw被繪制在圖5中。如圖5所示，最大？酌sw隨著節(jié)點數(shù)的增加不斷的增加。當N=30，最大？酌sw等于0并沒有小世界效應(yīng)；當N=50時，最大？酌sw只有0.01，小世界效應(yīng)非常弱；對于N=100，1，000，2，000和3，000，最大？酌sw與N相對應(yīng)的值分別為0.033，0.16，0.20和0.23。

3 結(jié)束語

我們的結(jié)果顯示小世界效應(yīng)隨著節(jié)點數(shù)N的增加不斷增強。當節(jié)點數(shù)是30時，沒有小世界效應(yīng)。當節(jié)點數(shù)是3，000時，綜合效率的日益增長的比率達到0.23。誘導(dǎo)最大小世界效應(yīng)的最佳重連效率prewire幾乎一個常量0.02，而且最佳平均連接概率pave隨著節(jié)點數(shù)N的增加單調(diào)下降。當節(jié)點數(shù)N=3，000時，最佳pave只有0.025。因此，為了引起小世界效應(yīng)，節(jié)點數(shù)應(yīng)該是大的（>500），prewire應(yīng)該是小的（≈0.02），并且網(wǎng)絡(luò)應(yīng)該是稀疏的（pave<0.1）。

參考文獻

[1]V. Latora， M. Marchiori.Phys. Rev. Lett[J].2001，87：198+701.

[2]S. Milgram. The small world problem[J].Psychol Today， 1967，5：60-67.