本文介绍了 Leiden 算法与 Louvain 算法的原理、流程及对比。Leiden 算法通过引入细化阶段解决了 Louvain 算法可能产生不连通社区的问题，具有更高的质量、速度和稳定性。文章详细阐述了模块度概念、算法步骤、代码实现示例（Python），并给出了在知识图谱中的应用实践建议。
在知识图谱或任何复杂网络中，'社区结构'是指网络中的节点被划分为若干个组，组内连接密集，组间连接稀疏。检测社区结构有助于：
Leiden 算法由 Traag、Waltman 和 van Eck 于 2019 年提出，旨在解决其前身——非常流行的Louvain 算法——所存在的主要缺陷。
要理解 Leiden，必须先了解 Louvain。Louvain 算法是一种基于模块度优化的快速启发式算法，包含两个反复迭代的阶段：
Louvain 算法的主要缺陷：
Leiden 算法继承了 Louvain 的高效框架（两阶段迭代），但通过引入一个关键的'细化'阶段和更智能的移动策略，彻底解决了 Louvain 的缺陷。其核心流程也是三个阶段，但内涵不同：
第一阶段：局部节点移动
第二阶段：细化
{C} 后，算法会对每个社区 C 进行内部重新划分。{s}。s 的内部连接是紧密的。这直接解决了 Louvain 产生'连接不良社区'的问题。第三阶段：社区聚合
{C} 进行聚合，而是基于细化阶段后产生的子社区 {s} 进行聚合。s 被折叠成一个新的超级节点。s 内部都是连接良好的，这就保证了在后续迭代中，由超级节点代表的'社区'始终是内部连通的。将上述三个阶段整合为一个完整的迭代轮次，算法流程如下：
{C}。
b. 细化：对每一个初步社区 C ∈ {C}，在其内部运行一个限制性的社区发现算法（本质上是带约束的移动步骤），将 C 划分为一组连接良好的子社区 {s}。
c. 聚合：将所有细化后得到的子社区 {s} 聚合为新的超级节点，构建一个更粗粒度的网络。将 Leiden 算法应用于知识图谱时，通常的步骤是：
igraph(Python/R),NetworkX(Python，但大规模图较慢),graph-tool，或专门的分布式图系统如Neo4j GDS**,Spark GraphFrames）中实现的 Leiden 算法。Leiden 算法是对经典 Louvain 算法的重大改进，它通过引入一个强制性的'细化'阶段，不仅解决了 Louvain 可能产生无意义的不连通社区的问题，还在社区划分质量、速度和稳定性上实现了全面超越。对于构建和分析大规模知识图谱，尤其是当社区结构的语义连贯性和可靠性至关重要时，Leiden 算法是目前模块度优化类算法中的首选。
Louvain 算法（又称 Blondel 算法）是 Vincent Blondel 等人在 2008 年提出的一种基于模块度优化的层次化社区发现算法。它以极高的计算效率和良好的划分质量而闻名，成为大规模网络社区发现的经典算法。
理解 Louvain 算法的关键是理解模块度，这是衡量社区划分质量的指标。
对于无向图，模块度 Q 定义为：
其中：
：指示函数，当
时为 1，否则为 0
：节点 i 所属的社区
：图中所有边的总权重
：节点 i 的度（或加权度）
：节点 i 和 j 之间的边权重（无权图中为 1 或 0）
差值：社区内部的实际连接减去随机期望的连接
范围：-1 ≤ Q ≤ 1，值越大表示社区结构越明显（通常 Q>0.3 认为有明显社区结构）
第二部分：在随机图（保持节点度不变）中节点 i 和 j 之间期望的连接数
第一部分：测量社区内部实际存在的连接
Louvain 算法采用两阶段迭代的贪婪优化策略：
目标：通过移动节点来最大化模块度增益
过程：
模块度变化 ΔQ 的计算公式：当节点 i 从原社区 D 移动到社区 C 时：
![\Delta Q = \left[ \frac{\sum_{in} + 2k_{i,in}}{2m} - \left( \frac{\sum_{tot} + k_i}{2m} \right)^2 \right] - \left \frac{\sum_{in}}{2m} - \left( \frac{\sum_{tot}}{2m} \right)^2 - \left( \frac{k_i}{2m} \right)^2 ]
其中：
：节点 i 与社区 C 中节点之间的边权重和
：节点 i 的度
：与社区 C 中节点相连的所有边权重和（包括社区内部和外部）
：社区 C 内部所有边的权重和
关键优化：ΔQ 可以局部计算，无需每次重新计算整个图的模块度，这是算法高效的关键。
目标：构建新的粗粒度图，为下一轮优化做准备
过程：
1. 初始化：每个节点作为一个社区
2. 重复直到模块度不再显著增加：
a. 执行阶段一（局部优化），直到没有节点可以移动
b. 计算当前模块度 Q
c. 执行阶段二（图压缩），构建新图
d. 在新图上重复阶段一
3. 输出最终的社区划分
考虑一个简单网络：4 个节点组成的环，额外增加一条对角线
节点：A, B, C, D
边：A-B, B-C, C-D, D-A, A-C (对角线)
执行过程：
# 使用 python-louvain 库的示例
import networkx as nx
import community as community_louvain
# 构建知识图谱的图表示
G = nx.Graph()
# 添加节点和边（带权重）
G.add_edge("实体 A", "实体 B", weight=3.0)
G.add_edge("实体 B", "实体 C", weight=2.5)
# ... 添加更多实体和关系
# 执行 Louvain 算法
partition = community_louvain.best_partition(G, weight='weight')
# 查看结果
for node, community_id in partition.items():
print(f"{node} -> 社区{community_id}")
# 计算模块度
modularity = community_louvain.modularity(partition, G, weight='weight')
print(f"模块度：{modularity}")
尽管 Louvain 算法非常流行，但它存在几个重要缺陷：
修改模块度公式：
| 特性 | Louvain 算法 | Leiden 算法 |
|---|---|---|
| 社区连通性 | 不保证 | 保证每个社区内部连通 |
| 结果质量 | 可能陷入局部最优 | 通常找到模块度更高的划分 |
| 运行速度 | 单次迭代快 | 单次迭代稍慢，但总迭代次数少 |
| 稳定性 | 对节点顺序敏感 | 更稳定，随机性影响小 |
| 可重复性 | 较差 | 更好 |
| 分辨率限制 | 存在 | 同样存在，但通过细化阶段缓解 |
python-louvain（又名community）库igraph包的cluster_louvain()函数Louvain 算法是社区发现领域的里程碑式算法，以其简单、高效、无需参数的特点被广泛应用。尽管存在产生不连通社区、结果不稳定等缺陷，但它仍然是理解网络社区结构的强大工具，并为后续更先进的算法（如 Leiden）奠定了基础。
对于知识图谱分析，Louvain 算法可以快速识别出实体聚集模式，但需要谨慎解释结果，特别是要检查社区的连通性和语义一致性。在实际应用中，如果条件允许，推荐使用其改进版——Leiden 算法，以获得更可靠、质量更高的社区划分。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
生成新的随机RSA私钥和公钥pem证书。 在线工具，RSA密钥对生成器在线工具，online
基于 Mermaid.js 实时预览流程图、时序图等图表，支持源码编辑与即时渲染。 在线工具，Mermaid 预览与可视化编辑在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online