在研读 GraphRAG 的时候发现了 Leiden 社群检测算法，对其原理很好奇，遂来学习研读一二。
论文标题：《From Louvain to Leiden: guaranteeing well-connected communities》
原文补充信息可以点击上述链接打开 Nature 官网查看。
P.S. 如果你想要看 Leiden 社群检测算法的具体实现，可以参考 Python 的 graspologic 库的 hierarchical_leiden() 方法哦！
1. 为什么要引入 Leiden 社群检测算法？以前的研究有什么不足？
在复杂网络中，节点趋向于聚集形成相对紧密的群体（即社群 communities）。这种结构事先未知，因此检测社群是一项重要任务。有一种有名的社群检测算法：模块度方法（modularity）。模块度方法的主要思想是，最大化社群内实际存在的边数与在随机假设下的期望边数之差。实际与期望边数如下表示：
实际边数：记为 ec ，表示社群 c 内部包含的边数。
期望边数：通过配置模型计算得到，表示为
其中，Kc 表示社群 c 中所有节点的度数之和，m 表示整个网络中的总边数。于是可以定义模块度（modularity）：
其中 γ > 0 是分辨率参数。分辨率参数越高，划分出的社群数越多。
然而，优化模块度是一个 NP-hard 问题，因此涌现出来了许多启发式算法。例如：
层次凝聚（hierarchical agglomeration）
极值优化（extremal optimisation）
模拟退火（simulated annealing）
谱算法（spectral algorithms）
在这些启发式算法中，有一个非常流行的算法：Louvain 算法。它在当时是速度最快且表现最好的算法之一，还是当时整个社群检测文献中被引用次数最多的著作之一。虽然 Louvain 算法最初是为优化模块度而设计的，但它同样可以用来优化其他质量函数。比如恒定波茨模型（Constant Potts Model, CPM），它克服了一些模块度指标的局限性：
其中 nc 是社群 c 中的节点数。与分辨率参数 γ 相乘的组合数表示该社群内部可能存在的最大总边数。CPM 中的分辨率参数 γ 具有清晰含义：
密度阈值作用：γ 扮演着一种“门槛”的角色——社群内部的密度应当至少为 γ ，而社群之间的密度应当低于 γ 。
分辨率参数越高，划分出的社群数越多。这一点与模块度类似。
然而作者在本研究中发现，Louvain 算法存在一个重大缺陷（无论优化目标是模块度还是 CPM ）：它会产生任意坏连通的社群，甚至产生内部完全不连通的社群。
为了解决任意坏连通问题，作者提出了 Leiden 算法，它综合并集成了先前的多项改进技术：
智能局部移动（Smart local move）
快速局部移动（Fast local move）
随机邻居移动（Random neighbour move）
Leiden 算法不仅运行更快、划分质量更好，还提供了显式的理论保证与边界：
内部连通性保证：数学上证明了该算法保证产生的划分中所有社群都是内部连通的。
渐近稳定划分（Asymptotically stable partition）：证明了算法会收敛到一个渐近稳定划分，在该划分中，所有社群的所有子集都被局部最优地分配。
最优质量上界：这种渐近稳定划分的质量，为全局最优划分的质量提供了一个上界。
最后，作者在一些基准测试与真实世界网络上验证了 Leiden 算法的有效性。
2. 从 Louvain 算法开始谈起
2.1 Louvain 算法的原理
Louvain 算法通过交替执行以下两个基础阶段来优化质量函数（如模块度 Modularity 或 CPM）：
阶段一：节点的局部移动。逐个遍历节点，将单个节点移动到能使其质量函数增量最大的社群中。
阶段二：网络的聚合。根据第一阶段获得的社群划分结果构建一个聚合网络。在此网络中，上一阶段划分出的每个社群都会收缩变成新网络中的一个单一节点。
这两个阶段会重复交替进行，直到质量函数无法获得进一步的提升为止。
通常情况下，Louvain 算法从单例划分（singleton partition）开始，即初始时网络中的每一个节点各自属于一个独立的社群。不过算法也可以将任何已有的划分作为起点。为了尝试寻找质量更好的划分，可以连续多次迭代运行该算法——将上一轮迭代最终识别出的社群划分结果，直接作为下一轮迭代的起始状态。
可以参考下面的示意图：
2.2 坏连通的社群
作者发现，Louvain 算法会划分出内部不连通的社群。这种社群内部被切分为不相连的部分，其中一部分节点如果想要到达另一部分节点，必须通过位于该社群之外的路径。更严重的是，社群断开问题不仅是理论上的极端特例。实验分析表明，在使用 Louvain 算法时，该问题在实际应用中频繁出现。
令人惊讶的是，连续迭代运行算法会加剧社群断开的问题。虽然迭代确实能进一步提高质量函数的得分，但同时却让社群内部的连通性变得更加糟糕。
为什么 Louvain 算法会导致这一问题呢？直观上来讲：
桥梁节点的离开：在某个节点被移出旧社群前，它可能在旧社群内部的不同部分之间扮演着“桥梁”的角色。
引发社群断开：一旦这个“桥梁节点”为了寻求质量函数的更大增量而移入其他社群，旧社群就会失去连接纽带，在内部被切断。
剩余节点无法自动修复：人们直觉上可能以为旧社群中被切断的剩余节点随后也会被移走，但事实并非如此。因为即使社群已经断开，这些剩余节点在原社群残留的局部范围内依然保持着足够的连接强度，因此算法没有进一步将它们移走的动力，导致这个“内部断开”的社群被保留了下来。
下图直观展示了 Louvain 算法是如何导致内部不连通的社群的：
解读：点 0–6 初始时位于同一个社群内。节点 1–6 仅在该社群内部存在连接，而节点 0 作为“桥梁”，还拥有许多外部连接。图中的粗边代表较强的连接，其余边代表较弱的连接。当网络其他部分的节点逐渐形成新社群后，节点 0 的外部邻居达到了足够数量。时为了追求质量函数的更大增量，算法将节点 0 移出了原社群，进入外部社群（形成了图 2b 所示的状态）。此时出现了以下困境：
节点 2, 3, 5, 6：仅拥有内部连接，因此被局部最优地分配在当前社群。
节点 1, 4：虽然同时拥有内部和外部连接，但受连接相对强度的影响，它们依然可能被局部最优地留在当前社群。
断裂现状：节点 1–6 在单节点层面全都是局部最优分配，但整个社群在全局客观上已经断裂（节点 1–3 与节点 4–6 之间失去了内部直接路径）。
从上图示例中我们能发现一些 Louvain 算法导致内部不连通社群的机理：
只能做“单节点移动”：显而易见，最优的解法是将原社群拆分为 {1, 2, 3} 和 {4, 5, 6} 两个新社群。但 Louvain 算法仅考虑单节点的移动，无法做出“拆分社群”这种宏观决策。
网络聚合加重这一现象：当没有单个节点可以继续移动时，算法就会进入聚合阶段，将这个内部断开的社群直接坍缩为一个聚合节点。一旦变成聚合节点，社群就彻底失去了被拆分的可能，除非未来碰巧与另一个充当桥梁的社群合并。
前面图 2 展示的是社群完全断开的最坏情况。但在实际应用中，还会出现更隐蔽的问题——算法检测到的社群虽然在形式上连通，但连接关系极其微弱 。因此综合来看，我们说 Louvain 算法可能会产生任意坏连通的社群。
此外作者强调：Louvain 的这一缺陷与模块度的分辨率极限（Resolution limit）问题是两个完全不同的问题：
什么是分辨率极限：由于模块度质量函数自身的计算特性，它倾向于将小社群合并为大社群，从而“隐藏”小社群，使社群内部包含显著的子结构。
CPM 模型可以解决分辨率极限：恒定波茨模型（CPM）不会受到分辨率极限的影响。
缺陷的独立性：然而，即使改用 CPM 作为质量函数，Louvain 算法依然会产生任意坏连通的社群。这证明了 Louvain 算法的连通性缺陷是算法自身的机制问题，独立于质量函数的“分辨率极限”。
双重影响：在优化模块度时，一个社群之所以包含显著的内部子结构，既可能是因为分辨率极限，也可能是因为 Louvain 算法本身的缺陷。
事实上，Louvain 算法在理论上只能确保：
对于标准单次 Louvain ：保证没有任何两个社群可以通过合并来进一步提升质量函数。
对于连续迭代 Louvain ：保证没有可以合并的社群，且没有可以移动的单个节点（即每个节点都是局部最优分配）。
此外，作者发现迭代运行 Louvain 会加剧社群断开与坏连通，作者的解释是：
在上一轮迭代生成的社群基础之上，下一轮迭代再次移动节点时，可能会将充当“桥梁”的节点移走，从而切断旧社群。而由于 Louvain 算法缺乏对已有社群进行拆分或修复的机制，这种损坏不仅被保留，还会被进一步放大。
因此，Louvain 算法是一把 “双刃剑”，它能提升社群划分质量函数，但却引入了任意坏连通性。
事实上，社群断开现象在先前的文献中曾被观察到，但过去的方法（例如简单地将断开的社群事后切分成独立的连通分量）存在缺陷：
仅处理了最极端情况：简单的连通分量切分只能修复“完全断开（Disconnected）”这种最极端的情况；
无法解决更本质的问题：它无法从根本上修复“连接关系较弱”的社群。
需要系统性的根本解法：必须从算法的设计机制本身入手，而不是依靠事后打补丁。
因此，作者提出了 Leiden 算法，这引出了下一章节。
3. Leiden 算法
3.1 算法概述
Leiden 算法集成了以往改进 Louvain 算法中最具前景的几项关键技术：
智能局部移动算法：其本身就是对 Louvain 算法的一种改进
加速节点局部移动
向随机邻居移动节点。
Leiden 算法分为三个阶段：
阶段一：节点的局部移动
阶段二：划分的细化
阶段三：基于细化划分的网络聚合
关键细节：在此阶段，利用阶段二细化后的划分来构建聚合网络，同时使用阶段一未细化的划分作为该聚合网络中节点的初始划分。
由于引入了细化过程与更复杂的聚合机制，Leiden 算法在结构上比 Louvain 算法复杂得多。可以参考下图以直观了解：
细化阶段的设计思想：P 与 Prefined 的配合
与 Louvain 算法的区别：
Louvain 算法：直接根据局部移动阶段得到的划分 P 来构建聚合网络。
Leiden 算法：先在划分 P 的基础上寻找一个更细化的划分 Prefined 。在 Prefined 中，原划分 P 中的大社群可能会被拆分为多个子社群。
聚合网络构建的“巧思”：
Leiden 算法的聚合网络是基于细化划分 Prefined 构建的（即 Prefined 中的每个子社群缩为一个新节点）。
但该聚合网络中节点的初始划分，依然是基于未细化的划分 P 。
带来的优势：基于 Prefined 构建聚合网络为寻找高质量划分留出了更大空间，并且只要正确实施细化阶段，就能为 Leiden 算法生成的划分提供多种优良的理论保证。
细化划分 Prefined 的生成规则：
划分初始化与合并约束：
单例初始化：细化划分 Prefined 初始时被设置为单例划分，即每个节点各自独立为一个新社群。
限定合并边界：节点的合并操作只能在原划分 P 的同一个社群内部进行，绝不跨越 P 的界限。
连通性门槛：只有当节点以及目标社群均与它们在 P 中对应的原社群保持足够紧密的连接时，才允许执行合并。
随机化选择机制（非贪心策略）：
放弃传统贪心策略：在选择合并的目标社群时，算法并没有贪心地直接挑选“能产生最大质量函数增量”的社群。相反，只要某个合并能够带来质量函数的任何正向增长，该目标社群就是可选的。
按增量概率随机采样：算法以随机的方式选择最终合并的社群。质量函数的增量越大，该社群被选中的概率就越高。
参数 θ 调节随机度：随机选择的程度由参数 θ > 0 控制。引入随机性能够让算法更广泛地探索划分空间，避免陷入局部最优陷阱。
高效剪枝与理论优越性：
禁止质量函数下降：算法严格排除任何会导致质量函数降低的合并操作。这与模拟退火等允许质量函数暂时下降的算法不同，提高了细化阶段在大型网络上的计算效率。
保证最优解的可达性：论文在补充信息中证明，即便排除了降低质量函数的合并，这种随机化增量合并依然能够揭示出节点集的最优划分。相反，传统的纯贪心合并由于路径固定，反而会导致某些最优划分无法被找到。
最终，在细化阶段结束后，原划分 P 中的社群通常（但并非绝对）会被精细拆分为 Prefined 中的多个子社群，为接下来的网络聚合阶段提供更高质量、完全连通的基础。
此外，Leiden 算法与 Louvain 算法在阶段一（节点局部移动）中也存在一个重要区别：
Louvain 算法的低效根源：
全网反复遍历：Louvain 在局部移动阶段会不断遍历网络中的所有节点，直到没有任何节点移动能提升质量函数为止。
存在无效计算：在这个过程中，Louvain 会大量重复访问那些邻居关系从未改变、根本不可能发生移动的节点，造成严重的时间浪费。
Leiden 的“快速局部移动”算法流程：
Leiden 借鉴了文献中的“剪枝”与“优先级排序”思想：只访问那些邻域发生了改变的节点。
队列初始化：将网络中的所有节点以随机顺序加入队列（Queue）。
节点出列评估：从队列头部取出第一个节点，评估将其移动到其他社群是否能增加质量函数。
触发邻居入列：如果该节点成功移动到了新社群，则将其所有不属于新社群且尚不在队列中的邻居节点，全部添加到队列尾部。
循环终止：持续从队列头部取出节点并评估，直到队列为空为止。
两者的运行效率对比：
第一轮访问完全一致：在算法刚开始时，Leiden 的队列中包含了全图所有节点，因此对所有节点的首次遍历与 Louvain 完全一样。
后续轮次大幅精简：首轮遍历结束后，Louvain 依然需要全图扫描，而 Leiden 仅精准访问邻域受到了影响的节点。
通过这种方式，Leiden 算法在局部移动阶段实现了比 Louvain 高得多的执行效率。
扩展思考：这里利用队列来完成增量触发与局部传播操作，与图论中 SPFA 优化 Bellman-Ford 算法的思想非常相似。在我们自己的工程实践中，是否也能借鉴这种思想？
3.2 Leiden 算法能确保什么性质？
Leiden 算法通过连续迭代的方式运行——将上一轮迭代识别出的划分结果直接作为下一轮迭代的初始起点。通过这种方式，Leiden 算法在理论上能确保以下性质：
每次迭代完成后
无论算法运行到第几轮，只要完成了一次迭代，就能保证以下两点：
所有社群均 γ-分离（γ-separated）
含义：不存在任何可以通过合并来进一步提升质量函数的社群。
与 Louvain 对比：Louvain 算法也保证此性质。
所有社群均 γ-连通（γ-connected）
含义：比普通连通性更强的一种连通属性。
与 Louvain 对比：Louvain 连普通的连通性都无法保证，因此无法保证 γ-连通性；而 Leiden 完全保证了这一点。
达到稳定迭代后
当某次迭代后划分结果不再发生改变时，该次迭代被称为“稳定迭代”。此时追加获得以下两点保证：
所有节点均局部最优分配（Locally optimally assigned）
含义：没有单个节点可以通过移动到其他社群来提升质量函数。
与 Louvain 对比：Louvain 算法在稳定迭代后也保证此性质。
所有社群都是子划分 γ-稠密的（Subpartition γ-dense）
含义：社群可以被划分为两个部分，且满足：(1) 两部分互相紧密连接；(2) 任何一部分都不能从原社群中分离出去；(3) 每一个部分本身也是“子划分 γ-稠密”的。这意味着社群内部每个节点都与所属社群保持良好的连接。
与 Louvain 对比：Louvain 算法无法保证此性质。
关于“稳定迭代”的重要机制差异：
Louvain：一旦出现 stable iteration，后续所有迭代都会保持 stable，算法无法做出任何进一步的改进。
Leiden：即使出现了 stable iteration，算法在后续的迭代中依然可能做出进一步的改进（因为引入了细化阶段的随机性）。
持续迭代收敛后
随着 Leiden 算法不断持续迭代直至完全收敛，最终能达到最顶级的理论保证：
所有社群都是一致 γ-稠密的（Uniformly γ-dense）
含义：社群中不存在任何可以被剥离/分离出去的子集。无论怎样将一个社群一分为二，这两部分始终保持紧密连接。
质量上界：论文在补充信息 Section E 中证明，当所有社群都满足均匀 γ-稠密时，整个划分的质量与全局最优划分非常接近。
所有社群都是子集最优的（Subset optimal）
含义：社群的所有子集（不仅是单个节点）都被局部最优地分配。没有任何一个子集可以通过整体移动到其他社群来提升质量函数。
最高保证：这是 Leiden 算法提供的最强理论保证。它蕴含了上述所有其他 5 项属性。
可以参见下表来直观对比 Leiden 算法与 Louvain 算法的理论保证差异：
以上性质的严格数学定义与数学推导请参见原文补充信息。这里只做直观解释。
4. 实验分析
4.1 实验概述
实验目标：
实验旨在实际验证上一节提出的理论保证（Guarantees），以及验证快速局部移动机制（Fast local move）是否确实让 Leiden 算法比 Louvain 更快。具体而言，实验在实证网络和基准网络上，从社群连通性质量、划分质量与计算时间三个维度对比两者的表现。
硬件环境与参数设置：
硬件环境：搭载 64 核 Intel Xeon E5-4667v3 2 GHz CPU 以及 1 TB 内存的高性能服务器。
核心参数 θ ：
细化阶段控制随机程度的参数 θ 在所有实验中统一设置为 0.01 ；
论文指出，θ 在大约 [0.0005, 0.1] 的区间内均能获得合理的划分结果（既引入了一定程度的随机探索，又不会引入过多噪声）。
数据集选择：
6 个真实经验网络：采用先前介绍的“智能局部移动算法”论文中的同一批网络（概况见下表）。
基准网络（Benchmark networks）：用于测试算法的可扩展性（Scaling），评估规模扩大时的时间与质量变化。
实验结论：
实证证实 Louvain 缺陷：实验结果证实，在真实的经验网络中，Louvain 算法确实会产生不连通（disconnected）以及坏连通（badly connected）的社群。
划分质量更高、耗时更短：Leiden 算法通常能够在更短的时间内找到质量更高的社群划分。
大图加速效果非常显著：在规模较大的网络中，计算时间的差异尤其明显。在真实网络测试中，Leiden 算法的运行速度最高达到了 Louvain 算法的 20 倍。
4.2 坏连通社群实验分析
作者详细说明了如何通过实证方法检测和统计 Louvain 算法在真实网络中产生的“坏连通”与“不连通（断开）”社群数量。
对于 Louvain 算法划分出的每一个社群，作者采用了以下两步检测方法：
直接检测断开状态：
直接检查社群内部是否为完全连通状态。
使用 Leiden 算法二次检测“坏连通”：
将该社群的所有节点提取出来作为一个子网络。
在该子网络上单独运行 Leiden 算法（确保子网络的模块度优化与全网的模块度优化完全一致），直到达到稳定迭代（stable iteration）。
判定标准：如果 Leiden 算法能够将该社群进一步拆分为多个子社群（subcommunities），则说明原社群属于坏连通。
作者特别强调了统计逻辑的严密性：
拆分必然提升模块度：如果 Leiden 算法能对某个社群做出拆分，那么拆分后绝对保证能够提升模块度（即证明原社群结构不合理/坏连通）。
未拆分不代表完美：反过来，即使 Leiden 在子网络上没有找到进一步拆分的方案，也不能百分之百保证拆分它就绝对无法提升模块度。
统计意义：因此，通过这种方式统计出的坏连通社群数量（包含断开社群），是真实网络中坏连通社群数量的一个下界。实际的坏连通社群比例只可能比统计值更高。
实验设置条件：
重复次数：每个经验网络上的实验均独立重复进行 10 次。
质量函数与参数：采用模块度作为质量函数，分辨率参数统一设置为 γ = 1 。
实验结果如下图所示：
第一轮迭代的初始表现：
坏连通比例高：在 Louvain 算法的第一轮迭代中，坏连通社群的比例就已经相当高。其中 Amazon 平均达到 23%，DBLP 为 16%，Web UK 为 14%。
断开社群相对较少：第一轮中完全断开的社群比例较小，通常在 1% 左右。
例外情况：Web of Science 网络在第一轮迭代中就有超过 5% 的社群处于完全断开状态。
多轮迭代加剧社群断开：
质量提升，连通恶化：随着算法继续迭代，尽管质量函数（模块度）得分在增加，但社群断开的问题显著加剧。
第二轮剧增，后续趋平：第二轮迭代时，断开社群的比例大幅上升；在此后的迭代中，该比例保持相对稳定。
网络差异：
LiveJournal 和 Web of Science 网络中断开社群比例的增长相对有限；
其他网络中，断开社群的比例出现了接近 10 倍 的增长；
DBLP 网络中的断开社群比例直接跃升至 16% 。
坏连通向断开社群的转化与最终数据对比：
坏连通社群的总比例受迭代次数影响较小。作者推测，这是因为第一轮迭代中出现的许多坏连通社群，在第二轮迭代中直接演变成了完全断开的社群，导致后续迭代中断开社群与坏连通社群的比例逐渐趋于接近。
极端网络表现：
Web UK 网络（4 次迭代后）：拥有 8% 的断开社群，而坏连通社群比例是其两倍（16%）；
Amazon 网络：拥有 5% 的断开社群，而坏连通社群的比例高达 25%。
于是可以得到以下结论：
坏连通问题的实际危害与隐蔽性：
坏连通问题被表象掩盖：在 Louvain 算法的第一轮迭代中，“完全断开”的社群比例看似较低，这于是掩盖了更根本的问题：算法产生了大量“任意坏连通”的社群。
影响规模巨大：在最坏情况下，接近四分之一 的社群都是坏连通的。
对实际领域分析的破坏性：
生物与神经科学网络：通常假设同一社群内的节点具备相似的功能或行为。如果社群坏连通，会导致对功能归因产生错误判断。
引文网络（如 Web of Science）：通常认为同一社群内的文献共享同一主题。坏连通社群会导致主题推断错误，直接影响文献计量学分析的准确性。
Leiden 算法的处理效果与“迭代反转”现象：
Leiden 算法专门为解决坏连通问题而设计，其实验表现呈现出非常有趣的迭代演进特征：
Leiden 算法保证所有社群始终是连通的，但在初始阶段仍可能包含坏连通社群。
在第一轮迭代中，Leiden 产生的坏连通社群比例甚至比 Louvain 还要高。
与 Louvain 越迭代越恶化不同，Leiden 算法的坏连通社群比例随每次迭代显著下降。
从第二轮迭代开始，Leiden 在坏连通社群比例上全面超越 Louvain。
如果持续运行迭代，Leiden 最终会收敛到一个完全没有任何坏连通社群的划分状态，解决了这一经典难题。
4.3 基准测试网络
基准网络的生成方法：
为了测试算法在不同图规模下的表现，作者采用了一种经典的基准网络生成方法的变体：
社群规模：预先设定节点数并划分社群，所有社群大小相同（文中实验设为每个社群 50 个节点；更大规模的社群实验结果在性质上类似）。
平均度数：生成边以达到指定的平均度数，设为 <k> = 10 。
边分布概率（混合参数 μ ）：
两节点位于不同社群之间连接边的概率为 μ ；
两节点位于同一社群内部连接边的概率为 1 - μ 。
网络规模跨度：节点总数 n 从 1000 个跨越到 1000 万个，用以测试海量节点下的扩展能力。
实验的严格控制变量:
相同输入与随机种子：Louvain 和 Leiden 运行在完全相同的网络上，且使用相同的随机数生成器种子。
迭代次数与重复实验：两个算法均执行 10 次迭代，且对每组参数设置重复实验 10 次 取结果。
质量函数设置：采用恒定波茨模型（CPM）作为质量函数，分辨率参数 γ 的取值基于混合参数 μ 确定。
划分质量的评估指标：
其中，H 是 CPM （具体表达式见前文），m 是网络中的总边数。
下面展示了 μ 对 Louvain 和 Leiden 划分质量差异的影响：
低 μ 值（社群结构清晰时）：
划分明确：当 μ 较小（即社群内部边密、社群间边少）时，网络中的社群界限非常明确。
表现一致：Louvain 和 Leiden 算法都非常轻松，仅需 2 次迭代就能准确识别出正确的划分。
质量无异：在此条件下，两个算法在划分质量上的差异微乎其微。
2. 高 μ 值（社群交织/界限模糊时）：
Leiden 展现优势：随着 μ 值增大（社群间连接变多，结构变得模糊），Leiden 算法开始超越 Louvain 算法，展现出更高的划分质量。
3. 质量差距并不悬殊的原因
差距有限：尽管 Leiden 更优，但两者之间的得分差距并不算非常巨大。
归因解释：作者指出，这主要是因为两个算法找到的划分质量都非常接近全局最优值。这种现象与质量函数的 “简并性” 密切相关（即存在许多结构略有不同但质量得分非常接近的划分）。
下面展示了 μ 对 Louvain 和 Leiden 运行速度差异的影响：
Leiden 算法的运行速度明显快于 Louvain 算法。
不同划分难度（ μ 值）下的速度差异：
低 μ 值（简单划分）：当 μ 较小时，正确的社群划分非常容易识别，此时 Leiden 的运行速度大约是 Louvain 的 2 倍。
高 μ 值与超大网络（困难划分）：随着 μ 值增大（划分难度增加），Leiden 的速度提升达到了多个数量级。在最大规模的网络中，Leiden 的运行速度甚至达到了 Louvain 的 10 到 100 倍。
这体现出 Leiden 算法的计算稳定性更强。
下面展示了 Louvain 与 Leiden 算法在所有迭代过程中的总运行时间与划分质量（Runtime vs. Quality）的动态权衡关系：
质量方面，Louvain 会极快地进入无法继续提升质量的状态，而 Leiden 算法能够不断寻找质量更好的划分。这种持续优化的能力在 μ 值较高（即划分难度较大）的网络中表现得尤为突出。
速度方面，在 Louvain 算法完成其第 1 轮迭代的漫长耗时里，Leiden 算法已经能够高效完成多次迭代。Louvain 后续几轮迭代虽然运行非常快，但这仅仅是因为其划分结果已经完全停滞、不再发生改变，而不是因为其单轮计算效率高。
除了唯一一个例外（除了唯一一个例外（ μ = 0.2 且 n = 107 的特定规模组合）之外，图 6 中的所有测试数据均证实：Leiden 算法在计算时间（速度）和划分质量两个维度上，全面超越了 Louvain 算法。
4.4 真实经验网络
为了模拟算法在真实世界中的效果，作者在研究中选取了 6 个真实经验网络对 Leiden 和 Louvain 算法的性能进行了对比。实验分析指标是模块度，分辨率参数统一设置为 γ = 1 。
下面研究在真实经验网络上， Leiden 和 Louvain 算法的运行速度对比。
可以发现，真实网络中，Leiden 算法的运行速度显著快于 Louvain 算法。而且网络规模越大，速度差异就越明显，这与基准网络中观察到的规律一致。
下面研究在真实经验网络上， Leiden 和 Louvain 算法的划分质量对比。
在测试的所有真实网络中，Leiden 算法识别出的社群划分质量都显著优于 Louvain 算法。而且Louvain 算法会快速收敛到一个局部状态，随后便无法做出任何进一步的质量提升。Leiden 算法则能够在每一次迭代中不断找到质量更高的划分。
下面研究真实经验网络与基准网络在收敛速度上的差异。
真实网络的复杂结构对 Leiden 的依赖更强：
质量提升更显著：相比结构简单的基准网络，Leiden 算法在真实经验网络上对划分质量的提升更为显著。
持续优化能力：基准网络通常在几轮迭代后就收敛了，但在真实的经验网络中，哪怕在 10 轮迭代之后，Leiden 算法依然能够不断找到质量更高的划分。
不同真实网络达到“稳定迭代”的难度差异：
真实网络达到首次稳定状态所需的迭代次数，直接反映了其社群结构的复杂程度：
IMDB & Amazon 网络：社群结构相对简单，算法能够相对快速地达到稳定迭代；
DBLP 网络：挑战性适中，平均需要约 80 次 迭代才能达到稳定；
Web of Science 网络：结构最复杂、最困难，平均需要 750 次以上 的迭代才能达到稳定状态。
迭代耗时的“前重后轻”规律：
作者特别强调了 Leiden 算法在多轮迭代中的计算时间特征：
首轮最重，后续极快：算法的第一轮迭代计算强度最大、最耗时，而随后的历次迭代速度都会显著加快。
具体数据（Web of Science 为例）：
第 1 轮迭代：耗时约 110–120 秒；
后续每轮迭代：耗时大幅缩短至约 40 秒。
5. 结论
社群发现是复杂网络分析中的一项重要任务。在大型网络中寻找社群绝非易事：算法既需要足够快速，又需要提供高质量的结果。使用最广泛的算法之一是 Louvain 算法，据报道，它是速度最快、性能最好的社群发现算法之一。然而，如本文所示，Louvain 算法存在一个重大缺陷：该算法生成的社群可能会出现任意程度的坏连通，社群甚至可能是完全断开（不连通）的。
为了克服社群任意坏连通的问题，作者引入了一种全新的算法，称之为 Leiden 算法。该算法提供了一系列明确的理论保证。特别地，它保证所生成的社群必定是连通的。此外，当该算法连续迭代运行演进时，它会收敛到一个划分，在该划分中，所有社群的所有子集都被保证处于局部最优分配状态。正如本文实验分析所示，在实际应用中，Leiden 算法无论是在计算速度还是在结果质量上，都令人信服地全面超越了 Louvain 算法。作者的结论是：Leiden 算法相比 Louvain 算法具有极强的优越性（强烈推荐使用 Leiden 算法取代 Louvain 算法）。