Louvain 算法來源于文章2010年的論文Fast unfolding of communities in large networks，簡稱為Louvian [1]。

算法原理

Louvain算法是基于模塊度(Modularity)的社區(qū)發(fā)現(xiàn)算法，該算法在效率和效果上都表現(xiàn)比較好，并且能夠發(fā)現(xiàn)層次性的社區(qū)結(jié)構(gòu)，其優(yōu)化的目標是最大化整個圖屬性結(jié)構(gòu)(社區(qū)網(wǎng)絡(luò))的模塊度。

其中需要理解的核心點有：

模塊度Modularity的定義，這個定義是描述社區(qū)內(nèi)緊密程度的值QQ；

模塊度增量ΔQ\Delta Q，即把一個孤立的點放入一個社區(qū)C后，計算Modularity的變化，其中計算過程的要點是，首先計算1個點的Modularity，和社區(qū)C的Modularity，再計算合并后新社區(qū)的Modularity，新社區(qū)的Modularity減去前兩個Modularity就是ΔQ\Delta Q。

對上述公式的理解是，將ΔQ\Delta Q展開其等價于1/2*(ki,in/m-Sumtot/m*ki/m)1/2 *( k_i,in / m - Sum_{tot} / m * ki / m )，其中kik_i,in/min/m表示的是將孤立的節(jié)點和社區(qū)C放在一起對整個網(wǎng)絡(luò) Modularity 的影響，而?Sumtot/mSum_{tot} / m 和?ki/mki / m?分別表示孤立的節(jié)點和社區(qū)C分開式分別對整個網(wǎng)絡(luò)Modularity的影響，所以他們的差值就反應(yīng)了孤立的節(jié)點放入社區(qū)C前后對整個網(wǎng)絡(luò)Modularity的影響。

算法的計算過程如下：每個點作為一個community，然后考慮每個community的鄰居節(jié)點，合并到community，然后看ΔQ\Delta Q；找到最大的正ΔQ\Delta Q，合并點到community；多進行幾輪，至不再變動，那么結(jié)束；

其中存在的問題是，不同的節(jié)點訪問順序?qū)е虏煌慕Y(jié)果，實驗中發(fā)現(xiàn)這個順序?qū)Y(jié)果影響不大，但是會在一定程度上影響計算時間。將新的community作為點，重復上述過程。那么如何確定新的點之前的權(quán)重呢？答案是將兩個community之間相鄰的點之間的權(quán)重和作為兩個community退化成一個點后的新的權(quán)重。

該算法的優(yōu)點主要有3個：

易于理解

非監(jiān)督

計算快速

最后我們可以得到的結(jié)果是層次化的社區(qū)發(fā)現(xiàn)結(jié)果。

Figure 1 Louvain結(jié)果示意圖1

Figure 2?Louvain結(jié)果示意圖2

算法的改進: 還有其加速實現(xiàn)的論文，例如[2], 其實現(xiàn)方式比較直接，就是考慮一個點周圍的百分之多少點進行歸并。可以在spark下面通過類似于多路歸并來實現(xiàn)。

參考資料：

總結(jié)

以上是生活随笔為你收集整理的louvain算法python_【转载】LOUVAIN算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。