圖結構使用 Louvain 社區檢測算法進行分組

flyfish

Louvain 算法是一種基于模塊度最大化的社區檢測算法，核心目標是在復雜網絡中找到“內部連接緊密、外部連接稀疏”的社區結構。它的優勢在于高效性（可處理百萬級節點的大規模網絡）和近似最優解，通過“局部優化→社區聚合”的迭代流程實現模塊度的逐步提升，最終得到穩定的社區劃分。

一、目標：最大化“模塊度（Modularity, Q）”

要理解 Louvain 算法，首先必須明確其優化目標——模塊度 Q。模塊度是衡量“社區劃分質量”的量化指標，它描述了“網絡實際社區內的邊密度”與“隨機網絡中相同社區內的邊密度”的差異：

• 若 Q > 0：實際社區內邊更密集，劃分有效；
• Q 越大（最大值約 0.7）：社區結構越顯著。

1. 模塊度 Q 的數學定義（無向無權網絡）

對于無向無權網絡，模塊度公式表示為：
$$Q=\frac{1}{2m}\sum _{i,j}\left(A_{ij}?\frac{k_i{k}_j}{2m}\right)\delta (c_i,c_j)$$

各符號含義：

符號	含義解釋
$A_{ij}$	網絡的鄰接矩陣元素：若節點 $i$ 和 $j$ 之間有邊，$A_{ij}=1$；否則 $A_{ij}=0$。
$k_i$	節點 $i$ 的度（即與節點 $i$ 直接相連的邊數）。
$m$	網絡的總邊數（$m=\frac{1}{2}{\sum }_{i,j}{A}_{ij}$，無向圖邊計數不重復）。
$c_i$	節點 $i$ 所屬的社區標簽（如 $c_i=0$ 表示節點 $i$ 在社區 0 中）。
$\delta (x,y)$	克羅內克函數：若 $x=y$（節點 $i$ 和 $j$ 同屬一個社區），$\delta =1$；否則 $\delta =0$。

2. 模塊度變化量 ΔQ：節點移動的判斷依據

Louvain 算法不直接計算全局 Q，而是通過局部模塊度變化量 ΔQ 決定節點的移動——即“將某個節點 $u$ 從當前社區移動到相鄰節點 $v$ 的社區后，模塊度的變化值”。只有當 ΔQ > 0 時，移動才會提升全局模塊度，才會執行。

節點 $u$ 移動到社區 $C$ 的 ΔQ 公式（簡化版，核心邏輯）：
$$\Delta Q=\left(\frac{{\sum }_{in}+k_{u,C}}{2m}?{\left(\frac{{\sum }_{tot}+k_u}{2m}\right)}^2\right)?\left(\frac{{\sum }_{in}}{2m}?{\left(\frac{{\sum }_{tot}}{2m}\right)}^2?{\left(\frac{k_u}{2m}\right)}^2\right)$$

各符號含義（聚焦局部社區 $C$ 和節點 $u$）：

符號	含義解釋
${\sum }_{in}$	社區 $C$ 內部所有邊的總權重（無權網絡中即邊數）。
$k_{u,C}$	節點 $u$ 與社區 $C$ 內所有節點之間的邊的總權重（即 $u$ 到 $C$ 的“連接強度”）。
${\sum }_{tot}$	社區 $C$ 內所有節點的度的總和（即社區 $C$ 與外部節點連接的“總能力”）。
$k_u$	節點 $u$ 的總度（同前）。

二、Louvain 算法的核心流程：兩階段迭代

Louvain 算法通過反復執行兩個階段，逐步聚合社區、提升模塊度，直到模塊度無法再優化為止。整個過程是“自下而上”的社區合并（從每個節點單獨為一個社區，到最終聚合為少數幾個大社區）。

階段 1：局部移動（Local Moving Phase）—— 優化單個節點的社區歸屬

目標：對每個節點單獨調整社區，最大化局部 ΔQ，直到網絡中所有節點都無法通過移動提升模塊度。
具體步驟：

