簡(jiǎn)介
Louvain算法[1]是一種基于多層次優(yōu)化Modularity[2]的算法壶冒，它的優(yōu)點(diǎn)是快速巫糙、準(zhǔn)確旦签，被[3]認(rèn)為是性能最好的社區(qū)發(fā)現(xiàn)算法之一。Modularity函數(shù)最初被用于衡量社區(qū)發(fā)現(xiàn)算法結(jié)果的質(zhì)量肪跋，它能夠刻畫發(fā)現(xiàn)的社區(qū)的緊密程度歧蒋。那么既然能刻畫社區(qū)的緊密程度，也就能夠被用來(lái)當(dāng)作一個(gè)優(yōu)化函數(shù)州既，即將結(jié)點(diǎn)加入它的某個(gè)鄰居所在的社區(qū)中疏尿，如果能夠提升當(dāng)前社區(qū)結(jié)構(gòu)的modularity。</br>
Modularity的定義如下：
其中易桃，m表示網(wǎng)絡(luò)中邊的數(shù)量，A為鄰接矩陣锌俱，如果ci,cj相同則$\delta(ci,cj)$＝1否則為0晤郑。</br>
如果當(dāng)前結(jié)點(diǎn)所在的社區(qū)只有它自己，那么在計(jì)算將它加入到其它社區(qū)時(shí)的modularity的變化有個(gè)技巧來(lái)加速計(jì)算贸宏，Louvain的高效性也在一定程度上受益于此造寝，它為:
</br>
Louvain算法包括兩個(gè)階段，在步驟一它不斷地遍歷網(wǎng)絡(luò)中的結(jié)點(diǎn)吭练，嘗試將單個(gè)結(jié)點(diǎn)加入能夠使modularity提升最大的社區(qū)中诫龙，直到所有結(jié)點(diǎn)都不再變化。在步驟二鲫咽，它處理第一階段的結(jié)果签赃，將一個(gè)個(gè)小的社區(qū)歸并為一個(gè)超結(jié)點(diǎn)來(lái)重新構(gòu)造網(wǎng)絡(luò)，這時(shí)邊的權(quán)重為兩個(gè)結(jié)點(diǎn)內(nèi)所有原始結(jié)點(diǎn)的邊權(quán)重之和分尸。迭代這兩個(gè)步驟直至算法穩(wěn)定锦聊。它的執(zhí)行流程如圖所示：
</br>
## ****代碼實(shí)現(xiàn)
GraphX是Spark上的一個(gè)圖處理框架，它在RDD的基礎(chǔ)之上封裝出VertexRDD以及EdgeRDD箩绍，由這兩個(gè)封裝出的RDD便可構(gòu)成圖結(jié)構(gòu)孔庭，詳細(xì)請(qǐng)見官網(wǎng)：
GraphX實(shí)現(xiàn)
Python實(shí)現(xiàn)參見
## ****文獻(xiàn)
1: Fast unfolding of communities in large networks
2: Finding community structure in very large networks
3: Community detection algorithms: A comparative analysis
