LOUVAIN——社交網(wǎng)絡(luò)挖掘之大規(guī)模網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)算法

===

算法來源

該算法來源于文章Fast unfolding of communities in large networks，簡稱為Louvian。

算法原理

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

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

• a、模塊度Modularity的定義，這個定義是描述社區(qū)內(nèi)緊密程度的值Q；
• b、模塊度增量delta Q，即把一個孤立的點放入一個社區(qū)C后，計算Modularity的變化，其中計算過程的要點是，首先計算1個點的Modularity，和社區(qū)C的Modularity，再計算合并后新社區(qū)的Modularity，新社區(qū)的Modularity減去前兩個Modularity就是delta Q。

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

算法的計算過程如下：

• a、每個點作為一個community，然后考慮每個community的鄰居節(jié)點，合并到community，然后看delta Q；找到最大的正delta Q，合并點到community；多進行幾輪，至不再變動，那么結(jié)束；
  其中存在的問題是，不同的節(jié)點訪問順序?qū)?dǎo)致不同的結(jié)果，試驗中發(fā)現(xiàn)這個順序?qū)Y(jié)果影響不大，但是會在一定程度上影響計算時間。

• b、將新的community作為點，重復(fù)上述過程。那么如何確定新的點之前的權(quán)重呢？答案是將兩個community之間相鄰的點之間的權(quán)重和作為兩個community退化成一個點后的新的權(quán)重。

該算法的優(yōu)點主要有3個：a、易于理解；b、非監(jiān)督；和c、計算快速，最后我們可以得到的結(jié)果是層次化的社區(qū)發(fā)現(xiàn)結(jié)果。

spark實現(xiàn)

https://github.com/Sotera/spark-distributed-louvain-modularity

Louvain結(jié)果示意圖

算法的改進

還有其加速實現(xiàn)的論文，文章的題目是：A New Randomized Algorithm for Community Detection in Large Networks，其實現(xiàn)方式比較直接，就是考慮一個點周圍的百分之多少點進行歸并。可以在spark下面通過類似于多路歸并來實現(xiàn)。

其他參考資料

• http://www.cnblogs.com/allanspark/p/4197980.html
• https://www.quora.com/Is-there-a-simple-explanation-of-the-Louvain-Method-of-community-detection

總結(jié)

以上是生活随笔為你收集整理的LOUVAIN——社交网络挖掘之大规模网络的社区发现算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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