圖論演算法：社群偵測與中心性分析實作探討

– 14 分鐘閱讀

圖論演算法在分析複雜網路結構和節點關係中扮演著至關重要的角色。本文將深入探討社群偵測和中心性分析這兩種關鍵技術，並結合 Python 和 NetworkX 函式庫進行實作演示。社群偵測旨在識別網路中緊密連線的節點群體，而中心性分析則用於評估節點在網路中的重要性。我們將以莎士比亞的《仲夏夜之夢》角色關係圖和一個簡單的社交網路為例，分別應用 Louvain 方法進行社群偵測、計算模組度和特徵向量中心性等指標，並輔以程式碼和圖表說明，幫助讀者更好地理解這些技術的應用和實作細節。

頂點連線性

給定一個圖 $G = (V, E)$，其中 $V$ 是頂點集，$E$ 是邊集。圖的鄰接矩陣 $A$ 是一個 $|V| \times |V|$ 的矩陣， 其中 $A_{ij} = 1$ 如果頂點 $i$ 和 $j$ 之間有一條邊，否則 $A_{ij} = 0$。

矩陣運算

現在，讓我們考慮以下矩陣運算：

$$ \sum_{k=1}^{|V|} \left( \frac{1}{2} \cdot \left( v_i^{(k)} \cdot v_j^{(k)} \right) \right) \cdot \delta(c(v_i), c(v_j)) $$

其中 $v_i^{(k)}$ 和 $v_j^{(k)}$ 分別是頂點 $i$ 和 $j$ 的 $k$ 次方鄰接矩陣的元素，$\delta(c(v_i), c(v_j))$ 是克羅內克爾函式，如果頂點 $i$ 和 $j$ 的顏色相同則傳回 1，否則傳回 0。

圖表翻譯

此圖表示瞭如何使用矩陣運算來計算圖中頂點之間的連線性。圖中，頂點 $i$ 和 $j$ 之間的連線性是透過計算其鄰接矩陣的元素之積來得到的。然後，透過對所有頂點進行求和，得到圖中頂點之間的總連線性。

程式碼實作

以下是使用 Python 實作上述矩陣運算的程式碼：

import numpy as np

def calculate_connectivity(graph):
    """
    計算圖中頂點之間的連線性
    """
    # 取得圖的鄰接矩陣
    adjacency_matrix = np.array(graph)

    # 初始化連線性矩陣
    connectivity_matrix = np.zeros((len(graph), len(graph)))

    # 進行矩陣運算
    for k in range(len(graph)):
        for i in range(len(graph)):
            for j in range(len(graph)):
                connectivity_matrix[i, j] += 0.5 * (adjacency_matrix[i, k] * adjacency_matrix[j, k])

    return connectivity_matrix

# 範例使用
graph = [[0, 1, 0], [1, 0, 1], [0, 1, 0]]
connectivity_matrix = calculate_connectivity(graph)
print(connectivity_matrix)

內容解密

上述程式碼實作瞭如何使用矩陣運算來計算圖中頂點之間的連線性。首先，取得圖的鄰接矩陣，然後初始化連線性矩陣。接著，進行矩陣運算，計算頂點之間的連線性。最終，傳回連線性矩陣。

此外，還可以使用其他矩陣運算來分析圖的結構和性質，例如計算圖的 Laplacian 矩陣、度矩陣等。這些矩陣運算可以幫助我們更深入地瞭解圖的性質和行為。

社群網路分析中的模組度

模組度（Modularity）是一個用於衡量社群網路中社群結構的指標。它的值域在[-1/2, 1]之間，表示網路中社群的相似度和差異度。

模組度的優點

模組度有一些優點，例如：

  • 它不受網路大小的影響
  • 它對社群結構的變化很敏感

模組度的計算

模組度的計算公式如下：

$$Q = \frac{1}{2m} \sum_{i,j} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(c_i, c_j)$$

其中，$A_{ij}$是網路的鄰接矩陣，$k_i$和$k_j$是節點$i$和$j$的度，$c_i$和$c_j$是節點$i$和$j$的社群標籤，$\delta(c_i, c_j)$是Kronecker delta函式。

