小世界網路模型

小世界網路模型是一類具有較短的平均路徑長度又具有較高的聚類係數的網路的總稱。

基本介紹

• 中文名：小世界網路模型
• 外文名：Small World Network
• 提出：在1998年
• 構造算法：一個環狀的規則網路開始
• 總稱：一類具有較短的平均路徑長度
• 提出者：Watts和Strogatz
• 性質：網路模型

簡介

通過調節一個參數可以從規則網路向隨機網路過渡，該模型成為WS小世界模型。

由於WS小世界模型構造算法中的隨機化過程有可能破壞網路的連通性，Newman和Watts提出了NW小世界網路模型，該模型是通過用“隨機化加邊”取代WS小世界網路模型構造中的“隨機化重連”。

WS小世界模型構造算法

1、一個環狀的規則網路開始：網路含有N個結點，每個節點向與它最臨近的K個節點連出K條邊，並滿足N>>K>>ln(N)>>1。

2、隨機化重連：以機率p隨機地重新連線網路中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網路中隨機選擇的一個節點。其中規定，任意兩個不同的節點之間至多只能有一條邊，並且每一個節點都不能有邊與自身相連。這樣就會產生pNK/2條長程的邊把一個節點和遠處的結點聯繫起來。改變p值可以實現從規則網路(p=0)向隨機網路(p=1)轉變。

NW小世界模型構造算法

1、一個環狀的規則網路開始：網路含有N個結點，每個結點向與它最臨近K個結點連出K條邊，並滿足N>>K>>ln(N)>>1。

2、隨機化加邊：以機率p在隨機選取的一對節點之間加上一條邊。其中，任意兩個不同節點之間至多只能有一條邊，並且每一個節點都不能有邊與自身相連。改變p值可以實現從最臨近耦合網路(p=0)向全局耦合網路(p=1)轉變。當p足夠小和N足夠大時，NW小世界模型本質上等同於WS小世界模型。