交通地理學與網路科學/小世界網路

圖.1 小世界網路影像 [作者：使用者：Sazaedo]

簡介

很久以前，由於多種因素（如地形、缺乏交通選擇、缺乏工具和缺乏教育），人們的活動範圍有限。人員、商品和思想的流動通常依靠人力和畜力。因此，山脈、河流和海洋是流動性的重大障礙。除了這些物理障礙之外，不同國家的人民由於語言障礙而無法輕鬆溝通。因此，將物品和思想從源頭移動到目的地需要很長時間。然而，自那些日子以來，技術已經有了很大的發展。由於發達的交通網路和交通方式（如汽車、飛機），我們可以輕鬆快捷地移動更長的距離。此外，由於教育的改善和少數標準化語言的傳播，我們與外國人的溝通能力也有所提高。此外，我們可以透過電信和計算機網路幾乎即時傳遞資訊。世界正在變小。

我們生活在一個網路世界中，許多事物相互連線，這種連線使我們的生活方式更加有效。鄧肯和斯特羅加茨指出，現實世界的網路既不是規則網路也不是隨機網路，它們存在於規則網路和隨機網路之間。他們稱這種型別的網路為“小世界網路”。

歷史^[3]

• 1929 年：匈牙利作家弗裡吉斯·卡林西首次報道了小世界現象。他在他的書《一切都不同》中討論了小世界屬性的主題。

• 1967 年：斯坦利·米爾格拉姆進行了第一個關於小世界現象的實驗研究。在這個實驗中，他分析了當信件在兩個陌生人之間傳遞時的平均分離程度。

• 1991 年：約翰·瓜爾寫了一部戲劇《六度分離》，“六度分離”一詞在世界上流行起來。

• 1998 年：鄧肯·瓦茨和史蒂文·斯特羅加茨透過分析演員網路、神經網路和電力網網路對“小世界網路”進行了數學分析。他們說明了小世界屬性出現在自然和技術網路以及社會網路中。

六度分離

圖.2 六度分離影像 [作者：勞倫斯·範·利斯霍特]

世界上任何兩個人都在 6 度內相連，即使他們彼此不認識。這意味著每個人都可以透過朋友的網路在 6 度內與名人（如麥當娜、達賴喇嘛和女王）聯絡起來。 這個想法最初由弗裡吉斯·卡林西在 1929 年提出，但在 1969 年進行實驗之前被認為是民間傳說。1969 年，研究人員斯坦利·米爾格拉姆進行了一項關於“六度分離”想法的第一個實驗研究。研究人員要求堪薩斯州威奇托、奧馬哈和內布拉斯加州的居民寄一封信，信的目的地是波士頓的股票經紀人或馬薩諸塞州的學生。當居民不認識目標人物時，他們必須將信寄給他們的朋友或熟人，而不是目標人物。雖然並非所有信件都送達目標人物，但平均度數為 5.5。 這個結果表明卡林西的想法幾乎是正確的。之後，這種現象因約翰·瓜爾的戲劇《六度分離》，以及客廳遊戲“六度分離凱文·貝肯” 廣為流行。在米爾格拉姆的實驗之後，幾位研究人員透過改變網路型別來檢驗“六度分離”的假設。雖然米爾格拉姆的實驗僅限於美國，但今天的實驗分析的是全球網路。

2008 年，微軟研究人員分析了微軟 Messenger 的 300 億條記錄，他們發現平均分離度為 6.6。這意味著 78% 的兩個人在 7 度內聯絡，而有些兩對人之間相隔 29 度。 2011 年，Facebook 科學家 Lars Backstrom 和米蘭大學的研究人員分析了 7.21 億 Facebook 使用者，約佔全球人口的 10%。結果顯示，平均分離度為 3.74，99.6% 的兩個使用者在 5 度分離內聯絡在一起。 這個結果表明 Facebook 的網路比微軟 Messenger 的網路顯示更小的世界。然而，兩個人之間的網路連線程度是不同的，因為微軟的研究是基於交換資訊；另一方面，Facebook 的研究是基於“朋友”功能。

表 1 顯示了平均分離度 [d] 的其他結果。在十個網路中，大腸桿菌代謝網路的平均分離度最小，為 2.98。相反，電力網路的平均分離度最大，為 18.99。 這意味著在電力網路中，任何兩個節點之間的距離不超過 19 個節點。這個數字遠大於社交網路中的平均分離度。根據這個結果，網路結構因網路型別而異。根據 Barabashi 的研究，如果知道網路的總節點數 [N] 和平均出度（協調數）[k]，就可以計算出任何網路的平均距離（平均分離度）[d]。平均距離大約為 $d\propto \log N/logk$，這個公式表明，網路越稠密，平均距離越小。表 1 顯示了該公式的結果，在某些情況下（例如，網際網路、行動電話通話），估計值 [log N / log k] 與平均距離 [d] 相似；然而，它並不完美（例如，全球資訊網、電力網路和電子郵件）。例如，在網際網路中，平均距離 [d] 為 6.98，而 log N / log k 的估計值為 6.59。另一方面，在電子郵件中，平均距離為 5.88，而 log N / log k 的估計值為 18.4。

