交通地理與網路科學/中心性

摘要

交通地理中存在各種網路，例如航空網路、道路網路和運河網路。一個重要的問題是如何衡量這些網路。如果我們關注節點的屬性，問題可以是：某些節點有多重要？以及如何量化它們的重要性？

中心性 衡量指標通常用於衡量節點的重要性。主要有三個類別：度中心性、接近中心性和中介中心性。

度中心性

度中心性透過節點所擁有的邊數（度）來衡量節點的重要性。其理念是，邊數越多的節點越重要。從數學上講，對於節點 j，其度中心性計算為其度的數量除以 n-1，其中 n 是圖中邊的總數。

接近中心性

接近中心性 透過節點到其他節點的測地距離來衡量節點的重要性。其理念是，節點離其他節點越近，該節點就越重要。從數學上講，它計算為所有其他節點測地距離之和的倒數。

中介中心性

中介中心性 透過節點在其他節點之間的路徑比例來衡量節點的重要性。其理念是，連線更多其他節點的節點越重要。從數學上講，節點 j 的中介中心性計算為從一個節點 s 到另一個節點 t 的最短路徑中經過 j 的比例。

一個思想實驗

您將使用哪種中心性指標來回答以下問題？。

• 如果我需要為我新成立的組織招募 10 人，我應該考慮誰？
• 如果我要將一條資訊傳遞給這個網路中的三個人，讓他們依次轉達給他們的朋友等等。我應該選擇哪三個人？
• 如果我要根據我的所有朋友在這個網路中的“中心性”對他們進行排名，我該如何去做？
• 如果我要為這個 500 人的團隊提名一個領導人，我應該選擇誰？

技術討論

改編自維基百科關於 中心性 的文章

在 w:圖論 和 w:網路分析 中，存在各種度量圖中頂點的中心性，這些度量決定了頂點在圖中的相對重要性（例如，一個人在w:社交網路中的重要性，或者，在w:空間句法理論中，一個房間在一個建築中的重要性，或者一條道路在一個w:城市網路中的使用程度）。

網路分析中廣泛使用四種中心性度量：度中心性、中介性、接近性和特徵向量中心性。有關對加權網路的回顧以及泛化，請參見 Opsahl 等人 (2010)。

度中心性

主要文章：度 (圖論)

第一個也是最簡單的就是度中心性。度中心性定義為與一個節點相連的邊的數量（即，一個節點所擁有的聯絡數量）。度通常根據節點在網路中感染流經網路的東西（如病毒或某種資訊）的直接風險進行解釋。如果網路是有向的（這意味著聯絡是有方向的），那麼我們通常定義兩種獨立的度中心性度量，即w:入度 和 w:出度。入度是節點接收到的聯絡數量的統計，而出度是節點發出的聯絡數量的統計。對於友誼或建議等積極的關係，我們通常將入度解釋為一種受歡迎程度，而將出度解釋為愛交際程度。

對於一個圖 $G:=(V,E)$，其中有 n 個頂點，頂點 $v$ 的度中心度 $C_{D}(v)$ 為

$C_{D}(v)={\frac {{\text{deg}}(v)}{n-1}}$

在一個圖的 密集 鄰接矩陣 表示中，計算所有節點 $V$ 的度中心度需要 $\Theta (V^{2})$；而在一個圖的 稀疏 鄰接矩陣 表示中，計算所有邊 $E$ 的度中心度需要 $\Theta (E)$。

中心度的定義可以擴充套件到圖。令 $v*$ 為圖 $G$ 中度中心度最高的節點。令 $X:=(Y,Z)$ 為使以下量最大化的 $n$ 個節點連線的圖（$y*$ 為圖 $X$ 中度中心度最高的節點）

$H=\displaystyle {\sum _{j=1}^{|Y|}{C_{D}(y*)-C_{D}(y_{j})}}$

則圖 $G$ 的度中心度定義如下：

$C_{D}(G)={\frac {\displaystyle {\sum _{i=1}^{|V|}{[C_{D}(v*)-C_{D}(v_{i})]}}}{H}}$