模組度的應用

模組度可以用於社群網路的分析和視覺化。例如，透過計算網路的模組度，可以判斷網路中是否存在明顯的社群結構。

Python實作

以下是使用Python和NetworkX函式庫計算模組度的程式碼：

import networkx as nx

# 建立一個空網路
G = nx.Graph()

# 新增節點和邊
for i in range(9):
    G.add_node(i+1)
# ...

# 計算模組度
Q = nx.modularity(G, [1, 1, 1, 2, 2, 2, 3, 3, 3])
print(Q)

圖表翻譯

此圖示社群網路中模組度的變化。隨著網路中社群結構的變化，模組度的值也會變化。這個圖表展示了模組度如何反映社群網路中的社群結構。

圖表翻譯：模組度的變化

此圖表展示了模組度的變化。隨著網路中社群結構的變化，模組度的值也會變化。這個圖表展示了模組度如何反映社群網路中的社群結構。

  flowchart TD
    A[社群網路] --> B[模組度計算]
    B --> C[模組度值]
    C --> D[社群結構變化]
    D --> E[模組度變化]
    E --> F[社群網路分析]

內容解密：模組度的計算

模組度的計算公式如下：

$$Q = \frac{1}{2m} \sum_{i,j} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(c_i, c_j)$$

其中，$A_{ij}$是網路的鄰接矩陣，$k_i$和$k_j$是節點$i$和$j$的度，$c_i$和$c_j$是節點$i$和$j$的社群標籤，$\delta(c_i, c_j)$是Kronecker delta函式。

import networkx as nx

# 建立一個空網路
G = nx.Graph()

# 新增節點和邊
for i in range(9):
    G.add_node(i+1)
# ...

# 計算模組度
Q = nx.modularity(G, [1, 1, 1, 2, 2, 2, 3, 3, 3])
print(Q)

社群偵測技術

社群偵測是一種重要的圖形分析技術，旨在識別圖形中的社群結構。這種技術在各個領域都有廣泛的應用，包括社交網路分析、生物網路分析和推薦系統等。

Louvain 方法

Louvain 方法是一種快速且高效的社群偵測演算法，特別適合於大型圖形的分析。這種方法使用了一種迭代的方式來最大化模度（modularity），模度是一個衡量圖形社群結構的指標。Louvain 方法的核心思想是透過多次迭代的模度最大化和圖形收縮來減少計算量。

模度最大化

模度最大化是一個重要的步驟，在 Louvain 方法中，它是透過多次迭代來實作的。在每次迭代中，演算法會嘗試將圖形中的頂點分配到不同的社群中，以最大化模度。模度的計算公式如下：

𝑄 = 1/2𝑚 * ∑(𝑒𝑖𝑗 - 𝑔𝑖𝑗) / 2𝑚

其中，𝑄 是模度，𝑚 是圖形中的邊數，𝑒𝑖𝑗 是社群 𝑖 和社群 𝑗 之間的邊數，𝑔𝑖𝑗 是社群 𝑖 和社群 𝑗 之間的預期邊數。

圖形收縮

圖形收縮是一個重要的步驟，在 Louvain 方法中，它是透過將一個社群中的所有頂點合併為一個單一的頂點來實作的。這個過程可以大大減少圖形的大小，從而減少計算量。

實作

以下是使用 Python 和 NetworkX 實作 Louvain 方法的例子：

import networkx as nx
import community

# 建立一個圖形
G = nx.Graph()
G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (5, 6), (4, 6), (6, 7), (7, 8), (8, 9), (7, 9)])

# 使用 Louvain 方法進行社群偵測
partition = community.best_partition(G)

# 取得社群結構
communities = {}
for node, community_id in partition.items():
    if community_id not in communities:
        communities[community_id] = []
    communities[community_id].append(node)

# 列印社群結構
for community_id, nodes in communities.items():
    print(f"社群 {community_id}: {nodes}")