表 1 平均分離度列表 [Barabashi]

網路名稱	$N$	$L$	$<k>$	$<d>$	$d_{max}$	${\dfrac {logN}{log<k>}}$
網際網路	192,244	609,066	6.34	6.98	26	6.59
全球資訊網	325,729	1,497,134	4.60	11.27	93	8.32
電力網路	4,941	6,594	2.67	18.99	46	8.66
行動電話通話	36,595	91,826	2.51	11.72	39	11.42
電子郵件	57,194	103,731	1.81	5.88	18	18.4
科學合作網路	23,133	186,936	8.08	5.35	15	4.81
演員網路	212,250	3,054,278	28.78	-	-	-
引用網路	449,673	4,707,958	10.47	11.21	42	5.55
大腸桿菌代謝網路	1,039	5,802	5.84	2.98	8	4.04
酵母蛋白相互作用網路	2,018	2,930	2.90	5.61	14	7.14

Barabashi 指出，總節點數 [N] 和平均距離 [d] 之間的關係因空間維度而異。Barabashi 的 圖 3.10 展示了透過改變維度，它們之間的關係，結果表明，規則網路的平均距離遠大於隨機網路的平均距離。這是實際平均距離 [d] 與估計值 [log N / log k] 之間存在差異的原因之一。此外，Barabashi 指出，平均距離 [d] 在不同規模的網路中有所不同。Barabashi 的 圖 3.11 顯示了 Facebook 使用者在全球使用者和美國使用者之間的距離分佈，結果表明，美國使用者之間的平均距離小於全球使用者之間的平均距離。

小世界網路： “Duncan Watts 模型”

規則網路和隨機網路的網路結構存在顯著差異。Watts 和 Strogatz 指出，現實世界中的網路結構既不是隨機網路的結構，也不是規則網路的結構。因此，他們指出，現實世界中的網路介於這兩種網路之間，他們稱這種型別的網路為“小世界網路”。圖 1 顯示了環形格子上小世界網路的影像。一個網路有 $N$ 個節點，每個節點連線到 $k$ 個節點，每個節點根據機率 [p] 從最近的節點隨機重新連線到另一個節點。在“規則網路”中，機率為零 [p = 0]，所有節點都連線到最近的鄰居。隨著機率的增加 [0< p < 1]，一些連線以機率 $p$ 隨機重新連線到另一個節點，我們將這種連線稱為“捷徑”。當所有連線都被隨機重新連線時 [p=1]，這個網路被稱為“隨機網路”。

路徑長度 [L] 和聚類係數 [C]

為了解釋網路結構特徵，Watts 和 Strogatz 使用了兩個因素：路徑長度 [L] 和聚類係數 [C]。 如果每個人都連線到每個人，則 C = 1。

在規則網路中，路徑長度 [L] 為 $L\sim N/2k$，聚類係數 [C] 為 $C\sim 3/4$。另一方面，在隨機網路中，路徑長度 [L] 為 $L\sim ln(N)/ln(k)$，聚類係數 [C] 為 $C\sim k/N$。因此，規則網路具有高度的聚類性，但路徑長度較長。另一方面，隨機網路聚類性較差，路徑長度較短。 存在一些方程式可以解釋聚類係數 [C] 和路徑長度 [L]。根據 Newman 的說法，聚類係數 [C] 可以透過 $C=3(k-2)/4(k-1)$ 來估計。此外，在考慮維度 [m] 時，聚類係數 [C] 可以透過 $C=3(k-2m)/4(k-m)$ 來估計。

Barrat 和 Weigt 提出了考慮機率 p 的聚類係數 [C] 和路徑長度 [L] 的公式。路徑長度 [L] 會根據 n 和 p 的變化而顯著改變。

$C={\dfrac {3(k-2)}{4(k-1)}}(1-p)^{3}$

$L(n,p)={\dfrac {1}{N(N-1)}}\sum _{i\neq j}d_{ij}$

$d_{ij}$ 是節點 i 和 j 之間的化學距離。

關於連線度分佈，規則網路中每個節點都具有相同的連線度 [k]；然而，隨著機率 $p$ 的增加，連線度分佈變得不均勻，分佈變得更廣，而平均連線度為 $k$。

小世界效應

