hello，大家好，之前呢医咨，分享了10X單細(xì)胞和10X空間轉(zhuǎn)錄組的降維算法，不知道大家掌握了多少架诞。今天我們來分享默認(rèn)的聚類算法Louvain拟淮，Louvain算法是目前單細(xì)胞分析中最常用的聚類算法，Seurat/Scanpy/RaceID等單細(xì)胞分析工具都默認(rèn)louvain算法谴忧，那么我們就來分享一下這個聚類算法很泊，很深的算法我們我們盡量理解，但是算法的精髓和運用必須掌握沾谓，我們用一個例子來展開委造。
社會網(wǎng)絡(luò)（social network）是是由許多節(jié)點構(gòu)成的一種社會結(jié)構(gòu)，節(jié)點通常是指個人或組織均驶，社會網(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)實生活中存在各種各樣的社會網(wǎng)絡(luò)，比如人際關(guān)系網(wǎng)逛腿、交易網(wǎng)稀并、交通運輸網(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)可以方便運營為這些社區(qū)推薦合適的商品。
算法簡介
在社交網(wǎng)絡(luò)中凌停，有的用戶之間的連接較為緊密粱年，有的用戶之間的連接關(guān)系較為稀疏，在這樣的的網(wǎng)絡(luò)中罚拟，連接較為緊密的部分可以被看成一個社區(qū)台诗，其內(nèi)部的節(jié)點之間有較為緊密的連接完箩，而在兩個社區(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)點在于速度快粱快，可以在較短時間內(nèi)實現(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ū)劃分算法能將連接比較稠密的點劃分在一個社區(qū)中，而社區(qū)之間的連接比較稀疏流炕，這樣劃分得到的網(wǎng)絡(luò)模塊度的值就會比較大澎现，模塊度越大的社區(qū)劃分算法性能越好。
——模塊度的計算
——模塊度簡單實現(xiàn)
模塊度的值在[-1,1]之間每辟，若所有的節(jié)點都被劃分到一個社區(qū)內(nèi)部剑辫，則此時模塊度為1，若所有的節(jié)點各自為一個社區(qū)渠欺，則模塊度為-1妹蔽，文章說當(dāng)模塊度的值在0.3~0.7之間則說明社區(qū)劃分算法的效果很好，Louvain算法的優(yōu)化目標(biāo)為最大化整個數(shù)據(jù)的模塊度挠将。
算法簡介
louvain算法原理
——louvain算法的兩個階段
第一階段——先令每個節(jié)點自己屬于一個社區(qū)胳岂，此時網(wǎng)絡(luò)中有幾個節(jié)點便有幾個社區(qū)，計算此時的模塊度舔稀，然后令節(jié)點i不再屬于自己而是和節(jié)點j一個社區(qū)乳丰，計算此時的模塊度，兩個步驟就使得此時的網(wǎng)絡(luò)出現(xiàn)了模塊度增量内贮，則模塊劃分方法就是將i節(jié)點劃分到使模塊度增量最大且大于0的那個節(jié)點中去产园；
第二階段——將第一階段劃分出來的社區(qū)聚合為一個節(jié)點，重構(gòu)整個網(wǎng)絡(luò)夜郁；
louvain算法的步驟
——模塊度增量
算法實現(xiàn)
算法實現(xiàn)
算法流程
算法實現(xiàn)
代碼詳解
——計算模塊度
——計算模塊度增量
——社區(qū)聚合
算法實現(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)良。
實例運用
《權(quán)力的游戲》，是美國HBO電視網(wǎng)制作推出的一部中世紀(jì)史詩奇幻題材的電視劇技俐。該劇改編自美國作家喬治·R·R·馬丁的奇幻小說《冰與火之歌》系列乘陪。16年數(shù)學(xué)家 Andrew Beveridge和Jie Shan分析了小說《冰與火之歌》第三部《冰雨的風(fēng)暴》中人物關(guān)系。在文章中介紹了如何通過文本分析和實體提取構(gòu)建人物關(guān)系的網(wǎng)絡(luò)虽另，并使用社交網(wǎng)絡(luò)分析算法對人物關(guān)系網(wǎng)絡(luò)分析找出最重要的角色暂刘，最后應(yīng)用社區(qū)發(fā)現(xiàn)算法來找到人物聚類。其中可視化是利用igraph實現(xiàn)捂刺，社區(qū)發(fā)現(xiàn)則是利用igraph中實現(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算法運用到上面仪缸，進(jìn)行社區(qū)發(fā)現(xiàn)并且將劃分的子網(wǎng)絡(luò)通過網(wǎng)絡(luò)圖中不同的色彩標(biāo)示出來贵涵。
實例運用
數(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ù)據(jù)可視化
實例運用
調(diào)用Louvain算法
——算法調(diào)用及劃分結(jié)果局部展示
——劃分后的模塊度
前面我們說過當(dāng)模塊度的值為0.3-0.7則表示社區(qū)劃分的效果比較好端盆，可見這里的劃分結(jié)果為0.5999說明劃分效果很好。
實例運用
社區(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)錄組都是運用一樣的原理果复，由此顯示了我們單細(xì)胞的聚類，從而運用到下游分析
但是渤昌，目前這個算法已經(jīng)暴露了很多不合適的地方虽抄，最新的算法leiden慢慢替換了louvain走搁，我們下一篇分享louvain的算法缺陷和leiden的算法原理。
生活很好迈窟，有你更好