$H$ 在圖 $X$ 包含一個連線到所有其他節點的節點，而所有其他節點僅連線到該中心節點（一個 w:star graph）時最大化。在這種情況下

$H=(n-1)(1-{\frac {1}{n-1}})=n-2$

因此 $G$ 的度中心性簡化為

$C_{D}(G)={\frac {\displaystyle {\sum _{i=1}^{|V|}{[C_{D}(v*)-C_{D}(v_{i})]}}}{n-2}}$

中介中心性

色調（從紅色=0 到藍色=最大）顯示節點介數中心性。

介數中心性是圖中 頂點 的一箇中心性度量（也存在 邊 介數中心性，這裡沒有討論）。出現在其他頂點之間許多 最短路徑 上的頂點比那些不在最短路徑上的頂點具有更高的介數中心性。

對於具有 n 個頂點的圖 $G:=(V,E)$，頂點 $v$ 的介數中心性 $C_{B}(v)$ 如下計算

1. 對於每對頂點 (s,t)，計算它們之間的所有 最短路徑。

2. 對於每對頂點 (s,t)，確定透過目標頂點（此處為頂點 v）的最短路徑所佔的比例。

3. 對所有頂點對 (s,t) 的比例進行求和。

或者，更簡潔地說：

$C_{B}(v)=\sum _{s\neq v\neq t\in V}{\frac {\sigma _{st}(v)}{\sigma _{st}}}$

其中 $\sigma _{st}$ 是從s到t的最短路徑數量，而 $\sigma _{st}(v)$ 是從s到t且經過頂點v的最短路徑數量。可以透過除以檢查的路徑數量來進行歸一化，即$(n-1)(n-2).$ 對於無向圖，只需要檢查每對頂點之間方向之一，因此總共只有$(n-1)(n-2)/2$ 條路徑，這也等於不包括v的頂點對的數量。例如，在無向星形圖中，中心頂點（包含在所有可能的 shortest path 中）的介數為$(n-1)(n-2)/2$（歸一化後為 1），而葉子（不包含在任何最短路徑中）的介數為 0。

計算圖中所有頂點的介數和接近中心度需要計算圖中所有頂點對之間的最短路徑。這需要 $\Theta (V^{3})$ 時間，使用 w:弗洛伊德-沃舍爾演算法，修改為不僅找到一條路徑，而且計算兩個節點之間所有最短路徑。在稀疏圖上，w:約翰遜演算法 可能更有效，需要$O(V^{2}\log V+VE)$ 時間。在無權圖上，使用 Brandes 演算法計算介數中心度需要 $O(VE)$ 時間。

在計算圖中所有頂點的介數和接近中心度時，假設圖是無向的、連通的，並且允許存在自環和重邊。當專門處理網路圖時，通常圖中沒有自環或重邊，以保持簡單的關係（邊表示兩個人或頂點之間的連線）。在這種情況下，使用 Brandes 演算法會將最終的中心度分數除以 2，以說明每條最短路徑都被計算了兩次。

接近中心性

在w:拓撲學和數學中相關的領域，接近度是拓撲空間中的基本概念之一。直觀地說，我們說兩個集合是接近的，如果它們彼此任意接近。這個概念可以在w:度量空間中自然地定義，其中定義了空間元素之間的距離概念，但它可以推廣到拓撲空間，在拓撲空間中，我們沒有具體的方法來度量距離。

在w:圖論中，接近度是圖中頂點的中心度度量。對其他頂點“淺”的頂點（即那些傾向於對圖中其他頂點有較短的測地距離的頂點）具有較高的接近度。在w:網路分析中，接近度被用來表示最短路徑長度，因為它對更中心化的頂點賦予更高的值，因此通常與其他度量（如度數）呈正相關。

在網路理論中，接近度是中心度的複雜度量。它被定義為頂點v與其可達到的所有其他頂點之間的平均測地距離（即最短路徑）

${\frac {\displaystyle \sum _{t\in V\setminus v}d_{G}(v,t)}{n-1}}$

其中 $n\geq 2$ 是網路從節點 v 可達的 '連通分量' V 的大小。緊密性可以被認為是衡量資訊從給定節點傳播到網路中其他可達節點所需時間的一種度量。