“小世界效應”意味著平均距離 [d] 隨著節點總數 [N] 的增加而對數增長。這與規則網路中平均距離 [d] 隨節點總數 [N] 線性增加的結構不同。另一方面，這與隨機網路類似。但是，小世界網路與隨機網路並不相同，因為它們表現出聚類性。 小世界網路兼具規則網路和隨機網路的特徵，因為它們像規則網路一樣具有高度的聚類性，並且像隨機網路一樣具有較小的路徑長度。

網路結構特徵 [L 和 C] 與機率 [p] 之間的關係

圖 5 網路結構特徵 [L 和 C] 與機率 [p] 之間的關係 [衍生作品：圖片來自 Watts 和 Strogatz]

圖 5 顯示了網路結構特徵 [L 和 C] 與機率 [p] 之間的關係。當 $p$ 很小時，路徑長度 [L] 的值迅速下降，而聚類係數 [C] 幾乎保持不變。另一方面，當 $p$ 很大時，路徑長度 [L] 幾乎保持不變，而聚類係數 [C] 大幅下降。 小世界範圍是指 $C$ 的值遠大於隨機網路的值，但 $L$ 的值接近隨機網路的值。

Watts 和 Strogatz 分析了三種不同的網路，以檢驗小世界網路的概念；“電影演員”、“電力網”和“神經網路 (秀麗隱杆線蟲)”。在電影演員方面，頂點是演員，當兩位演員在同一電影中合作時，就會建立邊。在電力網方面，頂點是發電機、變壓器和變電站，邊是輸電線路。在秀麗隱杆線蟲方面，頂點是神經元，邊是突觸或間隙連線連線的連結。

Watts 和 Strogatz 展示了路徑長度 [L] 和聚類係數 [C] 的實際值和隨機值（表 2）。他們發現，路徑長度 [L] 的實際值與隨機網路中的值相似，但聚類係數 [C] 的實際值明顯大於隨機網路中的值。因此，這三種網路都顯示出小世界網路的特徵。此外，他們還調查了傳染病的傳播時間，發現傳染病在小世界網路中傳播速度更快，因為網路中存在捷徑。此外，傳染病傳播時間呈現出與路徑長度 [L] 相似的曲線圖。 所有這些實證研究表明，現實世界網路與小世界網路具有相似性。

表 2 小世界網路的實證例子 [Watts 和 Strogatz]

	$L_{actual}$	$L_{random}$	$C_{actual}$	$C_{random}$
電影演員	3.65	2.99	0.79	0.00027
電力網	18.7	12.4	0.080	0.005
秀麗隱杆線蟲	2.65	2.25	0.28	0.05

小世界網路的類別

Prizmič 指出，現實世界網路中的連通性分佈遵循冪律，並以 WWW 網路為例說明。該網路顯示出“小世界效應”，因為兩個文件之間的最短路徑隨節點總數 (N) 的對數增長。這意味著，即使網路規模增加，最短路徑也不會發生顯著變化。這是一種小世界網路。

Amaral 等人 指出，小世界網路有三種類型；1) 無標度網路，2) 廣度尺度網路，3) 單尺度網路。

1) 無標度網路：“頂點連通性分佈呈冪律衰減”

2) 廣度尺度網路：“連通性分佈呈現冪律區域，然後是急劇的截止”

3) 單尺度網路：“連通性分佈具有快速衰減的尾部”

無標度網路的例子包括 WWW 和科學論文的引用網路。廣度尺度網路是電影演員。單尺度網路是電力網、初中友誼、神經網路和聚合物鏈模型。

小世界網路在交通領域的應用

機場網路

圖 6 世界航空路線圖-2009 [作者：Jpatokal]

Amaral 等人 分析了機場網路的客運量和貨運量。結果表明，機場網路是單尺度網路，因為連通性分佈的衰減程度大於無標度網路。作者指出，容量限制是航空網路不顯示無標度網路的原因。航空網路具有樞紐輻射結構，航空公司傾向於連線到樞紐機場；但是，每個機場的貨運和客運處理能力是有限的。因此，連通性分佈不遵循冪律模型。

波士頓地鐵網路

圖 7 MBTA 波士頓地鐵圖 [作者：Citynoise]

Latora 和 Massimo 分析了波士頓地鐵網路，利用路徑長度 [L] 和聚類係數 [C] 來確定該網路是否為小世界網路。他們計算了路徑長度 (L=15.55)，但由於某些節點僅連線到網路中的一個節點，因此無法計算聚類係數。因此，他們使用替代因素效率 [E] 來解釋小世界網路。當最短路徑長度 [d] 更長時，效率 [E] 更低。 $E_{glob}$ 表示“整個網路的效率”，而 $E_{loc}$ 表示“節點鄰居子圖的平均效率”。作者指出，當 $E_{glob}$ 和 $E_{loc}$ 都很高時，該網路表現為小世界網路。結果 (表 3) 表明波士頓地鐵網路沒有表現出小世界網路的特徵，因為 $E_{loc}$ 較低，而 $E_{glob}$ 較高。另一方面，當作者將公交系統新增到地鐵網路中時，$E_{glob}$ 和 $E_{loc}$ 都很高。因此，波士頓交通網路可以建模為小規模網路。

