誘導最大小世界效應的最佳網絡結構

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

關鍵詞：通信效率；網絡結構；效應

1 模型

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

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

（1）

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

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

我們試圖定量測量小世界效應，使用一般效率Egen去測量網絡的效率，Egen是全局效率和局部效率的平均值，定義為：

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

？酌sw=■ （3）

2 結果

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

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

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

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

3 結束語

我們的結果顯示小世界效應隨著節點數N的增加不斷增強。當節點數是30時，沒有小世界效應。當節點數是3，000時，綜合效率的日益增長的比率達到0.23。誘導最大小世界效應的最佳重連效率prewire幾乎一個常量0.02，而且最佳平均連接概率pave隨著節點數N的增加單調下降。當節點數N=3，000時，最佳pave只有0.025。因此，為了引起小世界效應，節點數應該是大的（>500），prewire應該是小的（≈0.02），并且網絡應該是稀疏的（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.