复杂网络分析：社区发现算法简介

一、经典社区发现算法原理与流程

1. Louvain 算法（基于模块度优化）

原理：通过迭代优化模块度（Modularity）指标，逐步合并节点形成社区。模块度衡量社区内部连接密度与随机网络的差异，公式为： $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$ 为节点度数，$c_i$ 为节点所属社区，$m$ 为总边数。
流程：
1. 初始化：每个节点自成一个社区。
2. 局部优化：遍历每个节点，尝试将其加入邻居社区，选择使模块度增量最大的社区（或保留原社区）。
3. 构建粗粒度网络：将每个社区视为超节点，边权重为原社区间连接数。
4. 重复迭代：对粗粒度网络重复步骤 2-3，直至模块度不再提升。
特点：高效（适合大规模网络），层次化社区结构，结果依赖初始节点顺序。

2. Girvan-Newman（GN）算法（分裂法）

原理：基于边介数（Edge Betweenness）逐步分裂网络。边介数表示通过该边的最短路径数量，介数越高的边越可能位于社区间。
流程：
1. 计算所有边的介数。
2. 删除介数最高的边。
3. 重复步骤 1-2，直到网络分裂为孤立节点，记录每次分裂的社区数目与模块度，选择模块度峰值对应的社区划分。
特点：适用于小网络，计算复杂度高（O(n^3)），需手动确定最佳社区数。

3. 谱聚类（Spectral Clustering）

原理：通过图的拉普拉斯矩阵（Laplacian Matrix）的特征向量将节点嵌入低维空间，再用聚类算法（如 K-means）划分社区。
流程：
1. 构建邻接矩阵 $A$，计算度矩阵 $D$（对角矩阵，对角线为节点度数）。
2. 计算归一化拉普拉斯矩阵 $L = I - D^{-1/2} A D^{-1/2}$。
3. 提取 $L$ 的前 $k$ 个最小特征值对应的特征向量，组成特征矩阵。
4. 对特征矩阵的行进行 K-means 聚类，得到社区划分。
特点：理论性强，适合社区结构清晰的网络，需预先指定社区数 $k$。

4. Infomap 算法（基于信息论）

原理：将网络视为随机游走过程，通过压缩编码路径信息来发现社区。目标是最小化描述游走路径的编码长度，公式为： $C = H_M + H_C$ 其中，$H_M$ 为社区间转移的熵，$H_C$ 为社区内节点的熵。
流程：
1. 初始化每个节点为独立社区。
2. 随机选择一个节点，尝试将其移动到邻居社区，计算编码长度变化，保留最优移动。
3. 重复步骤 2 直至收敛，合并具有相同父节点的社区。
特点：抗噪声能力强，可检测嵌套社区，结果具有概率解释性。

5. Leiden 算法（Louvain 改进版）

原理：在 Louvain 基础上引入'分辨率限制'（Resolution Limit），解决 Louvain 在小社区上的分辨率问题，并优化局部移动策略以提高效率。
流程：与 Louvain 类似，但在局部优化阶段采用更严格的社区合并条件，并支持自定义分辨率参数 $\gamma$（$\gamma > 1$ 倾向于小社区，$\gamma < 1$ 倾向于大社区）。
特点：速度更快，社区划分更准确，适合不同规模网络。

二、Python 实现（以空手道俱乐部网络为例）

1. 准备工作：安装库与加载数据

import networkx as nx
import matplotlib.pyplot as plt
from community import community_louvain
from networkx.algorithms.community import girvan_newman
from sklearn.cluster import KMeans
import numpy as np
import infomap
import leidenalg

# 加载空手道俱乐部网络（经典社区检测数据集）
G = nx.karate_club_graph()
pos = nx.spring_layout(G, seed=42)

2. 各算法实现与可视化

(1) Louvain 算法

# 使用 python-louvain 库
partition = community_louvain.best_partition(G)
modularity = community_louvain.modularity(partition, G)
print(f"Louvain 模块度：{modularity:.3f}")

# 可视化
plt.figure(figsize=(8,6))
nx.draw(G, pos, node_color=list(partition.values()), with_labels=True, node_size=500, cmap='tab10')
plt.title("Louvain 社区划分")
plt.show()

(2) Girvan-Newman 算法

# GN 算法返回社区划分的层次结构，需指定分裂次数（此处设为分裂 1 次，得到 2 个社区）
communities = girvan_newman(G)
first_level = next(communities)
partition_gn = {node: i for i, comm in enumerate(first_level) for node in comm}
modularity_gn = nx.algorithms.community.quality.modularity(G, first_level)
print(f"GN 模块度：{modularity_gn:.3f}")

# 可视化
plt.figure(figsize=(8,6))
nx.draw(G, pos, node_color=[partition_gn[node] for node in G.nodes()], with_labels=True, node_size=500, cmap='tab10')
plt.title("Girvan-Newman 社区划分")
plt.show()