1. 初始狀態：將網絡中每個節點都視為一個獨立的社區（即初始社區數 = 節點數）。
2. 遍歷節點：按隨機順序（或固定順序）遍歷每個節點 $u$。
3. 嘗試移動：對節點 $u$ 的每個相鄰節點 $v$（即與 $u$ 有邊相連的節點），計算“將 $u$ 移動到 $v$ 所屬社區 $C$”的 ΔQ。
4. 選擇最優移動：
   • 若所有 ΔQ 均 ≤ 0：節點 $u$ 保持在原社區；
   • 若存在 ΔQ > 0：選擇 ΔQ 最大的社區，將 $u$ 移動過去。
5. 重復迭代：重復步驟 2-4，直到遍歷所有節點后，沒有任何節點的移動能提升模塊度（此階段終止）。

階段 2：社區聚合（Community Aggregation Phase）—— 構建“超級節點”網絡

目標：將階段 1 得到的每個社區，聚合為一個“超級節點”，縮小網絡規模，為下一輪迭代做準備。
具體步驟：

1. 創建超級節點：每個社區對應一個新的“超級節點”（例如，社區 0 聚合為超級節點 $C_0$，社區 1 聚合為 $C_1$ 等）。
2. 計算超級節點間的邊權重：
   • 若原網絡中，社區 $C_a$ 的節點與社區 $C_b$ 的節點之間有 $w$ 條邊（無權網絡中 $w$ 是邊數，加權網絡中 $w$ 是邊權重總和），則在新網絡中，超級節點 $C_a$ 與 $C_b$ 之間添加一條權重為 $w$ 的邊。
   • 注意：社區內部的邊（同一社區節點間的邊）會被“折疊”到超級節點內部，不計入超級節點間的邊（因為后續迭代只關注社區間的連接）。
3. 生成新網絡：新網絡的節點是超級節點，邊是超級節點間的聚合邊權重，網絡規模大幅縮小。

迭代終止條件

將階段 2 生成的新網絡，再次代入階段 1（局部移動） 和階段 2（社區聚合），反復迭代。直到某一輪迭代后，模塊度不再提升（即階段 1 無法通過移動節點優化 ΔQ，階段 2 也無法生成更優的超級節點網絡），算法終止。

import networkx as nx
import community as community_louvain
import matplotlib.pyplot as plt
import matplotlib.colors as mcolors# 設置中文字體
plt.rcParams["font.family"] = ["SimHei"]  # Windows系統# 1. 構建水果相關的有向無環圖（DAG）
G = nx.DiGraph()# 添加節點
nodes = ["蘋果", "香蕉", "橙子", "草莓",  # 水果"紅色", "黃色", "橙色", "甜味", "酸味",  # 屬性"顏色", "味道", "漿果", "核果"  # 類別
]
G.add_nodes_from(nodes)# 添加有向邊（確保無環）
edges = [("蘋果", "紅色"), ("蘋果", "甜味"), ("蘋果", "核果"),("香蕉", "黃色"), ("香蕉", "甜味"),("橙子", "橙色"), ("橙子", "酸味"),("草莓", "紅色"), ("草莓", "甜味"), ("草莓", "漿果"),("紅色", "顏色"), ("黃色", "顏色"), ("橙色", "顏色"),("甜味", "味道"), ("酸味", "味道")
]
G.add_edges_from(edges)# 可視化原始有向圖
plt.figure(figsize=(10, 6))
pos = nx.spring_layout(G, seed=42)
# 原始圖使用紅色系為主的顏色
nx.draw_networkx_nodes(G, pos, node_size=800, node_color='lightcoral')
nx.draw_networkx_labels(G, pos, font_size=12, font_family=plt.rcParams["font.family"], font_color='white')
nx.draw_networkx_edges(G, pos, arrowstyle="->", arrowsize=10)
plt.title("水果相關的有向無環圖（DAG）")
plt.show()# 2. 轉換為無向圖以適配Louvain算法
G_undirected = G.to_undirected()# 3. 計算社區劃分
partition = community_louvain.best_partition(G_undirected)# 輸出分組結果
print("社區劃分結果：")
for community_id in set(partition.values()):members = [node for node, id in partition.items() if id == community_id]print(f"社區 {community_id}：{members}")# 4. 可視化社區劃分 - 使用自定義顏色列表（避免黃色，增加紅色系）
plt.figure(figsize=(10, 6))# 自定義顏色列表（選擇與白色文字對比度高的顏色，替換黃色為紅色系）
custom_colors = ['#FF6B6B',  # 淺紅色'#4ECDC4',  # 青綠色'#45B7D1',  # 天藍色'#FFA07A',  # 淺橙色'#98D8C8'   # 淡青色
]# 根據社區數量選擇合適的顏色
num_communities = max(partition.values()) + 1
used_colors = custom_colors[:num_communities]# 繪制節點（使用自定義顏色）
nx.draw_networkx_nodes(G_undirected, pos, partition.keys(),node_size=800, node_color=[used_colors[id] for id in partition.values()])# 繪制標簽（白色文字）
nx.draw_networkx_labels(G_undirected, pos, font_size=12, font_family=plt.rcParams["font.family"],font_color='white')# 繪制邊
nx.draw_networkx_edges(G_undirected, pos, alpha=0.5)plt.title("Louvain算法社區劃分結果")
plt.show()

