網路分析在理解複雜系統中扮演著關鍵角色，中心性指標能識別網路中的關鍵節點，而整體結構分析則揭示網路的宏觀特性。本文利用 Python 的 NetworkX 函式庫，示範如何計算各種中心性指標，例如接近中心性和本地聚類別係數，並以婦女參政運動網路為例，說明如何解讀這些指標。此外，文章也探討了描述網路整體結構的關鍵指標，包括直徑、平均最短路徑長度、全域叢集係數以及網路韌性，並使用空手道俱樂部、德國電網和歐洲 GÉANT 網路等不同型別的真實世界網路進行比較分析，展現不同網路結構特性之間的差異與關聯。透過這些分析，我們可以更深入地理解網路的行為模式，並應用於社交網路分析、基礎設施規劃和通訊網路最佳化等領域。
小規模網路分析：節點與中心性指標
在網路科學中，中心性（Centrality）是衡量節點重要性的關鍵指標。本章節將介紹幾種常見的中心性指標，並透過對婦女參政運動（Suffragette）網路的分析，展示如何運用這些指標來理解網路結構。
接近中心性（Closeness Centrality）
接近中心性是網路科學中最古老的中心性指標之一，由社會學家亞歷克斯·巴威拉斯（Alex Bavelas）在1950年提出。該指標定義為節點到其他所有節點距離之和的倒數。具有高接近中心性的節點意味著它與其他節點的平均距離較短，能夠快速傳遞資源。
以下範例使用 NetworkX 的 closeness_centrality() 函式計算婦女參政運動網路的接近中心性，並顯示前10個節點：
closeness = nx.closeness_centrality(G)
sorted(closeness.items(), key=lambda x: x[1], reverse=True)[0:10]
輸出結果如下：
[('Maud Joachim', 0.5357241748956739),
('Winifred Mayo', 0.5009438937877011),
('Caroline A Downing', 0.5009438937877011),
('Mabel Capper', 0.5006919099377073),
('Kitty Marion', 0.49793672684150186),
('Ada Wright', 0.4898501559823633),
('Patricia Woodlock', 0.4886477746471095),
('Vera Wentworth', 0.48769011119851163),
('Evelyn Whurry', 0.4874512815652116),
('Annie Bell', 0.4869743233640714)]
內容解密：
closeness_centrality()函式計算每個節點的接近中心性。sorted()函式根據接近中心性值進行排序，選取前10個節點。- 結果顯示
Maud Joachim具有最高的接近中心性，表明她在網路中具有較強的影響力。
本地聚類別係數（Local Clustering Coefficient）
本地聚類別係數衡量一個節點的鄰居之間是否相互連線。在社會網路中，這相當於詢問「朋友的朋友是否也是你的朋友」。該指標用於評估網路的穩健性和冗餘性。
以下範例使用 NetworkX 的 triangles() 和 clustering() 函式計算婦女參政運動網路中節點的三角形數量和本地聚類別係數：
triangles = nx.triangles(G)
sorted(triangles.items(), key=lambda x: x[1], reverse=True)[0:10]
clustering = nx.clustering(G)
[(x, clustering[x]) for x in sorted(people, key=lambda x: eigenvector[x], reverse=True)[0:10]]
輸出結果如下：
[('Maud Joachim', 19687),
('Caroline A Downing', 18201),
('Kitty Marion', 17696),
('Mabel Capper', 16811),
('Winifred Mayo', 16455),
('Annie Bell', 16065),
('Grace Chappelow', 16018),
('Ellen Pitfield', 14910),
('Mrs Maud Fussell', 14841),
('Dorothy Agnes Bowker', 14750)]
[('Maud Joachim', 0.23595330552759),
('Caroline A Downing', 0.34999903851700864),
('Kitty Marion', 0.3670988486671507),
('Mabel Capper', 0.33992518451117176),
('Annie Bell', 0.4233201581027668),
('Grace Chappelow', 0.43461037551551984),
('Winifred Mayo', 0.3480477177545582),
('Ellen Pitfield', 0.4828993392926545),
('Dorothy Agnes Bowker', 0.5058125578683859),
('Mrs Maud Fussell', 0.5006071645415908)]
內容解密：
triangles()函式計算每個節點參與的三角形數量。clustering()函式計算每個節點的本地聚類別係數。- 結果顯示
Maud Joachim具有最高的三角形數量，但其本地聚類別係數相對較低，表明她的鄰居之間並非完全相互連線。
網路的整體結構描述
不同網路之間的大規模結構可能存在顯著差異，這些差異往往反映了不同型別的網路特性（例如社交網路與技術網路）。大規模結構對於理解網路的功能特性（如對錯誤和攻擊的韌性）至關重要。本章將介紹用於分類別整個網路的各種結構度量方法，並以不同型別的真實世界網路為例進行說明。
本章涵蓋的主題
- 整體結構：瞭解整個網路的屬性
- 直徑與最短路徑：如何衡量網路的大小
- 全域叢集係數：利用叢集係數量化鄰居之間的相互連執行緒度
- 韌性：密度和最小切割等屬性如何量化錯誤和攻擊的容忍度
- 不平等性：學習如何衡量網路結構中的平等或不平等程度
網路的整體結構
在嘗試理解網路的一般趨勢或探索不同網路之間的差異時，單純觀察複雜的網路圖形（hairballs）並不特別有用。定量衡量大規模網路結構使得描述和比較不同網路成為可能。
大規模結構可以幫助我們解決以下問題：
- 網路在成長過程中是否變得更具韌性或更容易受到故障影響？
- 資料或電力在網路中傳輸時需要行經多遠？
- 網路的集中程度如何？
- 節點是否聚整合緊密相連的群組？
範例網路資料集
本章使用多個範例網路來探討大規模網路結構。首先是熟悉的空手道俱樂部網路（Zachary, 1977），這是社交網路的典型代表。該網路可以直接從 NetworkX 中載入：
G_karate = nx.karate_club_graph()
mr_hi = 0
john_a = 33
第二個範例是德國電網（Mureddu, 2016），其中節點代表發電機和變壓器，邊代表高壓輸電線。由於每個節點對應到物理空間，大多數連線發生在地理位置相近的節點之間，這是基礎設施網路的共同特徵。以下程式碼從邊列表格式檔案中載入該網路：
# 載入德國電網
with open(data_dir / 'mureddu2016' / '0.2' / 'branches.csv', 'rb') as f:
# 跳過標頭
next(f)
# 讀取邊列表格式
G_electric = nx.read_edgelist(
f,
delimiter="\t",
create_using=nx.Graph,
data=[('X', float), ('Pmax', float)])
內容解密：
此段程式碼主要功能是載入德國電網的資料。首先開啟指定的 CSV 檔案並跳過標頭行，然後使用 read_edgelist 函式讀取邊列表並構建無向圖 G_electric。data 引數用於指定邊的屬性，如輸電線的電抗（‘X’）和最大功率（‘Pmax’）。
第三個範例是歐洲 GÉANT 網路，一個連線歐洲研究和教育網路的通訊網路。節點代表存在點（Points of Presence, PoP），邊代表高容量通訊鏈路。以下程式碼從 GraphML 格式檔案中載入該網路：
G_internet = nx.read_graphml(data_dir / 'UAITZ' / 'Geant2012.graphml')
內容解密：
此處使用 read_graphml 函式從 GraphML 檔案中讀取 GÉANT 網路的結構和屬性，GraphML 是一種用於描述複雜網路的 XML 格式，能夠儲存節點和邊的詳細資訊。
網路視覺化
以下程式碼將三個範例網路視覺化：
# 建立圖形
plt.figure(figsize=(7.5, 2.75))
# 繪製網路
plt.subplot(1, 3, 1)
plt.title("Karate")
nx.draw_networkx(G_karate, node_size=0, with_labels=False)
plt.subplot(1, 3, 2)
plt.title("Electric")
nx.draw_networkx(G_electric, node_size=0, with_labels=False)
plt.subplot(1, 3, 3)
plt.title("Internet")
nx.draw_networkx(G_internet, node_size=0, with_labels=False)
# 調整佈局
plt.tight_layout()
內容解密：
這段程式碼使用 Matplotlib 和 NetworkX 將三個網路圖形並排顯示，分別代表空手道俱樂部、德國電網和 GÉANT 網路。每個子圖使用 draw_networkx 函式繪製，節點大小設為 0 且不顯示標籤，最後調整佈局以避免重疊。
直徑與平均最短路徑
網路的大小可以透過多種方式量化。在第 5 章中，節點之間的距離被定義為它們之間的最短路徑長度。有了衡量距離的方法，就可以根據距離定義網路的大小。
NetworkX 提供了多個方便的函式來尋找距離和最短路徑。例如，使用 all_shortest_paths() 函式可以找到兩個特定節點之間的所有最短路徑：
list(nx.all_shortest_paths(G_karate, mr_hi, john_a))
[[0, 8, 33], [0, 13, 33], [0, 19, 33], [0, 31, 33]]
如果只需要知道距離，可以使用 shortest_path_length() 函式：
nx.shortest_path_length(G_karate, mr_hi, john_a)
2
內容解密：
這段程式碼展示瞭如何使用 NetworkX 中的函式來計算空手道俱樂部網路中 Mr. Hi（節點 0）和 John A.（節點 33）之間的最短路徑和距離。結果顯示兩者之間的距離為 2，意味著最多經過一個中間節點即可到達。
最短路徑長度分佈
可以使用以下函式繪製某個網路中所有最短路徑長度的直方圖：
def path_length_histogram(G, title=None):
# 計算最短路徑長度
length_source_target = dict(nx.shortest_path_length(G))
# 將字典轉換為扁平列表
all_shortest = sum([
list(length_target.values())
for length_target in length_source_target.values()],
[])
# 計算整數區間
high = max(all_shortest)
bins = [-0.5 + i for i in range(high + 2)]
# 繪製直方圖
plt.hist(all_shortest, bins=bins, alpha=0.7, color='blue', edgecolor='black')
plt.xlabel('最短路徑長度')
plt.ylabel('頻率')
plt.title(title if title else '最短路徑長度分佈')
plt.show()
內容解密：
此函式首先計算輸入網路 G 中所有節點對之間的最短路徑長度，並將結果儲存在 length_source_target 字典中。接著，它將這些長度整理成一個扁平列表 all_shortest。然後，根據最長路徑的值確定直方圖的區間，並繪製最短路徑長度的分佈直方圖，用於展示網路的緊密程度。
網路描述的宏觀視角 - 第 6 章
路徑長度分佈的視覺化
在分析網路結構時，路徑長度的分佈是一個重要的指標。為了視覺化這個分佈，我們可以定義一個函式 path_length_histogram() 來繪製最短路徑長度的直方圖。
import matplotlib.pyplot as plt
import networkx as nx
def path_length_histogram(G, title):
# 計算所有節點對之間的最短路徑長度
all_shortest = [v for v in nx.shortest_path_length(G)]
# 取得最短路徑長度的最大值以決定直方圖的 bins 數量
bins = max(all_shortest) + 1
# 繪製直方圖
plt.hist(all_shortest, bins=bins, rwidth=0.8)
plt.title(title)
plt.xlabel("距離")
plt.ylabel("計數")
# 建立圖形
plt.figure(figsize=(7.5, 2.5))
# 繪製三個範例網路的路徑長度直方圖
plt.subplot(1, 3, 1)
path_length_histogram(G_karate, title="空手道俱樂部")
plt.subplot(1, 3, 2)
path_length_histogram(G_electric, title="電力網路")
plt.subplot(1, 3, 3)
path_length_histogram(G_internet, title="網際網路")
# 調整佈局
plt.tight_layout()
內容解密：
- 使用
nx.shortest_path_length(G)計算網路G中所有節點對之間的最短路徑長度。 - 直方圖的 bins 數量根據最短路徑長度的最大值決定，以確保每個不同的路徑長度都有對應的 bin。
- 使用
plt.hist()繪製直方圖，並設定標題、x 軸標籤和 y 軸標籤。
真實世界網路中的最短路徑長度分佈
觀察三個範例網路（空手道俱樂部、電力網路和網際網路）的最短路徑長度分佈，可以發現社交網路（如空手道俱樂部）傾向於具有較短的路徑長度，這被稱為「小世界現象」。基礎設施網路（如電力網路）由於高壓線的成本較高，通常只連線鄰近的節點，因此路徑長度較長。網際網路雖然也是基礎設施網路，但由於其包含許多跨越長距離的連線，因此具有較小的路徑長度。
平均最短路徑長度
平均最短路徑長度（也稱為特徵長度）是描述網路大小的一個重要指標。可以使用 nx.average_shortest_path_length(G) 計算。
print(nx.average_shortest_path_length(G_karate))
print(nx.average_shortest_path_length(G_electric))
print(nx.average_shortest_path_length(G_internet))
內容解密：
nx.average_shortest_path_length(G)計算網路G的平均最短路徑長度。- 在斷開的網路中，平均最短路徑長度可能變成無窮大。可以透過使用調和平均數或對每個連通分量內的平均最短路徑長度進行平均來解決這個問題。
網路直徑
網路直徑是指網路中任意兩節點之間的最長最短路徑長度。可以使用 nx.diameter(G) 計算。
print(nx.diameter(G_karate))
print(nx.diameter(G_electric))
print(nx.diameter(G_internet))
內容解密：
nx.diameter(G)計算網路G的直徑。- 網路直徑只依賴於一條路徑，因此單個異常值可能會大大增加直徑。
全球叢集係數
全球叢集係數用於衡量網路中的叢集程度。可以使用傳遞性（transitivity）或平均區域性叢集係數（average clustering coefficient）來衡量。
print(nx.transitivity(G_karate))
print(nx.transitivity(G_electric))
print(nx.transitivity(G_internet))
print(nx.average_clustering(G_karate))
print(nx.average_clustering(G_electric))
print(nx.average_clustering(G_internet))
內容解密：
nx.transitivity(G)計算網路G的傳遞性，即實際存在的三角形數量佔可能三角形數量的比例。nx.average_clustering(G)計算網路G的平均區域性叢集係數，即所有節點的區域性叢集係數的平均值。
網路韌性
網路韌性是指網路在面對錯誤或攻擊時的還原能力。可以使用密度（density）和最小割（minimum cut）等指標來衡量。
print(nx.density(G_karate))
print(nx.density(G_electric))
print(nx.density(G_internet))
內容解密：
nx.density(G)計算網路G的密度，即實際存在的邊數量佔可能邊數量的比例。- 網路密度越高，表示網路中冗餘路徑越多，韌性越強。
最小割
最小割是指需要移除的最少節點或邊數，以將網路分成兩個不連通的部分。可以使用 nxcon.minimum_st_node_cut(G, s, t) 計算。
import networkx.algorithms.connectivity as nxcon
print(nxcon.minimum_st_node_cut(G_karate, mr_hi, john_a))
內容解密：
nxcon.minimum_st_node_cut(G, s, t)計算網路G中節點s和t之間的最小節點割。- 最小割可以衡量網路在特定節點之間的韌性。
