在复杂网络分析中，社区检测是解析网络结构与功能的核心任务，其目标是识别节点密集连接的子集（社区），为生物网络功能注释、社交网络舆情追踪、引文网络主题识别等场景提供支撑。Louvain 算法作为经典的社区检测工具，因高效性被广泛应用，但 Traag、Waltman 与 van Eck（2019）的研究揭示了其关键缺陷 —— 易生成不良连接甚至完全断开的社区，而 Leiden 算法的提出则系统性解决了这一问题，为社区检测提供了更可靠的选择。
Louvain 算法的核心缺陷：断开社区的产生
Louvain 算法通过 “局部节点移动 + 网络聚合” 两阶段迭代优化质量函数（模块化或 CPM），但该流程存在本质局限：仅关注单个节点的局部最优移动，忽略社区整体连通性。其直接后果是生成断开社区—— 算法划分的同一社区内，部分节点需通过社区外部的节点或边才能与其他节点连通，内部形成孤立子集群。
Traag 等人（2019）的实验数据显示，Louvain 算法检测的社区中，最高 25% 为不良连接社区（Amazon 网络），最高 16% 为完全断开社区（DBLP 网络），Web of Science 网络首轮迭代中断开社区比例即超过 5%。更严重的是，迭代会加剧这一缺陷，多数网络迭代后断开社区比例升高近 10 倍。
用通俗场景可解释这一现象：将网络节点视为小区居民，社区对应兴趣小组。Louvain 算法如同小区管理员，仅依据 “单个人是否愿意留在小组” 划分 —— 原本连接下棋大爷与带娃宝妈的 “桥节点”（如保洁阿姨）被移至其他小组后，大爷与宝妈群体失去内部关联，但因各自在小群体内连接紧密，管理员仍将两拨无交集的人归为同一小组，形成 “名义上的社区，实际上的孤立集群”。
核心质量函数：社区划分的评价标准
社区检测的质量由特定函数量化，主流包括两种：
模块化（Modularity）：衡量社区内边数与随机网络期望边数的差异，公式为：
\(\mathcal{H}=\frac{1}{2\mathrm{m}} \sum_{\mathrm{c}}\left(\mathrm{e}_{\mathrm{c}}-\gamma \frac{\mathrm{K}_{\mathrm{c}}^2}{2\mathrm{m}}\right)\)
其中，\(\mathrm{e}_{\mathrm{c}}\)为社区\(\mathrm{c}\)内实际边数，\(\mathrm{K}_{\mathrm{c}}\)为社区\(\mathrm{c}\)节点度之和，\(\mathrm{m}\)为网络总边数，\(\gamma>0\)为分辨率参数（值越高生成社区越多，值越低生成社区越少）。该函数存在分辨率限制，可能将小社区聚类为大社区。
CPM（Constant Potts Model）：克服模块化的分辨率限制，公式为：
\(\mathcal{H}=\sum_{\mathrm{c}}\left[\mathrm{e}_{\mathrm{c}}-\gamma\left(\begin{array}{c}\mathrm{n}_{\mathrm{c}} \\ 2\end{array}\right)\right]\)
其中\(\mathrm{n}_{\mathrm{c}}\)为社区\(\mathrm{c}\)的节点数，\(\gamma\)为阈值（社区内密度需≥\(\gamma\)，社区间密度需 <\(\gamma\)），分辨率调节逻辑与模块化一致。
Louvain 算法的缺陷与质量函数无关，即便使用 CPM 仍会生成断开社区（Traag et al., 2019）。
Leiden 算法的改进：连通性与效率的双重突破
为解决 Louvain 的缺陷，Leiden 算法在其基础上新增 “分区细化” 阶段，形成 “局部节点移动→分区细化→网络聚合” 的三阶段迭代流程，核心改进包括：
局部节点移动：采用快速局部移动策略，仅访问邻居社区发生变化的节点，通过队列管理减少无效计算，提升效率；
分区细化：在局部移动生成的分区基础上，仅在原社区内随机合并节点（\(\theta\)参数控制随机性，仅保留提升质量函数的合并），确保社区连通性；
网络聚合：基于细化分区构建聚合网络，初始分区参考原分区，支持迭代优化。
Leiden 算法提供了 Louvain 不具备的理论保证：每轮迭代后社区满足\(\gamma\)- 连通性（确保内部连通）；迭代收敛后，社区达到子集最优（所有子集均局部最优）与均匀\(\gamma\)- 稠密（无任何子集可从社区分离）（Traag et al., 2019）。
实验验证：性能与质量的全面超越
Traag 等人（2019）在 6 个真实网络（节点数 31.7 万至 3.9 亿）与基准网络中验证了 Leiden 的优越性：
速度：Leiden 比 Louvain 快 2-20 倍，网络规模越大优势越显著。Web UK 网络（3.9 亿节点）中，Leiden 速度是 Louvain 的 20 倍以上；Web of Science 网络（981 万节点）中，Leiden 首轮迭代仅需 110-120 秒，而 Louvain 需远超该时间；
质量：所有网络中 Leiden 的模块度均高于 Louvain。例如，Live Journal 网络模块度从 0.7653 提升至 0.7739，Web of Science 网络从 0.7911 提升至 0.7951；
连通性：Leiden 消除断开社区，迭代后不良连接社区比例持续下降，收敛后无不良连接社区。
结语
Louvain 算法因断开社区缺陷，难以满足对社区连通性与精度要求较高的场景。Leiden 算法通过流程优化与理论保障，在连通性、效率与质量上全面超越 Louvain，成为复杂网络社区检测的优选方案。
参考文献
Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9(5233), https://doi.org/10.1038/s41598-019-41695-z