小世界網絡

在數學、物理學和社會學中，小世界網絡是一種數學之圖的類型，在這種圖中大部分的結點不與彼此鄰接，但大部分結點可以從任一其他點經少數幾步就可到達。若將一個小世界網絡中的點代表一個人，而連結線代表人與人認識，則這小世界網絡可以反映陌生人由彼此共同認識的人而連結的小世界現象。

自相似指的是這樣一種性質，系統在不同尺度上看起來性質相同。小世界網絡的定義就沒有這麼明確，只説它是規則和隨機網絡的中間物。這種不明確性可能來源於對它瞭解的缺乏。

在考慮網絡特徵的時候，使用兩個特徵來衡量網絡：

特徵路徑長度（characteristic path length）：在網絡中，任選兩個節點，連通這兩個節點的最少邊數，定義為這兩個節點的路徑長度，網絡中所有節點對的路徑長度的平均值，定義為網絡的特徵路徑長度。這是網絡的全局特徵。

聚合係數(clustering coefficient)：假設某個節點有k條邊，則這k條邊連接的節點（k個）之間最多可能存在的邊的條數為k(k-1)/2，用實際存在的邊數除以最多可能存在的邊數得到的分數值，定義為這個節點的聚合係數。所有節點的聚合係數的均值定義為網絡的聚合係數。聚合係數是網絡的局部特徵，反映了相鄰兩個人之間朋友圈子的重合度，即該節點的朋友之間也是朋友的程度。

對於規則網絡，任意兩個點（個體）之間的特徵路徑長度長（通過多少個體聯繫在一起），但聚合係數高（你是朋友的朋友的朋友的幾率高）。對於隨機網絡，任意兩個點之間的特徵路徑長度短，但聚合係數低。而小世界網絡，點之間特徵路徑長度小，接近隨機網絡，而聚合係數依舊相當高，接近規則網絡。

發現規則網絡具有很高的聚合係數，大世界（large world，意思是特徵路徑長度很大），其特徵路徑長度隨着n(網絡中節點的數量)線性增長，而隨機網絡聚合係數很小，小世界（small world，意思是特徵路徑長度小），其特徵路徑長度隨着log(n)增長中説明，在從規則網絡向隨機網絡轉換的過程中，實際上特徵路徑長度和聚合係數都會下降，到變成隨機網絡的時候，減少到最少。但這並不是説大的聚合係數一定伴隨着大的路徑長度，而小的路徑長度伴隨着小的聚合係數，小世界網絡就具有大的聚合係數，而特徵路徑長度很小。試驗表明，少量的short cut的建立能夠迅速減少特徵路徑長度，而聚合係數變化卻不大，因為某一個short cut的建立，不僅影響到所連接的節點的特徵路徑長度，而且影響到他們鄰居的路徑長度，而對整個網絡的聚合係數影響不大。這樣，少量的short cut的建立就能使整個網絡不知不覺地變成小世界網絡。

實際的社會、生態、等網絡都是小世界網絡，在這樣的系統裏，信息傳遞速度快，並且少量改變幾個連接，就可以劇烈地改變網絡的性能，如對已存在的網絡進行調整，如蜂窩電話網，改動很少幾條線路，就可以顯著提高性能。