網路社群偵測：Girvan-Newman演算法與視覺化實踐

– 9 分鐘閱讀

在複雜系統與數據科學領域，理解大型網路的拓撲結構是揭示其內在運作機制的關鍵。相較於單純的節點中心性或網路密度等宏觀指標，社群結構分析能更細緻地描繪出網路內部的子群體及其互動模式。本文將從理論與實踐兩個層面切入，首先闡述一種高效的視覺化策略，該策略透過區分不同層級的連結，將抽象的社群劃分結果轉化為直觀的視覺洞察。接著，將深入探討 Girvan-Newman 演算法，這是一種經典的分割式社群偵測方法，其核心在於利用邊介中心性來識別並移除跨社群的關鍵連結。透過結合演算法的嚴謹性與視覺化的直觀性，我們能更全面地掌握社交網路或知識圖譜中的隱藏模式。

大型線上社交網路社群結構的視覺化實踐

本章節將聚焦於大型線上社交網路的社群結構視覺化實踐。我們將運用先前定義的輔助函數與顏色映射，結合 NetworkX 的繪圖功能，來清晰地呈現偵測到的社群劃分，並分析社群之間的連接模式。

視覺化程式碼實踐：分層繪製

處理大型網路時，為了獲得清晰且有意義的視覺化結果，分層繪製策略至關重要。這有助於區分不同類型的連接，並突出社群結構的特徵。

  1. 準備邊列表：

    • 外部邊 (External Edges)：
      • 首先，我們需要從網路中分離出所有連接不同社群的邊。這些邊的 'community' 屬性被標記為 0。
      • 程式碼 external = [(v, w) for v, w in G_social.edges if G_social.edges[v, w]['community'] == 0] 創建了一個包含所有外部邊的列表。
    • 內部邊 (Internal Edges)：
      • 接著，我們分離出連接同一社群內節點的邊。這些邊的 'community' 屬性大於 0。
      • 程式碼 internal = [(v, w) for v, v in G_social.edges if G_social.edges[v, w]['community'] > 0] 創建了一個包含所有內部邊的列表。

  2. 準備內部邊的顏色：

    • 為了讓內部邊能夠反映其所屬社群的顏色，我們需要為每個內部邊生成對應的顏色。
    • internal_color = [get_color(G_social.edges[e]['community']) for e in internal] 這行程式碼遍歷所有內部邊 e，獲取其社群 ID，然後調用 get_color() 函數生成對應的顏色。

  3. 繪製圖形：

    • 繪製外部邊：
      • nx.draw_networkx(G_social, pos=pos, node_size=0, edgelist=external, edge_color="#333333", alpha=0.2, with_labels=False)
      • 此調用專門用於繪製外部邊。
        • 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)
      • 此調用繪製內部邊。
        • edgelist=internal 指定僅繪製內部邊。
        • edge_color=internal_color 使用先前生成的社群顏色列表，使內部邊的顏色與其所屬社群的節點顏色一致。
        • alpha=0.05 設定極低的透明度，因為內部邊數量龐大，過高的alpha值會導致顏色過於飽和，難以區分。
        • 同樣不繪製節點和標籤。

視覺化結果的意義

透過上述分層繪製的程式碼，我們將得到一張視覺化圖形，其中：

  • 灰色細線：代表連接不同社群的外部邊。它們稀疏地分佈在圖形中，顯示了社群之間的聯繫相對較弱。
  • 彩色粗線：代表社群內部的連接。這些邊會根據其所屬社群顯示出不同的顏色。由於內部邊的數量通常遠多於外部邊，這些彩色連接會形成更密集、更顯眼的區域，清晰地勾勒出各個社群的輪廓。

這種視覺化方式有效地突顯了網路的社群結構，使得觀察者能夠直觀地識別出不同的社群群集，以及它們之間的相對連接強度。

看圖說話：

