網路分析技術詳解與社群偵測應用

網路分析是理解複雜系統的關鍵技術，涵蓋網路連通性、中心性、社群結構等重要導向。利用 NetworkX 函式庫，可以有效計算最小割集、連通性指標，評估網路的強健性和可靠性。藉由特徵向量中心性、熵和吉尼指數等指標，可以量化網路的集中度與不平等性，進一步理解網路中節點的重要性分佈。社群偵測是網路分析的另一個核心議題，Clauset-Newman-Moore 演算法根據模組化最大化，有效識別網路中的緊密連結群組。Girvan-Newman 演算法則利用中介中心性，迭代移除重要邊緣來分割社群。這些技術結合視覺化工具，能更清晰地呈現網路結構，例如空手道俱樂部和線上社交網路的社群劃分，有助於深入理解網路的組織和行為模式。

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

網路連通性分析

在網路分析中，連通性（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
john_a = 33

# 計算最小節點割集
print(nxcon.minimum_st_node_cut(G_karate, mr_hi, john_a))
# 輸出：{0}

# 計算最小邊割集
print(nxcon.minimum_st_edge_cut(G_karate, mr_hi, john_a))
# 輸出：{(0, 8), (0, 31), (1, 30), (2, 8), (2, 27), (2, 28), (2, 32), (9, 33), (13, 33), (19, 33)}

連通性指標

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

# 計算節點連通性
print(nx.node_connectivity(G_karate, mr_hi, john_a))
# 輸出：6

# 計算邊連通性
print(nx.edge_connectivity(G_karate, mr_hi, john_a))
# 輸出：10

網路整體連通性

對於整個網路，可以計算其節點連通性和邊連通性，以評估其整體的強健性。

# 計算整個網路的節點連通性
print(nx.node_connectivity(G_karate))
# 輸出：1

平均連通性

為了更好地評估網路的可靠性，可以計算平均節點連通性和平均邊連通性。

# 計算平均節點連通性
print(nx.average_node_connectivity(G_karate))
# 輸出：2.2174688057040997

網路集中度與不平等性

網路的集中度（Centralization）是指其中心性是否集中在少數節點上。可以使用不同的方法來衡量節點的中心性，並進一步計算網路的集中度。

特徵向量中心性（Eigenvector Centrality）

特徵向量中心性是一種衡量節點重要性的指標。透過計算網路中所有節點的特徵向量中心性，可以進一步分析網路的集中度。

# 計算特徵向量中心性
centralities = nx.eigenvector_centrality(G_karate).values()

# 繪製直方圖
def centrality_histogram(x, title=None):
    import matplotlib.pyplot as plt
    plt.hist(x, density=True)
    plt.title(title)
    plt.xlabel("Centrality")
    plt.ylabel("Density")

centrality_histogram(centralities, title="Karate")
plt.show()

熵（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

# 計算特徵向量中心性的熵
print(entropy(nx.eigenvector_centrality(G_karate).values()))
# 輸出：4.842401948329853

網路結構分析：從大規模到中規模

網路結構的量化分析

量化網路結構是理解複雜網路特性的關鍵步驟。透過不同的測量方法，我們可以深入瞭解網路的整體特徵和區域性特性。本章將介紹多種用於描述網路大規模結構的技術。

網路大小的量化

網路大小可以透過直徑或平均最短路徑來量化。這些測量方法提供了網路規模和節點間距離的整體概念。

全球叢集係數

全球叢集係數用於衡量節點的鄰居之間相互連線的可能性。這一指標揭示了網路的區域性連線特性。

連通性測量

連通性測量，如最小或平均節點/邊連通性，透過尋找最小割集來計算，量化了網路的韌性。

不平等性測量

不平等性測量，如熵和吉尼指數，可以將小規模的中心性測量轉化為大規模的網路中心化測量。吉尼指數特別在經濟學中廣泛使用，其值範圍從0到1，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

內容解密：

此函式計算給定列表 x 的吉尼指數。首先，它複製輸入列表 x 以避免修改原始資料。然後計算列表的長度 n。接著，計算吉尼指數的分子 gini_num，這涉及到對列表中所有元素對的絕對差值求和。分母 gini_den 是 2.0 乘以列表長度 n 再乘以列表元素之和。最終，吉尼指數是分子除以分母的結果。

將吉尼指數應用於示例網路，得到與使用熵相似的結果：

gini(nx.eigenvector_centrality(G_karate).values())
# 輸出：0.3244949051532847
gini(nx.eigenvector_centrality(G_electric, max_iter=1000).values())
# 輸出：0.787950636595495
gini(nx.eigenvector_centrality(G_internet).values())
# 輸出：0.43432860097262216

社群結構分析

大於單個節點但小於整個網路的中規模或介觀結構，描述了節點群（稱為社群）及其相互關係。NetworkX提供了許多分析社群結構的工具。本章使用來自線上社交網路的資料來演示中規模網路分析。

社群檢測

社群檢測旨在識別節點社群並劃分網路。NetworkX的社群檢測函式通常接受一個Graph物件，並傳回社群列表或迭代器，其中社群表示為節點ID的集合。