# 計算模度
modularity = community.modularity(partition, G)
print(f"模度: {modularity}")

這個例子中，我們建立了一個圖形，然後使用 Louvain 方法進行社群偵測。最後，我們列印預出了社群結構和模度。

圖解矩陣運算

在圖論中，我們常常需要處理圖的結構和屬性。給定一個圖 $G = (V, E)$，其中 $V$ 是節點集合，$E$ 是邊集合。對於任意兩個節點 $v_i$ 和 $v_j$，我們可以定義一個矩陣 $A_{i, j}$，其元素代表了節點 $v_i$ 和 $v_j$ 之間的連線強度或權重。

矩陣元素的計算

矩陣 $A_{i, j}$ 的元素可以透過以下公式計算：

$$ A_{i, j} = \frac{k(v_i) \cdot k(v_j)}{2m} \cdot \delta(c(v_i), c(v_j)) $$

其中，$k(v_i)$ 和 $k(v_j)$ 分別代表節點 $v_i$ 和 $v_j$ 的度，$m$ 是圖中的邊數，$c(v_i)$ 和 $c(v_j)$ 分別代表節點 $v_i$ 和 $v_j$ 的顏色或類別，$\delta(c(v_i), c(v_j))$ 是克羅內克爾函式，當 $c(v_i) = c(v_j)$ 時傳回 1，否則傳回 0。

克羅內克爾函式

克羅內克爾函式 $\delta(x, y)$ 是一個二元函式，當 $x = y$ 時傳回 1，否則傳回 0。它常用於表示兩個變數是否相等。

節點度和邊數

節點度 $k(v_i)$ 是節點 $v_i$ 的鄰居數，邊數 $m$ 是圖中的邊數。這兩個引數對於計算矩陣元素至關重要。

矩陣的應用

矩陣 $A_{i, j}$ 可以用於圖的聚類、分群和推薦系統等應用。透過分析矩陣的元素，可以得出節點之間的連線強度和相似度，從而實作圖的分割和聚類。

內容解密：

以上內容介紹了圖論中的一個重要概念：矩陣運算。透過定義矩陣 $A_{i, j}$，我們可以計算節點之間的連線強度和相似度。矩陣的元素可以透過節點度、邊數和克羅內克爾函式計算得到。這個矩陣可以用於圖的聚類、分群和推薦系統等應用。

import numpy as np

def calculate_matrix(graph):
    """
    計算圖的矩陣
    """
    num_nodes = len(graph)
    matrix = np.zeros((num_nodes, num_nodes))
    
    for i in range(num_nodes):
        for j in range(num_nodes):
            # 計算節點度和邊數
            degree_i = len(graph[i])
            degree_j = len(graph[j])
            num_edges = len(graph)
            
            # 計算克羅內克爾函式
            delta = 1 if graph[i] == graph[j] else 0
            
            # 計算矩陣元素
            matrix[i, j] = (degree_i * degree_j) / (2 * num_edges) * delta
    
    return matrix

# 範例使用
graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}

matrix = calculate_matrix(graph)
print(matrix)

圖表翻譯：

此圖示了矩陣運算的過程。節點之間的連線強度和相似度可以透過矩陣元素計算得到。矩陣的元素可以用於圖的聚類、分群和推薦系統等應用。

  flowchart TD
    A[節點] --> B[節點度]
    B --> C[邊數]
    C --> D[克羅內克爾函式]
    D --> E[矩陣元素]
    E --> F[圖的聚類]
    F --> G[圖的分群]
    G --> H[推薦系統]

圖表翻譯：

此圖示了矩陣運算的過程和其應用。節點之間的連線強度和相似度可以透過矩陣元素計算得到。矩陣的元素可以用於圖的聚類、分群和推薦系統等應用。

社群偵測與圖表分析

社群偵測是一種用於識別圖表中社群或群體的技術。社群是一組節點，它們之間的連線比與社群外的節點更密集。在這個例子中，我們使用了Louvain方法來對莎士比亞的《仲夏夜之夢》中的角色進行社群偵測。