此圖示總結了「大型線上社交網路社群結構的視覺化實踐」的內容，重點在於展示如何透過分層繪製和顏色編碼來視覺化大型網路的社群結構。流程開頭首先聚焦於「大型線上社交網路社群結構的視覺化實踐」，透過「分割」結構，詳細闡述了「準備邊列表」（區分了「外部邊」和「內部邊」），接著探討了「準備內部邊顏色」（說明了其「目的」和「方法」），並概述了「繪製圖形 (分層)」（描述了「繪製外部邊」和「繪製內部邊」的樣式），然後闡述了「視覺化結果的意義」（對比了「灰色細線」和「彩色粗線」的含義），最後以「總結與展望」作結，強調了「視覺化方法的價值」，並指出其「為後續網路分析提供基礎」。

Girvan-Newman 演算法：基於邊介中心性的社群偵測

本章節將介紹另一種重要的社群偵測演算法——Girvan-Newman 演算法。與先前討論的基於模組化最大化的方法不同，Girvan-Newman 演算法著重於網路的邊結構，特別是邊的「介中心性」(betweenness centrality)。

Girvan-Newman 演算法原理

  • 核心思想：
    • Girvan-Newman 演算法的核心在於識別並移除那些在連接不同社群中扮演關鍵角色的「橋樑」邊。
    • 它基於「邊介中心性」的概念。邊介中心性衡量一條邊在所有節點對之間最短路徑中所扮演的比例。
  • 演算法步驟：
    1. 計算邊介中心性：首先，計算網路中所有邊的介中心性。
    2. 移除最高介中心性邊：移除具有最高介中心性的邊。這條邊很可能連接了兩個不同的社群，移除它會增加節點對之間的路徑長度，或將路徑分割。
    3. 重複分割：重複步驟 1 和 2，不斷移除最高介中心性的邊。每次移除邊的過程都可能將現有的社群分割成更小的社群。
    4. 停止條件：
      • 這個過程可以持續進行，直到每個節點都自成一個社群。
      • 然而，通常我們會希望獲得一個特定數量的社群，或者使用一個品質度量（如模組化）來判斷何時停止，以找到一個較好的社群劃分。
  • 與模組化方法的對比：
    • Girvan-Newman 演算法是一種「由上而下」(top-down) 的方法，它從一個單一的網路開始，逐步將其分割。
    • Clauset-Newman-Moore (模組化最大化) 則是一種「由下而上」(bottom-up) 的方法，它從每個節點自成社群開始，逐步合併。

計算複雜度與適用性

  • 計算成本：
    • Girvan-Newman 演算法的一個顯著缺點是其計算成本較高。在每一步迭代中，都需要重新計算所有邊的介中心性。
    • 對於非常大的網路，這種重新計算會變得非常耗時，可能導致演算法難以應用。
  • 替代方案：
    • 在處理極大規模網路時，可能需要考慮其他更高效的社群偵測演算法，例如基於標籤傳播 (Label Propagation) 或其他近似方法。

NetworkX 中的實現

  • 函數：NetworkX 在 networkx.community 模組中提供了 girvan_newman() 函數來實現此演算法。
  • 輸出：
    • girvan_newman() 函數返回一個迭代器 (iterator)。
    • 這個迭代器會產生一系列的「分割」(partitions)，其中每個分割都是對前一個分割的進一步細化。
    • 例如，第一次調用 next(result) 會得到一個包含兩個社群的分割。

範例應用：Zachary 空手道網路

  • 執行：
    • result = nxcom.girvan_newman(G_karate)：對 Zachary 空手道網路執行 Girvan-Newman 演算法。
    • communities = next(result)：獲取迭代器產生的第一個分割，即將網路劃分為兩個社群。
    • len(communities)：輸出社群數量，結果為 2。
  • 後續步驟：
    • 與先前一樣，我們可以使用 set_node_community() 和 set_edge_community() 來為節點和邊設置社群屬性。
    • 然後，利用 get_color() 函數為節點和內部邊生成顏色，以便進行視覺化。
import networkx as nx
import networkx.community as nxcom
import matplotlib.pyplot as plt
import collections

# --- 創建 Zachary 空手道網路 ---
G_karate_demo = nx.karate_club_graph()