有些人將緊密性定義為該數量的倒數，但無論哪種方式，傳遞的資訊都是一樣的（這次估計的是速度而不是時間跨度）。節點 $v$ 的緊密性 $C_{C}(v)$ 是 V 中所有其他節點到該節點的 測地距離 之和的倒數。

$C_{C}(v)={\frac {1}{\sum _{t\in V\setminus v}d_{G}(v,t)}}.$

不同的方法和演算法可以被用來衡量緊密性，例如 Noh 和 Rieger（2003）提出的 隨機遊走中心性，它衡量隨機遊走訊息從網路中的其他地方到達一個節點的速度——一種隨機遊走版本的中心性。

Stephenson 和 Zelen（1989）的 資訊中心性 是另一個緊密性度量，它與 Noh 和 Rieger 的度量有一些相似之處。本質上，它衡量的是以節點 i 為終點的路徑的調和平均長度，如果 i 有很多連線到其他節點的短路徑，則該值會更小。

Dangalchev（2006）為了衡量網路脆弱性，修改了緊密性的定義，使其適用於非連通圖，並且總的緊密性更容易計算。

$C_{C}(v)=\sum _{t\in V\setminus v}2^{-d_{G}(v,t)}.$

Opsahl（2010）提出了一個擴充套件，用於具有非連通分量的網路。

特徵向量中心性

特徵向量中心性是衡量網路中 節點 重要性的一個度量。它根據連線到高得分節點比連線到低得分節點對節點分數的貢獻更大這一原則，為網路中的所有節點分配相對得分。w:Google 的 w:PageRank 是特徵向量中心性度量的變體。

使用鄰接矩陣查詢特徵向量中心性

令 $x_{i}$ 表示第 $i^{th}$ 個節點的分數。令 $A_{i,j}$ 是網路的 w:鄰接矩陣。因此，如果第 $i^{th}$ 個節點與第 $j^{th}$ 個節點相鄰，則 $A_{i,j}=1$，否則 $A_{i,j}=0$。更一般地說，A 中的條目可以是表示連線強度的實數，如 w:隨機矩陣 中的條目。

對於第 $i^{th}$ 個節點，令其中心度得分與其所有連線節點的得分之和成正比。因此

$x_{i}={\frac {1}{\lambda }}\sum _{j\in M(i)}x_{j}={\frac {1}{\lambda }}\sum _{j=1}^{N}A_{i,j}x_{j}$

其中 $M(i)$ 是連線到第 $i^{th}$ 個節點的所有節點的集合，N 是節點總數，$\lambda$ 是一個常數。用向量表示法可以改寫為

$\mathbf {x} ={\frac {1}{\lambda }}\mathbf {Ax}$，或作為 w:特徵向量 方程 $\mathbf {Ax} ={\lambda }\mathbf {x}$

通常，會有許多不同的 w:特徵值 $\lambda$ 存在特徵向量解。然而，特徵向量所有元素都為正的附加要求意味著（根據 w:佩龍-弗羅貝尼烏斯定理）只有最大的特徵值才會產生所需的中心度度量。 然後，相關特徵向量的第 $i^{th}$ 個分量就給出網路中第 $i^{th}$ 個節點的中心度得分。 w:冪迭代 是許多用於尋找此主導特徵向量的 w:特徵值演算法 之一。

另見

• 圖中的距離

進一步閱讀

• Freeman, L. C. (1979). 社會網路中的中心性：概念澄清。社會網路，1(3), 215-239.
• Sabidussi, G. (1966). 圖的中心性指標。心理測量學，31 (4), 581-603.
• Freeman, L. C. (1977) 一套基於介數的中心性指標。社會計量學 40, 35-41.
• Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. 和 Zlotowski, O. (2005) 中心性指標。在 Brandes, U. 和 Erlebach, T. (Eds.) 網路分析：方法論基礎, pp. 16–61, LNCS 3418, Springer-Verlag.
• Bonacich, P.(1987) 權力和中心性：一組指標，美國社會學雜誌，92 (5), pp 1170–1182

外部連結

• https://networkx.lanl.gov/trac/attachment/ticket/119/page_rank.py
• http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html