hello，大家好，之前呢，分享了10X單細(xì)胞和10X空間轉(zhuǎn)錄組的降維算法，不知道大家掌握了多少。今天我們來分享默認(rèn)的聚類算法Louvain，Louvain算法是目前單細(xì)胞分析中最常用的聚類算法，Seurat/Scanpy/RaceID等單細(xì)胞分析工具都默認(rèn)louvain算法，那么我們就來分享一下這個聚類算法，很深的算法我們我們盡量理解，但是算法的精髓和運(yùn)用必須掌握，我們用一個例子來展開。
社會網(wǎng)絡(luò)（social network）是是由許多節(jié)點(diǎn)構(gòu)成的一種社會結(jié)構(gòu)，節(jié)點(diǎn)通常是指個人或組織，社會網(wǎng)絡(luò)代表各種社會關(guān)系，社會網(wǎng)絡(luò)關(guān)注的是人們之間的互動和聯(lián)系,社會互動會影響人們的社會行為。對于社交網(wǎng)絡(luò)的分析和研究范圍很廣，例如在社交網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)、基于好友關(guān)系為用戶推薦商品或內(nèi)容、社交網(wǎng)絡(luò)中人物影響力的計算、信息在社交網(wǎng)絡(luò)上的傳播模型、虛假信息和機(jī)器人賬號的識別、基于社交網(wǎng)絡(luò)信息對股市、大選以及互聯(lián)網(wǎng)金融行業(yè)中的反欺詐預(yù)測等。
現(xiàn)實(shí)生活中存在各種各樣的社會網(wǎng)絡(luò)，比如人際關(guān)系網(wǎng)、交易網(wǎng)、交通運(yùn)輸網(wǎng)等，對這些網(wǎng)絡(luò)進(jìn)行社區(qū)發(fā)現(xiàn)（community detection）具有極大的意義，如在微博構(gòu)成的人際關(guān)系網(wǎng)絡(luò)中，可以發(fā)現(xiàn)出具有不同興趣愛好、背景的社會團(tuán)體，方便進(jìn)行不同的宣傳策略和投放不同的廣告；在以淘寶為代表的交易網(wǎng)中，不同的社區(qū)代表不同購買力的客戶群體，社區(qū)發(fā)現(xiàn)可以方便運(yùn)營為這些社區(qū)推薦合適的商品。
算法簡介
在社交網(wǎng)絡(luò)中，有的用戶之間的連接較為緊密，有的用戶之間的連接關(guān)系較為稀疏，在這樣的的網(wǎng)絡(luò)中，連接較為緊密的部分可以被看成一個社區(qū)，其內(nèi)部的節(jié)點(diǎn)之間有較為緊密的連接，而在兩個社區(qū)間則相對連接較為稀疏，這便稱為社團(tuán)結(jié)構(gòu)。
Louvain算法來自于Vincent等人發(fā)表的文章《Fast unfolding of communities in large networks》，是基于模塊度（modularity）進(jìn)行社區(qū)發(fā)現(xiàn)，該算法的優(yōu)點(diǎn)在于速度快，可以在較短時間內(nèi)實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)以不同粒度的社區(qū)劃分（這個就對應(yīng)我們的Seurat的聚類參數(shù)resolution），并且無需指定社區(qū)的數(shù)量，當(dāng)模塊度不再增益時候，迭代便自動停止。
Louvain算法處理大量數(shù)據(jù)的結(jié)果示例
算法簡介
模塊度基本原理
Newman等人在文章《Finding and evaluating community structure in networks》中提出了模塊度（modularity）的概念，用來衡量社區(qū)劃分的好壞。簡單講，如果一個社區(qū)劃分算法能將連接比較稠密的點(diǎn)劃分在一個社區(qū)中，而社區(qū)之間的連接比較稀疏，這樣劃分得到的網(wǎng)絡(luò)模塊度的值就會比較大，模塊度越大的社區(qū)劃分算法性能越好。
——模塊度的計算
——模塊度簡單實(shí)現(xiàn)
模塊度的值在[-1,1]之間，若所有的節(jié)點(diǎn)都被劃分到一個社區(qū)內(nèi)部，則此時模塊度為1，若所有的節(jié)點(diǎn)各自為一個社區(qū)，則模塊度為-1，文章說當(dāng)模塊度的值在0.3~0.7之間則說明社區(qū)劃分算法的效果很好，Louvain算法的優(yōu)化目標(biāo)為最大化整個數(shù)據(jù)的模塊度。
算法簡介
louvain算法原理
——louvain算法的兩個階段
第一階段——先令每個節(jié)點(diǎn)自己屬于一個社區(qū)，此時網(wǎng)絡(luò)中有幾個節(jié)點(diǎn)便有幾個社區(qū)，計算此時的模塊度，然后令節(jié)點(diǎn)i不再屬于自己而是和節(jié)點(diǎn)j一個社區(qū)，計算此時的模塊度，兩個步驟就使得此時的網(wǎng)絡(luò)出現(xiàn)了模塊度增量，則模塊劃分方法就是將i節(jié)點(diǎn)劃分到使模塊度增量最大且大于0的那個節(jié)點(diǎn)中去；
第二階段——將第一階段劃分出來的社區(qū)聚合為一個節(jié)點(diǎn)，重構(gòu)整個網(wǎng)絡(luò)；
louvain算法的步驟
——模塊度增量
算法實(shí)現(xiàn)
算法實(shí)現(xiàn)
算法流程
算法實(shí)現(xiàn)
代碼詳解
——計算模塊度
——計算模塊度增量
——社區(qū)聚合
算法實(shí)現(xiàn)
算法測試
——數(shù)據(jù)導(dǎo)入
——測試結(jié)果
根據(jù)louvain算法結(jié)果，一共將數(shù)據(jù)“polbooks.gml”劃分成4個社區(qū)，劃分后網(wǎng)絡(luò)的模塊度為0.52，在0.3~0.7之間，可見劃分結(jié)果還是比較優(yōu)良。
實(shí)例運(yùn)用
《權(quán)力的游戲》，是美國HBO電視網(wǎng)制作推出的一部中世紀(jì)史詩奇幻題材的電視劇。該劇改編自美國作家喬治·R·R·馬丁的奇幻小說《冰與火之歌》系列。16年數(shù)學(xué)家 Andrew Beveridge和Jie Shan分析了小說《冰與火之歌》第三部《冰雨的風(fēng)暴》中人物關(guān)系。在文章中介紹了如何通過文本分析和實(shí)體提取構(gòu)建人物關(guān)系的網(wǎng)絡(luò)，并使用社交網(wǎng)絡(luò)分析算法對人物關(guān)系網(wǎng)絡(luò)分析找出最重要的角色，最后應(yīng)用社區(qū)發(fā)現(xiàn)算法來找到人物聚類。其中可視化是利用igraph實(shí)現(xiàn)，社區(qū)發(fā)現(xiàn)則是利用igraph中實(shí)現(xiàn)的walktrap方法。劃分結(jié)果：
7 大子網(wǎng)絡(luò)陣營
在這里，本文利用權(quán)利的游戲中角色之間的聯(lián)系緊密產(chǎn)能度收集到的數(shù)據(jù)集，內(nèi)含兩個角色的名字和相互之間對應(yīng)的權(quán)重，利這個數(shù)據(jù)進(jìn)行簡單的可視化工作，并且將louvain算法運(yùn)用到上面，進(jìn)行社區(qū)發(fā)現(xiàn)并且將劃分的子網(wǎng)絡(luò)通過網(wǎng)絡(luò)圖中不同的色彩標(biāo)示出來。
實(shí)例運(yùn)用
數(shù)據(jù)獲取
——NetworkX
是用Python語言開發(fā)的圖論與復(fù)雜網(wǎng)絡(luò)建模工具，內(nèi)置常用的圖與復(fù)雜網(wǎng)絡(luò)分析算法，可以方便的進(jìn)行復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)分析、仿真建模等工作；支持創(chuàng)建無向圖、有向圖和多重圖；
示例：
——community
是使用louvain方法進(jìn)行社區(qū)發(fā)現(xiàn)的模塊，在安裝庫的時候注意使用“pip install python-louvain”進(jìn)行安裝。
示例：
實(shí)例運(yùn)用
數(shù)據(jù)可視化
實(shí)例運(yùn)用
調(diào)用Louvain算法
——算法調(diào)用及劃分結(jié)果局部展示
——劃分后的模塊度
前面我們說過當(dāng)模塊度的值為0.3-0.7則表示社區(qū)劃分的效果比較好，可見這里的劃分結(jié)果為0.5999說明劃分效果很好。
實(shí)例運(yùn)用
社區(qū)發(fā)現(xiàn)結(jié)果可視化
看過《權(quán)游》的人應(yīng)該知道Cersei（瑟后）、Tyrion（小指頭）和Jamie（弒君者）三人是姐弟關(guān)系，其他人物例如Aerys（瘋王）、Tywin（瑟后他爹）、Oberyn（紅毒蛇）、Gregor（魔山），這些都是以Cersei為中心的人物關(guān)系，而我們的社區(qū)發(fā)現(xiàn)算法也成功的將他們劃分到了一個社區(qū)里面，可見louvain算法不僅速度快，而且劃分的準(zhǔn)確性也比較高。
當(dāng)然，這里只是一個例子，10X單細(xì)胞和10X空間轉(zhuǎn)錄組都是運(yùn)用一樣的原理，由此顯示了我們單細(xì)胞的聚類，從而運(yùn)用到下游分析
但是，目前這個算法已經(jīng)暴露了很多不合適的地方，最新的算法leiden慢慢替換了louvain，我們下一篇分享louvain的算法缺陷和leiden的算法原理。
生活很好，有你更好