Louvain方法

Louvain方法是一種根據模組性的社群偵測演算法。模組性是一個衡量圖表中社群結構的指標。Louvain方法透過遞迴地合併社群來最大化模組性。

import networkx as nx
import community

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

# 載入圖表資料
# ...

# 執行Louvain方法
partitions = community.best_partition(G, weight='weight')

# 列印社群分佈
for node, community_id in partitions.items():
    print(f"節點 {node} 屬於社群 {community_id}")

社群分析

透過Louvain方法，我們可以得到每個節點所屬的社群。然後，我們可以對社群進行分析，例如計算社群的大小、密度等指標。

# 計算社群大小
community_sizes = {}
for community_id in set(partitions.values()):
    community_sizes[community_id] = sum(1 for node, id in partitions.items() if id == community_id)

# 列印社群大小
for community_id, size in community_sizes.items():
    print(f"社群 {community_id} 的大小為 {size}")

圖表視覺化

我們可以使用圖表視覺化工具來展示社群結構。例如，我們可以使用不同的顏色來表示不同的社群。

  graph LR
    A[節點 A] --> B[節點 B]
    B --> C[節點 C]
    C --> D[節點 D]
    D --> A
    E[節點 E] --> F[節點 F]
    F --> G[節點 G]
    G --> H[節點 H]
    H --> E
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style B fill:#f9f,stroke:#333,stroke-width:2px
    style C fill:#f9f,stroke:#333,stroke-width:2px
    style D fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#ccf,stroke:#333,stroke-width:2px
    style F fill:#ccf,stroke:#333,stroke-width:2px
    style G fill:#ccf,stroke:#333,stroke-width:2px
    style H fill:#ccf,stroke:#333,stroke-width:2px

圖表翻譯：

這個圖表展示了兩個社群。左邊的社群由節點 A、B、C 和 D 組成，右邊的社群由節點 E、F、G 和 H 組成。每個社群的節點之間都有連線，表示它們之間的密切關係。不同的顏色表示不同的社群。

圖表分析：《仲夏夜之夢》的角色共同出場關係

在《仲夏夜之夢》的角色共同出場關係圖（Fig. 8.9）中，我們可以看到不同角色之間的關係。圖中使用不同的顏色來代表不同的角色群體，包括貴族（藍色）、仙女（紅色）、機械師（青色）和劇中劇的角色（洋紅色）。

角色群體分析

  • 貴族（藍色）：在圖中，我們可以看到貴族角色之間的關係非常密切，尤其是「地獄四人組」（Lysander、Hermia、Demetrius和Helena）之間的關係非常緊密。
  • 機械師（青色）：機械師角色群體位於圖的左上角，他們之間的關係也非常密切。
  • 仙女（紅色）：仙女角色群體位於圖的中間，除了泰坦妮亞（Titania）外，其他仙女角色之間的關係也非常密切。
  • 劇中劇的角色（洋紅色）：劇中劇的角色群體位於圖的右下角，他們之間的關係也非常密切。

角色關係分析

  • 波頓（Bottom）：波頓是一個特殊的角色，他雖然屬於機械師群體，但在圖中被放在仙女群體中，因為他是被泰坦妮亞（Titania）所愛上的角色。
  • 伊吉斯（Egeus）：伊吉斯是一個孤立的角色，他只出現在特定的場景中，並且只與貴族和波頓有關係。
圖表翻譯：
  graph LR
    A[貴族] --> B[機械師]
    A --> C[仙女]
    B --> D[劇中劇的角色]
    C --> D
    E[波頓] -.-> C
    F[伊吉斯] -.-> A
    F -.-> E

圖表翻譯：圖表顯示了《仲夏夜之夢》中不同角色之間的關係，包括貴族、機械師、仙女和劇中劇的角色。波頓是一個特殊的角色，他雖然屬於機械師群體，但在圖中被放在仙女群體中。伊吉斯是一個孤立的角色，他只出現在特定的場景中，並且只與貴族和波頓有關係。

8.4.1.2 在《仲夏夜之夢》中角色雙重演出

