hello苛秕，大家好城看，今天我們來分享一下最新常用的聚類算法----leiden潘飘，其實(shí)大家在看Seurat的函數(shù)FindClusters可能會觀察到乐严，其中有一個參數(shù)algorithm瘤袖，有4個可選項，我們列舉出來
1 = original Louvain algorithm（原始Louvain算法 ）
2 = Louvain algorithm with multilevel refinement（具有多級細(xì)化的Louvain算法 ）
3 = SLM algorithm（SLM算法昂验，關(guān)于這個算法大家可以參考文章Neo4j：SLM群集算法的過程,我會在后續(xù)分享的文章中提到這個算法）捂敌。
4 = Leiden algorithm（leiden算法，這是我們今天分享的重點(diǎn)）既琴。
在軟件scanpy的運(yùn)行函數(shù)中占婉，原來的聚類函數(shù)sc.tl.louvain也被函數(shù)sc.tl.leiden取代，可見更大范圍上甫恩，leiden算法比louvain更為合適锐涯。
其中關(guān)于louvain的算法，在我分享的文章10X單細(xì)胞（10X空間轉(zhuǎn)錄組）聚類算法之Louvain填物，詳細(xì)介紹過纹腌，大家可以參考霎终，而今天我們的內(nèi)容，就從louvain和leiden的關(guān)系開始升薯。
首先來總結(jié)一下louvain的缺點(diǎn)：
1莱褒、社區(qū)劃分的精度有局限性
2知牌、分組內(nèi)細(xì)胞分布密度的大小會影響亞群的鑒定
3叉趣、被鑒定為同一個分群的細(xì)胞群內(nèi)削饵，存在兩個沒有連線的小分群
Leiden算法主要針對上述的第3個缺點(diǎn)蛉幸，對louvain算法進(jìn)行優(yōu)化啼肩。Leiden算法的命名來源于荷蘭萊頓大學(xué)(Leiden University)亭敢。該算法由萊頓大學(xué)的三位研究員開發(fā)倚喂，結(jié)果于2020年3月份發(fā)表在Scientific Reports上嫁乘。
總結(jié)Leiden算法優(yōu)化louvain的兩個要點(diǎn)：
比louvain算法運(yùn)行更快蹦浦。
針對louvain聚類結(jié)果中出現(xiàn)一些分群內(nèi)部存在斷鏈的現(xiàn)象(連線沒有把所有細(xì)胞串起來扭吁，存在明顯亞群)進(jìn)行優(yōu)化，分群更加合理盲镶，可能得到更多亞群侥袜。
圖解leiden算法的操作過程
再分享深入的算法之前，我們先來舉一個例子
我們可以把聚類過程當(dāng)作體育課的一場游戲溉贿。
學(xué)生是細(xì)胞枫吧，在操場上站隊(聚類)。
模塊度是體育老師宇色，檢查學(xué)生站隊是否合理九杂。
連線(細(xì)胞間權(quán)重)表示學(xué)生之間有一定的關(guān)系，比如同班同學(xué)宣蠕，身高一致等尼酿。
經(jīng)過學(xué)生的一陣騷動(初始劃分聚類)之后，初始的隊伍出來了植影，分成的三個隊伍：
這時體育老師出來裳擎，看了看整體隊形(模塊度給聚類結(jié)果打分)，感覺還不行(模塊度分?jǐn)?shù)偏低)思币，需要調(diào)整分組站隊鹿响。
Leiden和louvain算法的調(diào)整策略不同(leiden優(yōu)化的要點(diǎn)一)：
- Louvain：讓每個同學(xué)去另外兩個隊伍，每次換隊伍都讓體育老師評價一下谷饿；
2. Leiden：只讓每個同學(xué)去有連線的其他隊伍惶我，節(jié)省時間。
當(dāng)害羞同學(xué)從紅隊調(diào)整到綠隊時博投，體育老師發(fā)現(xiàn)隊形變好看了(模塊度打分提高了)绸贡。因為紅隊身高整體比綠隊高，害羞同學(xué)比較矮，適合綠隊听怕。害羞同學(xué)剛開始站在紅隊捧挺，是因為她跟紅隊是同班同學(xué)。
但害羞同學(xué)離開紅隊之后尿瞭，問題就來了闽烙。紅隊內(nèi)部出現(xiàn)左右兩個沒有連線的小隊：耶小隊和奸笑小隊。Louvain算法沒有檢測這種內(nèi)部斷鏈的現(xiàn)象声搁。盡管紅隊都是同班同學(xué)黑竞，但內(nèi)部還是有身高的差異，耶小隊比奸笑小隊普遍矮小疏旨。之前不高不矮的害羞同學(xué)在的時候很魂，還能起到內(nèi)部過渡的作用。當(dāng)害羞同學(xué)離開之后檐涝，紅隊內(nèi)部出現(xiàn)兩極化遏匆。
幸虧體育老師提前備課，看了leiden算法骤铃，及時將紅隊分開。(leiden優(yōu)化要點(diǎn)二)
下課鈴聲響起坷剧，體育老師手握Leiden書惰爬，看著同學(xué)們完美的隊形，露出了滿意的微笑惫企。
那么接下來撕瞧，我們就要進(jìn)入深刻的leiden算法環(huán)節(jié)了。
簡單回顧一下Louvain Algorithm
對比一下leiden算法
We here introduce the Leiden algorithm, which guarantees that communities are well connected. The Leiden algorithm is partly based on the previously introduced smart local move algorithm, which itself can be seen as an improvement of the Louvain algorithm. The Leiden algorithm also takes advantage of the idea of speeding up the local moving of nodes and the idea of moving nodes to random neighbours. We consider these ideas to represent the most promising directions in which the Louvain algorithm can be improved, even though we recognise that other improvements have been suggested as well. The Leiden algorithm consists of three phases: (1) local moving of nodes, (2) refinement of the partition and (3) aggregation of the network based on the refined partition, using the non-refined partition to create an initial partition for the aggregate network. The Leiden algorithm is considerably more complex than the Louvain algorithm. Figure 3（下圖） provides an illustration of the algorithm.
we show that the Louvain algorithm has a major problem, for both modularity and CPM. The algorithm may yield arbitrarily badly connected communities, over and above the well-known issue of the resolution limit. Communities may even be internally disconnected. To address this important shortcoming, we introduce a new algorithm that is faster, finds better partitions and provides explicit guarantees and bounds. The new algorithm integrates several earlier improvements, incorporating a combination of smart local move, fast local move and random neighbour move. We prove that the new algorithm is guaranteed to produce partitions in which all communities are internally connected. In addition, we prove that the algorithm converges to an asymptotically stable partition in which all subsets of all communities are locally optimally assigned. The quality of such an asymptotically stable partition provides an upper bound on the quality of an optimal partition. Finally, we demonstrate the excellent performance of the algorithm for several benchmark and real-world networks. To ensure readability of the paper to the broadest possible audience, we have chosen to relegate all technical details to the Supplementary Information. The main ideas of our algorithm are explained in an intuitive way in the main text of the paper. We name our algorithm the Leiden algorithm狞尔。
好了丛版，就分享這么多了，大家多多學(xué)習(xí)
生活很好偏序，有你更好
