??? Louvain算法是目前單細胞分析中最常用的聚類算法[1]，Seurat/Scanpy/RaceID等單細胞分析工具都默認louvain算法。6天前HumanCell Atlas(HCA)團隊發(fā)表在Nature Method上的單細胞分析流程中[2]，默認的聚類算法是scran包的方法：細胞間權重基于排序計算(rank-based)，聚類算法用Walktrap。這跟杰卡德距離+Louvain算法的方法截然不同。

???????聚類算法孰優(yōu)孰劣，此前已經(jīng)有人做過比較。2016年Scientific Reports上有一篇文章比較了igraph包里的8種聚類算法，其中包括了Louvain和Walktrap[3]。測試結(jié)果的準確率Louvain和Walktrap相近。但是，當節(jié)點數(shù)(細胞數(shù))大于6000時，Louvain的表現(xiàn)要優(yōu)于Walktrap。

????總結(jié)評測結(jié)果，Louvain算法表現(xiàn)是最好的。但仍有不少文章選擇其他聚類算法，因為louvain算法有以下幾個缺點：

社區(qū)劃分的精度有局限性[4]；

分組內(nèi)細胞分布密度的大小會影響亞群的鑒定[2];

被鑒定為同一個分群的細胞群內(nèi)，存在兩個沒有連線的小分群[5]。

??? Leiden算法主要針對上述的第3個缺點，對louvain算法進行優(yōu)化[5]。

??? Leiden算法的命名來源于荷蘭萊頓大學(Leiden University)。該算法由萊頓大學的三位研究員開發(fā)，結(jié)果于今年3月份發(fā)表在Scientific Reports上。

想了解louvain算法的聚類過程，可以回顧往期文章：

?單細胞聚類(二)社區(qū)劃分與模塊度

總結(jié)Leiden算法優(yōu)化louvain的兩個要點：

比louvain算法運行更快。

針對louvain聚類結(jié)果中出現(xiàn)一些分群內(nèi)部存在斷鏈的現(xiàn)象(連線沒有把所有細胞串起來，存在明顯亞群)進行優(yōu)化，分群更加合理，可能得到更多亞群。

圖解leiden算法的操作過程

我們可以把聚類過程當作體育課的一場游戲。

學生是細胞，在操場上站隊(聚類)。

模塊度是體育老師，檢查學生站隊是否合理。

連線(細胞間權重)表示學生之間有一定的關系，比如同班同學，身高一致等。

????經(jīng)過學生的一陣騷動(初始劃分聚類)之后，初始的隊伍出來了，分成的三個隊伍：

??????這時體育老師出來，看了看整體隊形(模塊度給聚類結(jié)果打分)，感覺還不行(模塊度分數(shù)偏低)，需要調(diào)整分組站隊。

Leiden和louvain算法的調(diào)整策略不同(leiden優(yōu)化的要點一)：

Louvain：讓每個同學去另外兩個隊伍，每次換隊伍都讓體育老師評價一下；

Leiden：只讓每個同學去有連線的其他隊伍，節(jié)省時間。

????????當害羞同學從紅隊調(diào)整到綠隊時，體育老師發(fā)現(xiàn)隊形變好看了(模塊度打分提高了)。因為紅隊身高整體比綠隊高，害羞同學比較矮，適合綠隊。害羞同學剛開始站在紅隊，是因為她跟紅隊是同班同學。

????????但害羞同學離開紅隊之后，問題就來了。紅隊內(nèi)部出現(xiàn)左右兩個沒有連線的小隊：耶小隊和奸笑小隊。Louvain算法沒有檢測這種內(nèi)部斷鏈的現(xiàn)象。盡管紅隊都是同班同學，但內(nèi)部還是有身高的差異，耶小隊比奸笑小隊普遍矮小。之前不高不矮的害羞同學在的時候，還能起到內(nèi)部過渡的作用。當害羞同學離開之后，紅隊內(nèi)部出現(xiàn)兩極化。

????????幸虧體育老師提前備課，看了leiden算法，及時將紅隊分開。(leiden優(yōu)化要點二)

????下課鈴聲響起，體育老師手握Leiden書，看著同學們完美的隊形，露出了滿意的微笑。

如果您對相關內(nèi)容感興趣，歡迎關注本公眾號：“單細胞組學”。

如果您對內(nèi)容滿意，歡迎點擊右下角 “在看”，讓更多感興趣的朋友看到！

感謝！

參考文獻：

[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).

總結(jié)

以上是生活随笔為你收集整理的louvain算法_单细胞聚类（四）图解Leiden算法对Louvain算法的优化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。