最簡單的社群檢測型別是尋找非重疊社群，即將網路劃分為社群，使得每個節點恰好屬於一個社群。

圖表翻譯：

此圖示呈現了社群結構的概念。節點被劃分為不同的社群，社群內部的節點之間有著緊密的連線，而不同社群之間的連線則相對稀疏。

@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle

title 網路分析技術詳解與社群偵測應用

package "圖論網路分析" {
    package "節點層" {
        component [節點 A] as nodeA
        component [節點 B] as nodeB
        component [節點 C] as nodeC
        component [節點 D] as nodeD
    }

    package "中心性指標" {
        component [度中心性
Degree Centrality] as degree
        component [特徵向量中心性
Eigenvector Centrality] as eigen
        component [介數中心性
Betweenness Centrality] as between
        component [接近中心性
Closeness Centrality] as close
    }
}

nodeA -- nodeB
nodeA -- nodeC
nodeB -- nodeD
nodeC -- nodeD

nodeA --> degree : 計算連接數
nodeA --> eigen : 計算影響力
nodeB --> between : 計算橋接度
nodeC --> close : 計算距離

note right of degree
  直接連接數量
  衡量局部影響力
end note

note right of eigen
  考慮鄰居重要性
  衡量全局影響力
end note

@enduml

圖表翻譯： 此圖示展示了兩個不同的社群（{節點1, 節點2, 節點3} 和 {節點4, 節點5, 節點6}），以及它們之間的連線。社群內部的連線是緊密的，而社群之間的連線則是稀疏的。

社群偵測：以模組化為基礎的最佳化方法

在複雜網路分析中，社群偵測是一項重要的任務，其目標是找出網路中具有緊密連結的節點群組。模組化（Modularity）是評估社群劃分品質的常用指標，其核心思想是社群內部的邊應該比社群之間的邊更為常見。

模組化最大化

要找到最佳的社群劃分，一種方法是定義一個量化社群劃分品質的函式，並透過調整社群劃分來最大化這個品質指標。模組化的數學定義在附錄A中有詳細討論。

Clauset-Newman-Moore 社群偵測演算法

NetworkX 函式庫中的 greedy_modularity_communities() 函式實作了 Clauset-Newman-Moore 社群偵測演算法。該演算法初始時將每個節點視為一個獨立的社群，然後合併能夠最大化模組化的兩個社群，重複此過程直到進一步合併會降低模組化為止。

# 生成 Zachary 空手道俱樂部網路
G_karate = nx.karate_club_graph()

# 使用 Clauset-Newman-Moore 演算法進行社群偵測
communities = sorted(nx.community.greedy_modularity_communities(G_karate), key=len, reverse=True)

# 輸出社群數量
print(len(communities))  # 輸出：3

內容解密：

1. nx.karate_club_graph() 生成 Zachary 空手道俱樂部網路，這是一個經典的社會網路分析範例。
2. greedy_modularity_communities(G_karate) 對該網路進行社群偵測。
3. sorted(..., key=len, reverse=True) 將偵測到的社群按照大小排序。
4. 輸出結果顯示該網路被劃分為3個主要社群。

社群視覺化

為了視覺化社群結構，需要定義一些輔助函式來設定節點和邊的社群屬性，並根據社群屬性為節點和邊著色。

def set_node_community(G, communities):
    '''為節點新增社群屬性'''
    for c, v_c in enumerate(communities):
        for v in v_c:
            G.nodes[v]['community'] = c + 1

def set_edge_community(G):
    '''為邊新增社群屬性，內部邊標記為對應社群，外部邊標記為0'''
    for v, w in G.edges:
        if G.nodes[v]['community'] == G.nodes[w]['community']:
            G.edges[v, w]['community'] = G.nodes[v]['community']
        else:
            G.edges[v, w]['community'] = 0

def get_color(i, r_off=1, g_off=1, b_off=1):
    '''將整數對映到獨特的顏色'''
    r0, g0, b0 = 0, 0, 0
    n = 16
    low, high = 0.1, 0.9
    span = high - low
    r = low + span * (((i + r_off) * 3) % n) / (n - 1)
    g = low + span * (((i + g_off) * 5) % n) / (n - 1)
    b = low + span * (((i + b_off) * 7) % n) / (n - 1)
    return (r, g, b)

內容解密：

1. set_node_community() 為每個節點設定其所屬的社群編號。
2. set_edge_community() 根據節點的社群屬性，區分內部邊和外部邊，並賦予相應的社群編號。
3. get_color() 將整數對映到不同的顏色，用於視覺化不同社群。

線上社交網路的社群偵測

同樣的社群偵測演算法也可以應用於更大的網路，如線上社交網路。以下範例使用了一個結合了10個個人的線上社交網路資料集（McAuley & Leskovec, 2012）。

# 載入社交網路資料
G_social = nx.read_edgelist(data_dir / 'mcauley2012' / 'facebook_combined.txt')

# 使用 Clauset-Newman-Moore 演算法進行社群偵測
communities = sorted(nx.community.greedy_modularity_communities(G_social), key=len, reverse=True)

# 設定節點和邊的社群屬性
set_node_community(G_social, communities)
set_edge_community(G_social)

