Louvain算法是目前单细胞分析中最常用的聚类算法[1]，Seurat/Scanpy/RaceID等单细胞分析工具都默认louvain算法。6天前HumanCell Atlas(HCA)团队发表在Nature Method上的单细胞分析流程中[2]，默认的聚类算法是scran包的方法：细胞间权重基于排序计算（rank-based），聚类算法用Walktrap。这跟杰卡德距离+Louvain算法的方法截然不同。

    聚类算法孰优孰劣，此前已经有人做过比较。2016年Scientific Reports上有一篇文章比较了igraph包里的8种聚类算法，其中包括了Louvain和Walktrap[3]。测试结果的准确率Louvain和Walktrap相近。但是，当节点数（细胞数）大于6000时，Louvain的表现要优于Walktrap。

    总结评测结果，Louvain算法表现是最好的。但仍有不少文章选择其他聚类算法，因为louvain算法有以下几个缺点：

    1. 社区划分的精度有局限性[4]；
    2. 分组内细胞分布密度的大小会影响亚群的鉴定[2];
    3. 被鉴定为同一个分群的细胞群内，存在两个没有连线的小分群[5]。

    Leiden算法主要针对上述的第3个缺点，对louvain算法进行优化[5]。
    Leiden算法的命名来源于荷兰莱顿大学（Leiden University）。该算法由莱顿大学的三位研究员开发，结果于今年3月份发表在Scientific Reports上。
    单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图1

    想了解louvain算法的聚类过程，可以回顾往期文章：
    单细胞聚类（二）社区划分与模块度
    总结Leiden算法优化louvain的两个要点：

    1. 比louvain算法运行更快。
    2. 针对louvain聚类结果中出现一些分群内部存在断链的现象（连线没有把所有细胞串起来，存在明显亚群）进行优化，分群更加合理，可能得到更多亚群。

    单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图2

    图解leiden算法的操作过程
    我们可以把聚类过程当作体育课的一场游戏。
    学生是细胞，在操场上站队（聚类）。
    模块度是体育老师，检查学生站队是否合理。
    连线（细胞间权重）表示学生之间有一定的关系，比如同班同学，身高一致等。
    单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图3

    经过学生的一阵骚动（初始划分聚类）之后，初始的队伍出来了，分成的三个队伍：
    单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图4

    这时体育老师出来，看了看整体队形（模块度给聚类结果打分），感觉还不行（模块度分数偏低），需要调整分组站队。

    Leiden和louvain算法的调整策略不同（leiden优化的要点一）：

    1. Louvain：让每个同学去另外两个队伍，每次换队伍都让体育老师评价一下；
    2. Leiden：只让每个同学去有连线的其他队伍，节省时间。

    当害羞同学单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图5从红队调整到绿队时，体育老师发现队形变好看了（模块度打分提高了）。因为红队身高整体比绿队高，害羞同学单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图6比较矮，适合绿队。害羞同学刚开始站在红队，是因为她跟红队是同班同学。

    单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图7

    但害羞同学单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图8离开红队之后，问题就来了。红队内部出现左右两个没有连线的小队：耶小队单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图9和奸笑小队单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图10。Louvain算法没有检测这种内部断链的现象。尽管红队都是同班同学，但内部还是有身高的差异，耶小队单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图11比奸笑小队单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图12普遍矮小。之前不高不矮的害羞同学单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图13在的时候，还能起到内部过渡的作用。当害羞同学单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图14离开之后，红队内部出现两极化。

    单细胞聚类（四）图解Leiden算法对Louvain算法的优化 - 图15
    幸亏体育老师提前备课，看了leiden算法，及时将红队分开。（leiden优化要点二）

    下课铃声响起，体育老师手握Leiden书，看着同学们完美的队形，露出了满意的微笑。

    如果您对相关内容感兴趣，欢迎关注本公众号：“单细胞组学”。
    如果您对内容满意，欢迎点击右下角 “在看”，让更多感兴趣的朋友看到！
    感谢！

    参考文献：
    [1] Blondel,Vincent D., et al. “Fast unfolding of communities in large networks.” Journal of statisticalmechanics: theory and experiment 2008.10 (2008): P10008.
    [2] AmezquitaR A, Lun A T L, Becht E, et al. Orchestrating single-cell analysis withBioconductor[J]. Nature Methods, 2019: 1-9.
    [3] YangZ, Algesheimer R, Tessone C J. A comparative analysis of community detectionalgorithms on artificial networks[J]. Scientific reports, 2016, 6: 30750.
    [4] FortunatoS, Barthelemy M. Resolution limit in community detection[J]. Proceedings of thenational academy of sciences, 2007, 104(1): 36-41.
    [5] Traag,Vincent A., Ludo Waltman, and Nees Jan van Eck. “From Louvain to Leiden:guaranteeing well-connected communities.” Scientific reports 9 (2019).