$E={\dfrac {1}{N(N-1)}}\sum _{i\neq j}(1/d_{ij})$

表 3 波士頓地鐵網路的全域性和區域性效率 [Latora 和 Marchiori]

	$E_{glob}$	$E_{loc}$
波士頓地鐵	0.63	0.03
波士頓地鐵 + 公交	0.72	0.46

不同規模交通網路的自相關統計

圖 6 自相關統計 [Moran's I 和 Getis's G] 與機率 [p] 之間的關係 [衍生作品：圖片來自 Xu 和 Sui

Xu 和 Sui 介紹了一種方法，用於分析小世界屬性與網路自相關統計之間的關係，從而分析“小世界效應”；Moran's $I$ 和 Getis's $G$.

莫蘭指數 ($I$) 是自相關統計量之一，莫蘭指數 ($I$) 的正值說明了與鄰居的相似性；另一方面，$I$ 的負值解釋了與鄰居的不相似性。在 Getis's $G$ 方面，$G$ 的高值表明高值可能彼此捆綁在一起，而 $G$ 的低值表明低值更集中。在常規網路中，莫蘭指數 ($I$) 較高，而 Getis's $G$) 較低；但是，隨著機率 [p] 增加，莫蘭指數 ($I$) 急劇下降，而 Getis's $G$) 逐漸增加。

此外，這兩個值在小世界網路範圍內相互交叉。Getis's $G$) 的低值說明節點連線度低可能集中，而莫蘭指數 ($I$) 的低值表明全域性相關性小。這解釋了小世界網路的特徵，因此莫蘭指數 ($I$) 和 Getis's $G$) 的交點表明小世界網路。

他們將這種方法應用於三個交通網路：國家（美國州際和高速公路網路）、都市（休斯頓-加爾維斯頓地區的道路網路）和城市內（波士頓地鐵網路）。結果表明，莫蘭指數 ($I$) 和 Getis's $G$) 受滯後距離的影響很大。根據 Xu 和 Sui 的說法，滯後距離的含義是“鄰域的大小，即在計算網路自相關統計量時要考慮多少個鄰居”。隨著滯後距離的增加，莫蘭指數 ($I$) 降低；另一方面，Getis's $G$) 升高。此外，當莫蘭指數 ($I$) 和 Getis's $G$) 較低時，它們會相互交叉。他們發現交點值在所有交通網路中都相似。

擁堵因子與網路型別之間的關係

吳等人研究了三種類型的網路（小世界、無標度、隨機）中擁塞因子與交通量之間的關係。為了分配交通流，使用使用者均衡 (UE) 方法，並隨機分配鏈路容量。網路規模為 $400\times 400$，平均協調數 [k] 為 7。

結果表明，當交通量較小時，無標度網路和小世界網路比隨機網路更容易擁塞。另一方面，當交通量較大時，隨機網路比無標度網路和小世界網路更容易擁塞。這是因為在無標度網路和小世界網路中，大部分流量首先集中在樞紐節點上，但隨著交通量的增加，擁塞的增加速度相對較慢。另一方面，在隨機網路中，隨著交通量的增加，擁塞鏈路的數量穩定增長。與無標度網路和小世界網路相比，小世界網路更容易發生擁塞。因此，在三種類型的網路中，無標度網路可以處理最大的交通量。此外，他們還分析了擁塞因子與重連機率 [p] 和聚類係數 [C] 之間的關係，結果表明，當機率 [p] 和聚類係數 [C] 較大時，擁塞因子較小。

結論

“小世界網路”介於完全規則網路和隨機網路之間。Duncan 和 Strogatz用兩個特徵對該網路進行了數學解釋；路徑長度 [L] 和聚類係數 [C]。小世界網路像規則網路一樣高度聚類，路徑長度像隨機網路一樣小。根據研究，他們表明現實世界網路在生物、技術和社會網路中具有小世界網路的特徵。這是一個重大發現，因為小世界網路有可能對現實世界網路進行建模。

研究人員關注這一主題，因為它對於理解交流（例如，新聞、謠言和時尚的傳播）至關重要。尤其是在醫療領域，需要弄清楚疾病（例如，艾滋病毒、非典）傳播的特徵。此外，該主題還擴充套件到交通研究領域。現實世界網路結構並不統一，它具有多種型別的網路，因此很難對現實世界網路進行建模。研究是一個正在進行的工作，研究人員試圖解釋這個複雜的網路。