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

摘 要：在文章中，一般效率是全局效率和局部效率的平均值，一般效率被用來(lái)測(cè)量一個(gè)網(wǎng)絡(luò)的通信效率。一個(gè)小世界網(wǎng)絡(luò)的一般效率相對(duì)于一個(gè)相應(yīng)規(guī)則網(wǎng)絡(luò)的一般效率的增長(zhǎng)率被用來(lái)定量地測(cè)量小世界效應(yīng)。我們的研究結(jié)果表明，當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)增加時(shí)，小世界效應(yīng)單調(diào)增長(zhǎng)。誘導(dǎo)最大小世界效應(yīng)的最佳連接概率大約為0.02，并且當(dāng)節(jié)點(diǎn)數(shù)目增加時(shí)最佳平均連接概率單調(diào)遞減。因此，誘導(dǎo)最大小世界效應(yīng)的最佳網(wǎng)絡(luò)結(jié)構(gòu)是具有大量節(jié)點(diǎn)數(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]提出，該定義是基于一個(gè)網(wǎng)絡(luò)的效率。在全局和局部范圍內(nèi)，網(wǎng)絡(luò)的特征是通過(guò)效率來(lái)有效傳遞信息，而不是用C和L。為了定義圖G[1]的效率，Vito Latora和Massimo Marchiori假設(shè)每個(gè)節(jié)點(diǎn)是通過(guò)網(wǎng)絡(luò)發(fā)送信息。一個(gè)加權(quán)網(wǎng)絡(luò)是由一個(gè)加權(quán)值與連接邊相關(guān)聯(lián)。加權(quán)網(wǎng)絡(luò)需要兩個(gè)矩陣來(lái)表示：一個(gè)是連接矩陣{aij}，表明兩個(gè)節(jié)點(diǎn)直接是否存在一個(gè)連接邊（對(duì)于無(wú)權(quán)網(wǎng)絡(luò)，如果有一條邊直接連接節(jié)點(diǎn)i和j，其項(xiàng)aij為1，否則為0。）；另一個(gè)表示物理距離的矩陣{lij}。數(shù)值lij可能是兩個(gè)頂點(diǎn)之間的空間距離或者是它們可能連接的長(zhǎng)度：即使在圖G中兩個(gè)節(jié)點(diǎn)i和j之間沒有連接，lij也是被已知的[1]。例如，在傳輸網(wǎng)絡(luò)中l(wèi)ij可能是兩個(gè)站點(diǎn)之間的地理距離，可能是在英特網(wǎng)中兩個(gè)路由器之間信息包裹交換所花的時(shí)間，或者是生物系統(tǒng)中沿著一個(gè)直接的連接的化學(xué)反應(yīng)的倒轉(zhuǎn)速率。在一個(gè)無(wú)權(quán)網(wǎng)絡(luò)的特殊情況下，lij=1，？坌i，j。兩個(gè)一般頂點(diǎn)i和j之間的最短路徑長(zhǎng)度dij是從i到j(luò)的圖G中的曲線的所有可能的路徑的物理距離最小的總數(shù)和。因此，矩陣{dij}能通過(guò)矩陣{aij}和矩陣lij的信息計(jì)算出來(lái)，dij？叟lij，？坌i，j，當(dāng)節(jié)點(diǎn)i和節(jié)點(diǎn)j之間有直接連接邊時(shí)等號(hào)成立。他們[1]假設(shè)每個(gè)頂點(diǎn)通過(guò)它的邊沿著整個(gè)網(wǎng)絡(luò)不斷的傳遞信息，在傳遞過(guò)程中兩個(gè)節(jié)點(diǎn)i和j之間的傳遞效率？著ij是最短路徑dij的倒數(shù)，即？著ij=1/dij，？坌i，j?；谶@個(gè)定義，當(dāng)圖G中的節(jié)點(diǎn)i和節(jié)點(diǎn)j之間沒有任何路徑連通時(shí)，dij=+∞，然而？著ij=0。

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

（1）

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

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

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

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

？酌sw=■ （3）

2 結(jié)果

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

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

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

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

3 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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.