# --- Girvan-Newman 社群偵測 ---
print("--- 使用 Girvan-Newman 演算法偵測社群 ---")
try:
    # 執行 Girvan-Newman 演算法
    # 它返回一個迭代器，每次迭代都產生一個更細分的分割
    girvan_newman_iterator = nxcom.girvan_newman(G_karate_demo)

    # 獲取第一個分割 (通常是將網路劃分為兩個社群)
    communities_gn = next(girvan_newman_iterator)

    # 輸出社群數量
    num_communities_gn = len(communities_gn)
    print(f"Girvan-Newman 演算法第一次分割得到的社群數量: {num_communities_gn}")

    # 輸出每個社群的大小
    print("第一次分割的社群大小:")
    for i, comm in enumerate(communities_gn):
        print(f"  社群 {i+1}: {len(comm)} 個節點")

    # --- 視覺化輔助函數 (沿用前述定義) ---
    def set_node_community(G, communities_list):
        '''為節點添加 'community' 屬性'''
        if not communities_list: return
        for c, nodes_in_community in enumerate(communities_list):
            for node in nodes_in_community:
                G.nodes[node]['community'] = c + 1

    def set_edge_community(G):
        '''為社群內的邊添加 'community' 屬性'''
        for u, v in G.edges():
            if 'community' in G.nodes[u] and 'community' in G.nodes[v]:
                if G.nodes[u]['community'] == G.nodes[v]['community']:
                    G.edges[u, v]['community'] = G.nodes[u]['community']
                else:
                    G.edges[u, v]['community'] = 0 # 外部邊標記為 0
            else:
                pass

    def get_color(community_id, n_communities, low=0.1, high=0.9):
        if community_id == 0: return (0.5, 0.5, 0.5) # 灰色
        if n_communities <= 1: return (0.8, 0.2, 0.2)
        normalized_community_id = (community_id - 1) / (n_communities - 1)
        return plt.cm.viridis(normalized_community_id)

    # --- 設置節點和邊的社群屬性 ---
    print("\n--- 為節點和邊設置社群屬性 ---")
    set_node_community(G_karate_demo, communities_gn)
    set_edge_community(G_karate_demo)

    # --- 準備節點顏色 ---
    n_communities_gn = len(communities_gn)
    node_colors_gn = []
    for node in G_karate_demo.nodes():
        community_id = G_karate_demo.nodes[node].get('community', 0)
        node_colors_gn.append(get_color(community_id, n_communities_gn))

    # --- 準備邊列表與顏色 ---
    external_edges_gn = []
    internal_edges_gn = []
    internal_edge_colors_gn = []

    for u, v, d in G_karate_demo.edges(data=True):
        community_id = d.get('community', 0)
        if community_id == 0:
            external_edges_gn.append((u, v))
        else:
            internal_edges_gn.append((u, v))
            internal_edge_colors_gn.append(get_color(community_id, n_communities_gn))

    # --- 繪製社群結構圖 ---
    print("\n--- 繪製 Girvan-Newman 社群結構圖 ---")
    karate_pos = nx.spring_layout(G_karate_demo, seed=42, k=0.3) # 使用與之前一致的佈局

    plt.figure(figsize=(10, 8))

    # 繪製外部邊
    nx.draw_networkx(
        G_karate_demo, pos=karate_pos, node_size=0,
        edgelist=external_edges_gn, edge_color="#333333", width=0.5, alpha=0.4, style='dashed'
    )

    # 繪製節點和內部邊
    nx.draw_networkx(
        G_karate_demo, pos=karate_pos,
        node_color=node_colors_gn, node_size=300, alpha=0.9,
        edgelist=internal_edges_gn, edge_color=internal_edge_colors_gn, width=1.5, alpha=0.7
    )

    nx.draw_networkx_labels(G_karate_demo, karate_pos, font_size=10, font_weight='bold')

    plt.title("Zachary Karate Club Network - Girvan-Newman Communities (First Partition)", fontsize=16)
    plt.axis('off')
    plt.show()