在戲劇史上，「角色雙重演出」一詞指的是一位演員在同一部作品中扮演兩個或以上的角色。莎士比亞的角色雙重演出已被廣泛研究。佈雷特·加博亞（Brett Gamboa）甚至專門撰寫了一本章《莎士比亞的雙重劇》（Shakespeare’s Double Plays）[9]，在第139頁，他列出了《仲夏夜之夢》中角色雙重演出的清單，我們在清單中增加了（以斜體表示）機械師和西斯貝演員之間的對應關係，如《仲夏夜之夢》中所述：

奧伯龍 = 西斯

泰坦妮亞 = 伊波利塔

普克 = 菲洛斯特拉特

萊桑德

德米特里斯

波頓 = 皮拉莫斯

赫米亞 = 斯納格 = 蠶 = 獅子

海倫娜 = 弗魯特 = 西斯貝

斯塔弗林 = 科布韋伯 = 月光

斯諾特 = 芥子 = 牆

伊吉斯 = 豌豆花 = 昆斯 = 序言

我們採用了共存圖，並根據機械師和西斯貝演員之間的對應關係合併節點。合併後，我們的圖表具有21個節點和151條邊（而不是之前的172條邊）。舞臺上角色共存的問題與圖形著色問題相似。在這個問題中，我們尋找最少的頂點顏色，使得邊總是連線不同顏色的頂點。這被稱為圖的色彩數。演算法很簡單：在定義顏色順序後，一個一個地取頂點，並為其分配與其鄰居顏色不同的最小顏色。由於這取決於順序，因此我們重複執行演算法（我們執行了100,000次）以隨機選擇的頂點順序。這樣做，我們發現需要13位演員來扮演所有角色，具體如下：

奧伯龍 = 昆斯 = 序言

泰坦妮亞 = 菲洛斯特拉特

普克 = 西斯

內容解密：

上述內容解釋了《仲夏夜之夢》中角色雙重演出的概念，並列出了角色之間的對應關係。透過合併節點和執行演算法，我們發現需要13位演員來扮演所有角色。這個過程涉及圖形著色問題的解決，目的是找到最少的頂點顏色，使得邊總是連線不同顏色的頂點。

圖表翻譯：

此圖表示了《仲夏夜之夢》中角色雙重演出的過程。圖表左側列出了角色，右側列出了對應的角色。圖表中間的箭頭表示角色之間的對應關係。透過這個圖表，我們可以清晰地看到角色之間的對應關係，並瞭解需要多少位演員來扮演所有角色。

  graph LR
    A[奧伯龍] --> B[昆斯]
    A --> C[序言]
    D[泰坦妮亞] --> E[菲洛斯特拉特]
    F[普克] --> G[西斯]
    H[萊桑德] --> H
    I[德米特里斯] --> I
    J[波頓] --> K[皮拉莫斯]
    L[赫米亞] --> M[斯納格]
    L --> N[蠶]
    L --> O[獅子]
    P[海倫娜] --> Q[弗魯特]
    P --> R[西斯貝]
    S[斯塔弗林] --> T[科布韋伯]
    S --> U[月光]
    V[斯諾特] --> W[芥子]
    V --> X[牆]
    Y[伊吉斯] --> Z[豌豆花]
    Y --> AA[昆斯]
    Y --> AB[序言]

社群偵測

社群偵測是一種用於識別複雜網路中社群結構的技術。在《仲夏夜之夢》中，我們可以使用社群偵測來分析角色之間的互動關係。

角色關係圖

我們可以將角色之間的互動關係表示為一個圖，圖中的節點代表角色，邊代表角色之間的互動關係。這個圖可以幫助我們瞭解角色之間的社群結構。

中心性分析

中心性分析是一種用於評估節點在圖中重要性的方法。在《仲夏夜之夢》中，我們可以使用中心性分析來評估角色在社群中的重要性。

特徵向量中心性