為何 Louvain 算法高效且實用？

1. 低時間復雜度：每輪迭代的時間復雜度約為 $O(n)$（$n$ 是節點數），即使是百萬級節點的網絡，也能快速運行（這是它比傳統全局優化算法（如譜聚類）更實用的核心原因）。
2. 近似最優解：雖然是局部優化，但通過多輪迭代的社區聚合，最終能逼近全局最大模塊度（在大多數真實網絡中，效果接近最優）。
3. 適配無向網絡：標準 Louvain 算法僅支持無向網絡（加權/無權均可）；若處理有向網絡（水果 DAG），需先將其轉換為無向網絡（如 G.to_undirected()）。

結合代碼，對應算法原理

import networkx as nx
import community as community_louvain
import matplotlib.pyplot as plt# 1. 構建水果DAG（有向）
G = nx.DiGraph()
nodes = ["蘋果", "香蕉", "橙子", "草莓", "紅色", "黃色", "橙色", "甜味", "酸味", "顏色", "味道", "漿果", "核果"]
G.add_nodes_from(nodes)
edges = [("蘋果", "紅色"), ("蘋果", "甜味"), ("蘋果", "核果"), ...]  # 省略部分邊
G.add_edges_from(edges)# 2. 轉換為無向圖 → 適配標準Louvain算法（僅支持無向網絡）
G_undirected = G.to_undirected()  # 關鍵：有向邊轉為無向邊，確保A_ij=A_ji# 3. Louvain算法核心：community_louvain.best_partition()
partition = community_louvain.best_partition(G_undirected)  # 內部執行完整的兩階段迭代

代碼與算法原理的對應：

1. 無向圖轉換（G.to_undirected()）：
   標準 Louvain 算法基于無向圖的鄰接矩陣 $A_{ij}$（滿足 $A_{ij}=A_{ji}$），因此必須將你的有向 DAG 轉為無向圖，否則無法計算節點度 $k_i$ 和總邊數 $m$。

2. community_louvain.best_partition() 內部邏輯：
   這個函數封裝了 Louvain 算法的完整迭代流程：

   • 初始狀態：為每個水果/屬性節點（如“蘋果”“紅色”“顏色”）分配獨立社區 ID（例如，“蘋果”=0，“香蕉”=1，…，“核果”=12）。
   • 階段 1（局部移動）：
     遍歷每個節點（如“蘋果”），計算其相鄰節點（“紅色”“甜味”“核果”）所屬社區的 ΔQ，選擇 ΔQ 最大的社區移動。例如：
     • “蘋果”與“紅色”相連，計算將“蘋果”移入“紅色”社區的 ΔQ；
     • 若 ΔQ > 0，且是所有相鄰社區中最大的，則“蘋果”與“紅色”歸為同一社區。
   • 階段 2（社區聚合）：
     將階段 1 得到的社區（如“蘋果-紅色-草莓”為一個社區，“香蕉-黃色”為另一個社區）聚合為超級節點，構建新的小網絡，再次執行階段 1。
   • 迭代終止：直到模塊度不再提升，輸出最終的社區劃分（即 partition 字典，鍵是節點，值是社區 ID）。

3. 輸出結果（社區劃分）：
   打印的“社區 0：[蘋果, 紅色, 草莓]，社區 1：[香蕉, 黃色]…”，正是 Louvain 算法通過多輪兩階段迭代后，最大化模塊度得到的結果——這些社區內部的節點連接更緊密（如“蘋果-紅色”“草莓-紅色”有邊），外部連接更稀疏。