簡介

Louvain算法[1]是一種基于多層次優(yōu)化Modularity[2]的算法，它的優(yōu)點是快速、準(zhǔn)確，被[3]認為是性能最好的社區(qū)發(fā)現(xiàn)算法之一。Modularity函數(shù)最初被用于衡量社區(qū)發(fā)現(xiàn)算法結(jié)果的質(zhì)量，它能夠刻畫發(fā)現(xiàn)的社區(qū)的緊密程度。那么既然能刻畫社區(qū)的緊密程度，也就能夠被用來當(dāng)作一個優(yōu)化函數(shù)，即將結(jié)點加入它的某個鄰居所在的社區(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é)點所在的社區(qū)只有它自己，那么在計算將它加入到其它社區(qū)時的modularity的變化有個技巧來加速計算，Louvain的高效性也在一定程度上受益于此，它為:

</br>

Louvain算法包括兩個階段，在步驟一它不斷地遍歷網(wǎng)絡(luò)中的結(jié)點，嘗試將單個結(jié)點加入能夠使modularity提升最大的社區(qū)中，直到所有結(jié)點都不再變化。在步驟二，它處理第一階段的結(jié)果，將一個個小的社區(qū)歸并為一個超結(jié)點來重新構(gòu)造網(wǎng)絡(luò)，這時邊的權(quán)重為兩個結(jié)點內(nèi)所有原始結(jié)點的邊權(quán)重之和。迭代這兩個步驟直至算法穩(wěn)定。它的執(zhí)行流程如圖所示：

</br>

## ****代碼實現(xiàn)
GraphX是Spark上的一個圖處理框架，它在RDD的基礎(chǔ)之上封裝出VertexRDD以及EdgeRDD，由這兩個封裝出的RDD便可構(gòu)成圖結(jié)構(gòu)，詳細請見官網(wǎng)：

GraphX實現(xiàn)
Python實現(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