特徵向量中心性是一種中心性分析方法，根據節點的特徵向量來評估節點的重要性。在《仲夏夜之夢》中，特徵向量中心性分析顯示，四個最重要的角色是兩對情侶：Lysander/Hermia和Demetrius/Helena。這四個角色有相同的中心性值，表示他們在社群中的重要性相同。

和諧距離中心性

和諧距離中心性是一種中心性分析方法，根據節點之間的距離來評估節點的重要性。在《仲夏夜之夢》中，和諧距離中心性分析顯示，角色之間的距離與他們的互動關係相關。

社群偵測結果

社群偵測結果顯示，《仲夏夜之夢》中的角色可以分為幾個社群。這些社群包括：

  • 兩對情侶：Lysander/Hermia和Demetrius/Helena
  • 演員：Bottom、Flute、Snout和Snug
  • 精靈：Titania、Puck和其他精靈
  • 機械師：Egeus和其他機械師

這些社群結構可以幫助我們瞭解《仲夏夜之夢》中的角色關係和互動模式。

社交網路分析中的 Eigenvector Centrality

在社交網路分析中，Eigenvector Centrality是一種用於衡量節點（node）重要性的指標。它不僅考慮了節點的直接鄰居，也考慮了鄰居的鄰居，從而對節點的影響力進行更全面的評估。

Eigenvector Centrality 的計算

Eigenvector Centrality 的計算根據矩陣運算，具體來說，它是透過對網路的鄰接矩陣進行特徵分解來得到的。鄰接矩陣是一個二元矩陣，其中的元素表示兩個節點是否直接相連。

範例計算

假設我們有一個簡單的社交網路，包含 5 個節點（A、B、C、D、E），且有以下連結：

  • A 與 B、C 相連
  • B 與 A、D 相連
  • C 與 A、E 相連
  • D 與 B 相連
  • E 與 C 相連

首先，構建鄰接矩陣：

import numpy as np

# 鄰接矩陣
adj_matrix = np.array([
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0]
])

接著，計算 Eigenvector Centrality：

from numpy import linalg as LA

# 計算特徵值和特徵向量
eigenvalues, eigenvectors = LA.eig(adj_matrix)

# 找到最大實特徵值對應的特徵向量
max_eigenvalue_index = np.argmax(eigenvalues)
eigenvector = np.real(eigenvectors[:, max_eigenvalue_index])

# Eigenvector Centrality
eigenvector_centrality = eigenvector / np.sum(eigenvector)

Eigenvector Centrality 的應用

Eigenvector Centrality 在社交網路分析中的應用包括：

  • 影響力評估：透過計算每個節點的 Eigenvector Centrality，可以評估其在社交網路中的影響力。
  • 推薦系統：Eigenvector Centrality 可以用於推薦系統中，找出最有影響力的使用者或節點。
  • 病毒傳播：在研究病毒或資訊在社交網路中的傳播時，Eigenvector Centrality 可以幫助找出最容易感染或傳播資訊的節點。

內容解密：

上述程式碼展示瞭如何計算 Eigenvector Centrality。首先，構建社交網路的鄰接矩陣，然後計算其特徵值和特徵向量。找到最大實特徵值對應的特徵向量，即可得到 Eigenvector Centrality。

從技術架構視角來看，利用圖形分析技術，特別是社群偵測和中心性分析，能有效地揭示複雜網路的底層結構和關鍵節點。本文深入探討了Louvain方法、模組度最大化、特徵向量中心性以及和諧距離中心性等核心技術，並以莎士比亞的《仲夏夜之夢》角色關係及雙重演出為例，展示了這些技術在實際應用中的價值。然而，目前的分析主要集中在角色的共現關係，尚未考慮到劇情發展的時間順序和角色互動的語義資訊，這也限制了分析的深度。展望未來，整合動態網路分析和自然語言處理技術，將能更精確地捕捉角色關係的演變和角色的影響力，進一步提升圖形分析在文學研究和社交網路分析領域的應用價值。玄貓認為，隨著圖形資料函式庫和圖形計算引擎的快速發展，圖形分析技術將在更多領域展現其強大的分析能力，值得密切關注。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。