網路影像分析與社群結構探索

網路影像分析是理解複雜系統結構和行為的關鍵技術。本文使用 Python 的 NetworkX 函式庫，示範如何分析網路的路徑長度分佈、連通性、中心化程度和社群結構等特性。透過計算最短路徑長度、直徑、全域性叢集係數等指標，可以量化網路的拓撲結構，並比較不同型別網路的特性差異，例如空手道俱樂部網路、電力網路和網際網路。此外，最小割集、節點連通性和邊連通性等概念，有助於評估網路的強健性和抗毀性。特徵向量中心性、熵和基尼指數則可用於分析網路中節點的重要性分佈和不平等性。最後，社群檢測演算法可以揭示網路中隱藏的社群結構，進一步理解網路的組織和功能。

網路描述：整體影像 Chapter 6

路徑長度分佈的視覺化與分析

在分析網路結構時，路徑長度的分佈是一個重要的指標。為了視覺化這個分佈，我們可以定義一個函式 path_length_histogram() 來繪製最短路徑長度的直方圖：

import matplotlib.pyplot as plt
import networkx as nx

def path_length_histogram(G, title):
    all_shortest = [v for k, v in nx.shortest_path_length(G)]
    bins = max(all_shortest) - min(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()

內容解密：

1. path_length_histogram() 函式：計算並繪製給定網路 G 的最短路徑長度直方圖。

   • 使用 nx.shortest_path_length(G) 取得所有節點對之間的最短路徑長度。
   • 動態計算 bins 的數量以確保每個可能的路徑長度都有對應的 bin。
   • 使用 plt.hist() 繪製直方圖，並設定標題和軸標籤。

2. 子圖繪製：使用 plt.subplot() 將三個網路的路徑長度直方圖並排顯示。

   • 對每個網路（空手道俱樂部、電力網路、網際網路）呼叫 path_length_histogram()。

3. plt.tight_layout()：自動調整子圖的佈局，避免標籤重疊。

真實世界網路中的最短路徑長度分佈

觀察三個範例網路的路徑長度分佈，我們發現：

• 空手道俱樂部和網際網路具有非常小的路徑長度，這是社交網路和小世界現象的典型特徵。
• 電力網路的路徑長度較大，因為高壓線的建設成本高，通常只連線鄰近的節點。

平均最短路徑長度與直徑

為了簡化對路徑長度分佈的理解，我們可以使用以下兩個匯總指標：

1. 平均最短路徑長度（特性長度）：

   nx.average_shortest_path_length(G_karate)
   nx.average_shortest_path_length(G_electric)
   nx.average_shortest_path_length(G_internet)
   

   • 用於衡量網路的整體緊密程度。
   • 在斷開的網路中，平均路徑長度可能變為無窮大，可以透過調和平均或分元件計算來解決。

2. 直徑（Diameter）：

   nx.diameter(G_karate)
   nx.diameter(G_electric)
   nx.diameter(G_internet)
   

   • 定義為網路中最長的最短路徑長度。
   • 對個別極端值敏感，但可用於衡量最壞情況下的路徑長度。

全球叢集特性

衡量網路中的叢集程度可以使用以下指標：

1. 轉置性（Transitivity）：

   nx.transitivity(G_karate)
   nx.transitivity(G_electric)
   nx.transitivity(G_internet)
   

   • 表示網路中實際存在的三角形佔所有可能三角形的比例。

2. 全球叢集係數（Global Clustering Coefficient）：

   nx.average_clustering(G_karate)
   nx.average_clustering(G_electric)
   nx.average_clustering(G_internet)
   

   • 對所有節點的區域性叢集係數取平均。

網路韌性評估

1. 密度（Density）：

   nx.density(G_karate)
   nx.density(G_electric)
   nx.density(G_internet)
   

   • 用於衡量網路中實際存在的邊佔所有可能邊的比例。
   • 稀疏網路的邊數量接近節點數量，而稠密網路的邊數量接近節點數量的平方。

2. 最小割（Minimum Cut）：

   import networkx.algorithms.connectivity as nxcon
   nxcon.minimum_st_node_cut(G_karate, mr_hi, john_a)
   

   • 表示需要移除多少節點或邊才能將網路分成兩個不相連的部分。
   • 用於評估網路的韌性和冗餘路徑。

內容解密：

• 網路韌性是指系統在面對錯誤或攻擊時的抵抗能力，例如電力網在傳輸線故障時的持續供電能力。
• 最小割分析可用於找出網路中的關鍵節點或邊，以最佳化網路設計和提升韌性。

網路描述的宏觀視野 - 第六章

網路連通性分析

在網路分析中，連通性（Connectivity）是一個重要的衡量指標，用於評估網路的強健性和可靠性。NetworkX 提供了多種方法來計算網路的連通性，包括節點連通性和邊連通性。

最小割集（Minimum Cut）

最小割集是指將網路分割成兩個不相連的部分所需移除的最小節點或邊的集合。NetworkX 中的 minimum_st_node_cut 和 minimum_st_edge_cut 函式可以用來計算兩個特定節點之間的最小節點割集和最小邊割集。

import networkx as nx
import networkx.algorithms.connectivity as nxcon

# 載入空手道俱樂部網路
G_karate = nx.karate_club_graph()

# 計算特定節點對之間的最小節點割集
mr_hi = 0  # Mr. Hi
john_a = 33  # John A
node_cut = nxcon.minimum_st_node_cut(G_karate, mr_hi, john_a)
print("最小節點割集：", node_cut)

# 計算特定節點對之間的最小邊割集
edge_cut = nxcon.minimum_st_edge_cut(G_karate, mr_hi, john_a)
print("最小邊割集：", edge_cut)

連通性指標

• 節點連通性（Node Connectivity）：指網路中任意兩個節點之間的最少需要移除的節點數量，以使這兩個節點不相連。
• 邊連通性（Edge Connectivity）：指網路中任意兩個節點之間的最少需要移除的邊數量，以使這兩個節點不相連。

# 計算節點連通性
node_connectivity = nx.node_connectivity(G_karate, mr_hi, john_a)
print("節點連通性：", node_connectivity)

# 計算邊連通性
edge_connectivity = nx.edge_connectivity(G_karate, mr_hi, john_a)
print("邊連通性：", edge_connectivity)

網路整體連通性

除了計算特定節點對之間的連通性外，還可以計算整個網路的連通性指標。

# 計算整個網路的節點連通性
overall_node_connectivity = nx.node_connectivity(G_karate)
print("整體節點連通性：", overall_node_connectivity)

# 計算整個網路的平均節點連通性
average_node_connectivity = nx.average_node_connectivity(G_karate)
print("平均節點連通性：", average_node_connectivity)

網路中心化與不平等性

網路的中心化程度反映了其結構的不平等性。一個高度中心化的網路通常意味著少數節點掌握著大部分的連線。

特徵向量中心性（Eigenvector Centrality）

特徵向量中心性是一種衡量節點重要性的指標，它不僅考慮了節點的直接連線，還考慮了其鄰居的重要性。

# 計算特徵向量中心性
eigenvector_centrality = nx.eigenvector_centrality(G_karate)
print("特徵向量中心性：", eigenvector_centrality)

熵（Entropy）

熵可以用來衡量一組值的分佈是否均勻。在這裡，我們可以用它來評估網路中心性的分佈是否集中。

import math

def entropy(x):
    total = sum(x)
    x = [xi / total for xi in x]
    H = sum([-xi * math.log2(xi) for xi in x])
    return H

# 計算特徵向量中心性的熵
centrality_entropy = entropy(eigenvector_centrality.values())
print("特徵向量中心性的熵：", centrality_entropy)

透過這些分析，我們可以更深入地瞭解網路的結構特性，包括其連通性和中心化程度。這些指標對於理解和最佳化網路結構具有重要的意義。

網路結構分析：從全域性到社群

網路科學是一門跨學科領域，涉及數學、電腦科學、社會學等多個學科。網路可以用來描述各種複雜系統，如社交網路、蛋白質互動作用網路、網際網路等。瞭解網路的結構對於理解其功能和行為至關重要。

網路全域性結構描述

網路的全域性結構可以透過多種指標來描述，包括網路直徑、平均最短路徑、全域性聚類別係數等。這些指標可以幫助我們瞭解網路的規模、連通性和結構特徵。

網路直徑和平均最短路徑

網路直徑是指網路中最長的最短路徑，而平均最短路徑則是指所有節點對之間的最短路徑的平均值。這些指標可以用來衡量網路的規模和連通性。

import networkx as nx

# 建立一個圖
G = nx.Graph()

# 新增節點和邊
G.add_nodes_from([1, 2, 3, 4, 5])
G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

# 計算網路直徑
diameter = nx.diameter(G)

# 計算平均最短路徑
average_shortest_path = nx.average_shortest_path_length(G)

print("網路直徑：", diameter)
print("平均最短路徑：", average_shortest_path)

全域性聚類別係數

全域性聚類別係數用於衡量網路中節點的鄰居之間相互連線的可能性。它可以用來描述網路的區域性結構特徵。

# 計算全域性聚類別係數
clustering_coefficient = nx.clustering(G)

# 輸出全域性聚類別係數
print("全域性聚類別係數：", clustering_coefficient)

連通性指標

連通性指標，如最小節點/邊連通度，可以用來衡量網路的魯棒性和抗毀性。

# 計算最小節點連通度
node_connectivity = nx.node_connectivity(G)

# 計算最小邊連通度
edge_connectivity = nx.edge_connectivity(G)

print("最小節點連通度：", node_connectivity)
print("最小邊連通度：", edge_connectivity)

不平等性指標

不平等性指標，如熵和基尼指數，可以用來描述網路中節點屬性的分佈情況。

基尼指數

基尼指數是一種常用的不平等性指標，範圍從0到1，值越大表示不平等性越高。

def gini(x):
    x = [xi for xi in x]
    n = len(x)
    gini_num = sum([sum([abs(x_i - x_j) for x_j in x]) for x_i in x])
    gini_den = 2.0 * n * sum(x)
    return gini_num / gini_den

# 計算特徵向量中心性的基尼指數
centrality = nx.eigenvector_centrality(G)
gini_index = gini(centrality.values())

print("基尼指數：", gini_index)

內容解密：

• gini函式用於計算給定列表的基尼指數。
• 首先，將輸入列表x轉換為普通列表。
• 然後，計算列表的長度n。
• gini_num是透過兩層迴圈計算所有元素對之間的絕對差之和得到的。
• gini_den是透過計算列表元素總和並乘以2.0 * n得到的。
• 最後，傳回gini_num與gini_den的比值，即基尼指數。
• 使用nx.eigenvector_centrality計算網路的特徵向量中心性，並將結果傳入gini函式計算基尼指數。

社群結構分析

社群結構是網路中的一個重要特徵，指的是一組節點之間的連線比與其他節點之間的連線更緊密。社群檢測是網路科學中的一個重要課題。

社群檢測演算法

NetworkX提供了多種社群檢測演算法，如貪婪模組最大化演算法、譜社群檢測演算法等。

import community

# 使用貪婪模組最大化演算法進行社群檢測
partition = community.best_partition(G)

# 輸出社群分配結果
print("社群分配：", partition)

內容解密：

• community.best_partition函式使用貪婪模組最大化演算法對網路進行社群檢測。
• 傳回一個字典，其中鍵是節點ID，值是對應的社群標號。
• 這種演算法旨在最大化網路的模組度，從而劃分出最優的社群結構。