1.3　小世界網(wǎng)絡(luò)

Watts和Strogatz在分析了規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)后發(fā)現(xiàn):前者不存在短路徑，后者缺乏群集性;規(guī)則網(wǎng)絡(luò)是秩序的象征，隨機(jī)網(wǎng)絡(luò)是混亂的代表;但現(xiàn)實網(wǎng)絡(luò)不太可能是這兩個極端之一。1967年美國社會心理學(xué)家Milgram^[18]通過“小世界實驗”提出了“六度分離推斷”，即地球上任意兩人之間的平均距離為6，也就是說只要中間平均通過5個人，你就能聯(lián)系到地球上的任何人。隨后，一些數(shù)學(xué)家也對此進(jìn)行了嚴(yán)格的證明。于是，1998年Watts和Strogatz^[19]在《自然》雜志上發(fā)表了一篇開創(chuàng)性的論文，提出了網(wǎng)絡(luò)科學(xué)中著名的小世界網(wǎng)絡(luò)模型（WS模型），刻畫了真實網(wǎng)絡(luò)所有的大聚簇和短平均距離的特性。小世界網(wǎng)絡(luò)的基本模型是WS模型，算法描述如下。

① 一個環(huán)狀的規(guī)則網(wǎng)絡(luò)開始:網(wǎng)絡(luò)含有N個節(jié)點，每個節(jié)點向與它最臨近的K個節(jié)點連出K條邊，并滿足N≥K≥lnN≥1。

② 隨機(jī)化重連:以概率p隨機(jī)地重新連接網(wǎng)絡(luò)中的每個邊，即將邊的一個端點保持不變，而另一個端點取為網(wǎng)絡(luò)中隨機(jī)選擇的一個節(jié)點。其中規(guī)定，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每一個節(jié)點都不能有邊與自身相連。這樣就會產(chǎn)生pNK/2條長程的邊把一個節(jié)點和遠(yuǎn)處的節(jié)點聯(lián)系起來。改變p值可以實現(xiàn)從規(guī)則網(wǎng)絡(luò)（p=0）向隨機(jī)網(wǎng)絡(luò)（p=1）的轉(zhuǎn)變。當(dāng)p=0時，每個節(jié)點都有K個鄰點，完全沒有“隨機(jī)跳躍邊”，顯示一個規(guī)則網(wǎng)絡(luò)模型;而在0<p<1時，隨機(jī)重連邊的期望值是pNK（N→∞），顯示一個位于規(guī)則與隨機(jī)之間的模型;當(dāng)p=1時，所有邊都隨機(jī)重連，模型轉(zhuǎn)化為一個ER隨機(jī)網(wǎng)絡(luò)模型。

由于WS小世界模型構(gòu)造算法中的隨機(jī)化過程有可能破壞網(wǎng)絡(luò)的連通性，出現(xiàn)孤立的集團(tuán)，而且不便于理論分析。于是，Newman和Watts^[20]提出了NW小世界網(wǎng)絡(luò)模型，該模型是通過用“隨機(jī)化加邊”取代WS小世界網(wǎng)絡(luò)模型構(gòu)造中的“隨機(jī)化重連”。NW小世界模型構(gòu)造算法如下。

① 一個環(huán)狀的規(guī)則網(wǎng)絡(luò)開始:網(wǎng)絡(luò)含有N個節(jié)點，每個節(jié)點向與它最臨近的K個節(jié)點連出K條邊，并滿足N≥K≥lnN≥1。

② 隨機(jī)化加邊:以概率p在隨機(jī)選取的一對節(jié)點之間加上一條邊。其中，任意兩個不同節(jié)點之間至多只能有一條邊，并且每個節(jié)點都不能有邊與自身相連。改變p值可以實現(xiàn)從最近鄰耦合網(wǎng)絡(luò)（p=0）向全局耦合網(wǎng)絡(luò)（p=1）轉(zhuǎn)變。當(dāng)p足夠小且N足夠大時，NW小世界模型本質(zhì)上等同于WS小世界模型。