# 視覺化社群結構
pos = nx.spring_layout(G_social, k=0.1)
external = [(v, w) for v, w in G_social.edges if G_social.edges[v, w]['community'] == 0]
internal = [(v, w) for v, w in G_social.edges if G_social.edges[v, w]['community'] > 0]
internal_color = [get_color(G_social.edges[e]['community']) for e in internal]

nx.draw_networkx(G_social, pos=pos, node_size=0, edgelist=external, edge_color="#333333", alpha=0.2, with_labels=False)
nx.draw_networkx(G_social, pos=pos, node_size=0, edgelist=internal, edge_color=internal_color, alpha=0.05, with_labels=False)

圖表翻譯：

此圖展示了線上社交網路的社群結構，不同顏色代表不同的社群。可以觀察到，該網路具有明顯的社群結構特徵。透過 Clauset-Newman-Moore 社群偵測演算法，能夠有效地識別出網路中的不同社群。

內容解密：

1. 使用 read_edgelist() 載入線上社交網路資料。
2. 同樣使用 greedy_modularity_communities() 進行社群偵測，並視覺化結果。
3. 圖中不同顏色代表不同的社群，內部邊和外部邊被區分顯示。

透過上述範例，可以看到 Clauset-Newman-Moore 社群偵測演算法在不同規模的網路中都能有效地識別出具有緊密連結的節點群組，為理解複雜網路結構提供了有力的工具。

社群分析：揭開網路結構的神秘面紗

在網路分析的世界中，社群（Communities）是一個非常重要的概念。社群是指一群彼此之間具有強烈連結的節點（Nodes），這些節點之間的連線比與其他社群的節點之間的連線更為緊密。在本章中，我們將探討社群分析的各種方法，包括 Girvan-Newman 演算法、派系（Cliques）和 K-核心（K-cores）。

Girvan-Newman 演算法：根據中介中心性的社群偵測

Girvan-Newman 演算法是一種根據中介中心性（Betweenness Centrality）的社群偵測方法。中介中心性是一種衡量節點或邊在網路中重要性的指標，它表示一個節點或邊在網路中的最短路徑上出現的頻率。Girvan-Newman 演算法透過移除中介中心性最高的邊來分割社群，直到每個節點都成為一個獨立的社群。

程式碼範例：使用 Girvan-Newman 演算法進行社群偵測

import networkx as nx
import community as nxcom

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

# 使用 Girvan-Newman 演算法進行社群偵測
result = nxcom.girvan_newman(G_karate)
communities = next(result)

# 設定節點和邊的社群屬性
set_node_community(G_karate, communities)
set_edge_community(G_karate)

# 視覺化社群
node_color = [get_color(G_karate.nodes[v]['community']) for v in G_karate.nodes()]
external = [(v, w) for v, w in G_karate.edges if G_karate.edges[v, w]['community'] == 0]
internal = [(v, w) for v, w in G_karate.edges if G_karate.edges[v, w]['community'] > 0]
internal_color = [get_color(G_karate.edges[e]['community']) for e in internal]

nx.draw_networkx(G_karate, pos=karate_pos, node_size=0, edgelist=external, edge_color="#333333", with_labels=False)
nx.draw_networkx(G_karate, pos=karate_pos, node_color=node_color, edgelist=internal, edge_color=internal_color)

內容解密：

1. 載入網路資料：使用 nx.karate_club_graph() 載入 Zachary 空手道俱樂部網路，這是一個經典的社會網路分析資料集。
2. Girvan-Newman 演算法應用：透過 nxcom.girvan_newman(G_karate) 進行社群偵測，並取得第一次迭代的結果。
3. 屬性設定：使用 set_node_community 和 set_edge_community 設定節點和邊的社群屬性。
4. 視覺化：根據社群屬性對節點和邊進行著色，並使用 nx.draw_networkx 進行視覺化。

派系（Cliques）：網路中的密集區域

派系是指一群彼此之間完全連線的節點。在網路中，派系往往代表著緊密的群體或團體。NetworkX 提供了 find_cliques 函式來尋找網路中的派系。

程式碼範例：尋找網路中的派系

cliques = list(nx.find_cliques(G_karate))
max_clique = max(cliques, key=len)

node_color = [(0.5, 0.5, 0.5) for v in G_karate.nodes()]
for i, v in enumerate(G_karate.nodes()):
    if v in max_clique:
        node_color[i] = (0.5, 0.5, 0.9)

nx.draw_networkx(G_karate, node_color=node_color, pos=karate_pos)

內容解密：

1. 尋找派系：使用 nx.find_cliques(G_karate) 尋找網路中的所有派系。
2. 找出最大派系：透過 max(cliques, key=len) 找出最大的派系。
3. 視覺化最大派系：將最大派系中的節點著色為藍色，並進行視覺化。

K-核心（K-cores）：網路中的密集核心

K-核心是指透過移除度數小於 k 的節點所得到的子圖。K-核心可以用來找出網路中的密集區域。

K-核心的應用

K-核心可以用於分析大型網路中的核心結構。透過調整 k 的值，可以控制核心的大小和密集程度。