except Exception as e:
    print(f"執行 Girvan-Newman 社群偵測或視覺化時發生錯誤: {e}")

@startuml
!define DISABLE_LINK
!define PLANTUML_FORMAT svg
!theme _none_

skinparam dpi auto
skinparam shadowing false
skinparam linetype ortho
skinparam roundcorner 5
skinparam defaultFontName "Microsoft JhengHei UI"
skinparam defaultFontSize 16
skinparam minClassWidth 100

start

:Girvan-Newman 演算法：基於邊介中心性的社群偵測;
split
:演算法原理;
note right
核心思想: 移除連接社群的「橋樑」邊
基於: 邊介中心性 (Betweenness Centrality)
演算法步驟:
  1. 計算邊介中心性
  2. 移除最高介中心性邊
  3. 重複分割
  4. 停止條件 (社群數或品質度量)
end note
split again
:計算複雜度與適用性;
note right
計算成本高: 每步需重算介中心性
適用性: 對大型網路可能不適用
替代方案: 標籤傳播等高效演算法
end note
split again
:NetworkX 中的實現;
note right
函數: nxcom.girvan_newman()
輸出: 迭代器 (partitions)
範例: 第一次分割為兩個社群
end note
end split

:範例應用 (Zachary 空手道網路);
note right
執行步驟:
  - 調用 girvan_newman()
  - 獲取 next(result)
  - 設置節點/邊屬性
  - 準備顏色
  - 視覺化
結果: 2 個社群
end note

:總結與展望;
note right
Girvan-Newman 的優勢與劣勢
與其他演算法的比較
為後續網路結構分析做鋪墊
end note

stop

@enduml

看圖說話：

此圖示總結了「Girvan-Newman 演算法：基於邊介中心性的社群偵測」的內容，重點在於介紹 Girvan-Newman 演算法的原理、計算複雜度、在 NetworkX 中的實現，以及透過 Zachary 空手道網路的範例進行應用。流程開頭首先聚焦於「Girvan-Newman 演算法：基於邊介中心性的社群偵測」，透過「分割」結構，詳細闡述了「演算法原理」（說明了「核心思想」，基於「邊介中心性」，並列舉了「演算法步驟」和「停止條件」），接著探討了「計算複雜度與適用性」（指出了「計算成本高」，並提到了「替代方案」），並說明了「NetworkX 中的實現」（介紹了「函數」和「輸出」），最後以「範例應用 (Zachary 空手道網路)」作結，概述了「執行步驟」和「結果」。

好的，這是一篇為上述關於「網路社群結構視覺化與演算法」的技術文章所撰寫的，符合「玄貓風格」的結論。

結論

縱觀現代管理者的多元挑戰，這兩種網路社群分析方法——分層視覺化與 Girvan-Newman 演算法——分別代表了洞察複雜系統的兩種關鍵視角：前者追求「詮釋效率」，後者則側重「分析深度」。分層視覺化以其直觀性，讓管理者能迅速捕捉社群結構的宏觀輪廓與密度分佈；而 Girvan-Newman 演算法則透過移除網路的「結構應力點」，揭示了社群形成與分離的深層邏輯。

對高階經理人而言，真正的挑戰並非在兩者間做出技術性取捨，而是如何策略性地整合運用。在實務中，快速的模組化方法搭配分層視覺化，可用於日常的市場格局或組織健康度監測；而計算成本高昂的 Girvan-Newman 演算法，則更適合應用於併購整合、關鍵人才流失風險評估等需要深度結構拆解的重大決策場景。這體現了在有限的分析資源下，如何將其投入在最具價值的策略問題上。

展望未來，我們預見分析工具將朝向「混合式框架」發展，讓使用者能無縫切換不同演算法視角。然而，工具的進化並不能取代決策者的判斷力。玄貓認為，高階管理者真正的核心能力，應從鑽研技術細節轉向培養「網路識讀力」（Network Literacy）——即從複雜的視覺化圖形與數據中，精準提煉出攸關策略成敗的商業洞見，這才是駕馭數據時代的根本之道。

玄貓

玄貓

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