PythonAI算法
复杂网络分析:社区发现算法简介
复杂网络分析中五种经典的社区发现算法,包括基于模块度优化的 Louvain 算法、基于边介数的 Girvan-Newman 算法、谱聚类、基于信息论的 Infomap 算法以及改进版 Leiden 算法。文章详细阐述了各算法的原理与流程,提供了基于 Python 和 networkx 库在空手道俱乐部数据集上的完整实现代码及可视化示例。最后通过对比表格分析了各算法在社区数、模块度及特点上的差异,并给出了针对不同场景的算法选择建议与注意事项。

复杂网络分析中五种经典的社区发现算法,包括基于模块度优化的 Louvain 算法、基于边介数的 Girvan-Newman 算法、谱聚类、基于信息论的 Infomap 算法以及改进版 Leiden 算法。文章详细阐述了各算法的原理与流程,提供了基于 Python 和 networkx 库在空手道俱乐部数据集上的完整实现代码及可视化示例。最后通过对比表格分析了各算法在社区数、模块度及特点上的差异,并给出了针对不同场景的算法选择建议与注意事项。

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)
# 使用 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()
# 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()
# 构建拉普拉斯矩阵并计算特征向量
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()
# 创建 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()
# 使用 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,速度更快,模块度相同 |
resolution_parameter 调整社区粒度)。
微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
生成新的随机RSA私钥和公钥pem证书。 在线工具,RSA密钥对生成器在线工具,online
基于 Mermaid.js 实时预览流程图、时序图等图表,支持源码编辑与即时渲染。 在线工具,Mermaid 预览与可视化编辑在线工具,online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具,curl 转代码在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online