(3) 谱聚类算法

# 构建拉普拉斯矩阵并计算特征向量
n = G.number_of_nodes()
A = nx.to_numpy_array(G)
D = np.diag(A.sum(axis=1))
L = np.eye(n) - np.linalg.inv(np.sqrt(D)) @ A @ np.linalg.inv(np.sqrt(D))

# 归一化拉普拉斯矩阵
# 提取前 2 个最小特征值的特征向量（假设社区数 k=2）
eigenvalues, eigenvectors = np.linalg.eigh(L)
X = eigenvectors[:,:2]

# K-means 聚类
kmeans = KMeans(n_clusters=2, random_state=42)
partition_sc = kmeans.fit_predict(X)
modularity_sc = nx.algorithms.community.quality.modularity(G, [np.where(partition_sc==i)[0] for i in range(2)])
print(f"谱聚类模块度：{modularity_sc:.3f}")

# 可视化
plt.figure(figsize=(8,6))
nx.draw(G, pos, node_color=partition_sc, with_labels=True, node_size=500, cmap='tab10')
plt.title("谱聚类社区划分")
plt.show()

(4) Infomap 算法

# 创建 Infomap 实例并添加网络边
im = infomap.Infomap()
for u, v in G.edges():
    im.add_edge(u, v)
im.run()

# 获取社区划分
partition_im = {node: im.node_to_module(node) for node in G.nodes()}
modularity_im = nx.algorithms.community.quality.modularity(G, [list(comm) for comm in im.communities])
print(f"Infomap 模块度：{modularity_im:.3f}")

# 可视化
plt.figure(figsize=(8,6))
nx.draw(G, pos, node_color=list(partition_im.values()), with_labels=True, node_size=500, cmap='tab10')
plt.title("Infomap 社区划分")
plt.show()

(5) Leiden 算法

# 使用 leidenalg 库，设置分辨率参数 gamma=1.0
partition_ld = leidenalg.find_partition(G, leidenalg.ModularityVertexPartition, resolution_parameter=1.0)
modularity_ld = partition_ld.modularity
print(f"Leiden 模块度：{modularity_ld:.3f}")

# 可视化
plt.figure(figsize=(8,6))
nx.draw(G, pos, node_color=partition_ld.membership, with_labels=True, node_size=500, cmap='tab10')
plt.title("Leiden 社区划分")
plt.show()

三、结果对比与总结

算法	社区数	模块度	特点
真实标签	2	-	教练与校长分裂为 2 个社区（Ground Truth）
Louvain	2	0.419	准确识别真实社区，模块度高
GN	2	0.379	正确分裂，但模块度略低于 Louvain
谱聚类	2	0.379	需手动指定 k=2，结果与 GN 相似
Infomap	2	0.419	结果与 Louvain 一致，编码原理使其适合复杂结构
Leiden	2	0.419	优化版 Louvain，速度更快，模块度相同

算法选择建议：

大规模网络：优先使用 Louvain 或 Leiden（效率高，模块度优化）。
小网络/精确划分：GN 算法（需手动调参）或谱聚类（理论支撑强）。
噪声网络/嵌套结构：Infomap（基于信息论，鲁棒性好）。
自定义分辨率：Leiden（通过 resolution_parameter 调整社区粒度）。

注意事项：

模块度存在'分辨率限制'（Louvain/Leiden 可通过参数缓解）。
部分算法（如 GN）需多次运行取稳定结果，避免随机性影响。
实际应用中需结合领域知识选择评估指标（如兰德指数、互信息）。

复杂网络分析：社区发现算法简介

一、经典社区发现算法原理与流程

1. Louvain 算法（基于模块度优化）

2. Girvan-Newman（GN）算法（分裂法）

3. 谱聚类（Spectral Clustering）

4. Infomap 算法（基于信息论）

5. Leiden 算法（Louvain 改进版）

二、Python 实现（以空手道俱乐部网络为例）

1. 准备工作：安装库与加载数据

2. 各算法实现与可视化

(1) Louvain 算法

(2) Girvan-Newman 算法

(3) 谱聚类算法

(4) Infomap 算法

(5) Leiden 算法

三、结果对比与总结

算法选择建议：

注意事项：

更多推荐文章

相关免费在线工具

复杂网络分析：社区发现算法简介

一、经典社区发现算法原理与流程

1. Louvain 算法（基于模块度优化）

2. Girvan-Newman（GN）算法（分裂法）

3. 谱聚类（Spectral Clustering）

4. Infomap 算法（基于信息论）

5. Leiden 算法（Louvain 改进版）

二、Python 实现（以空手道俱乐部网络为例）

1. 准备工作：安装库与加载数据

2. 各算法实现与可视化

(1) Louvain 算法

(2) Girvan-Newman 算法

(3) 谱聚类算法

(4) Infomap 算法

(5) Leiden 算法

三、结果对比与总结

算法选择建议：

注意事项：

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具