奇技指南

在海量的信息流中，通過精準的算法給用戶推薦其感興趣的內容，已經成為了一個產品吸引用戶，獲取收益的極其重要的方式。

本篇為算法系列文章，將為大家分享360的算法團隊在實踐中積累的算法知識及經驗，歡迎大家交流分享~

Louvain算法是一種基于多層次優化Modularity的算法，具有快速、準確的優點，在效率和效果上都表現比較好，并且能夠發現層次性的社區結構，被認為是性能最好的社區發現算法之一。

模塊度

Louvain算法是一種基于圖數據的社區發現算法。

原始論文為：

《Fast unfolding of communities in large networks》。

Louvain算法的優化目標為最大化整個數據的模塊度，

模塊度的計算如下：

其中m為圖中邊的總數量，k_i表示所有指向節點i的連邊權重之和，k_j同理。A_{i,j} 表示節點i，j之間的連邊權重。

有一點要搞清楚，模塊度的概念不是Louvain算法發明的，而Louvain算法只是一種優化關系圖模塊度目標的一種實現而已。

Louvain算法的兩步迭代設計

最開始，每個原始節點都看成一個獨立的社區，社區內的連邊權重為0

步驟1

算法掃描數據中的所有節點，針對每個節點遍歷該節點的所有鄰居節點，衡量把該節點加入其鄰居節點所在的社區所帶來的模塊度的收益。并選擇對應最大收益的鄰居節點，加入其所在的社區。這一過程化重復進行指導每一個節點的社區歸屬都不在發生變化。

步驟2

對步驟1中形成的社區進行折疊，把每個社區折疊成一個單點，分別計算這些新生成的“社區點”之間的連邊權重，以及社區內的所有點之間的連邊權重之和。用于下一輪的步驟1。

該算法的最大優勢就是速度很快，步驟1的每次迭代的時間復雜度為O(N)，N為輸入數據中的邊的數量。步驟2 的時間復雜度為O(M + N)， M為本輪迭代中點的個數。

算法實現

數據結構設計

算法數據結構的設計主要有兩方面的考慮：

如何高效地存儲圖中的節點和節點之間的關系

如何在設計的數據結構上高效地掃描數據、進行算法迭代。

當前一些開源的算法實現主要通過hash表或set的結構來存儲節點和節點之間的關系。

主要有兩個缺點：

維護hash 或 集合結構本身就需要不少內存開銷

遍歷過程中需要不斷地創建、銷毀、清空對應的Hash 或 Set 結構，尤其是在遍歷不同的節點的鄰居節點以及社區這點時。

而且，在遍歷過程中，結構對元素的訪問也并不是嚴格O(1)的。

出于以上考慮，我們設計一種更高效的數據結構來存儲圖中的節點和邊，避開使用復雜的數據結構，且在算法迭代過程中不申請多余的空間和空間的銷毀操作，具體如下：

關于節點字段的說明：

• count：社區內的節點個數

• clsid：節點歸屬社區的代表節點ID

• next：步驟1迭代中下一個屬于同一個臨時社區的節點

• prev：步驟1迭代中上一個屬于同一個臨時社區的節點

• first：屬于同一個社區的，除代表節點外的第一個節點，該節點有步驟2 社區折疊的時候生成

• kin：穩定社區內部節點之間的互相連接權重之和

• kout：穩定社區外部，指向自己社區的權重之和

• clskin：臨時社區內部節點之間的互相連接權重之和

• clstot：穩定社區所有內外部指向自己的連接權重之和

• eindex：節點鄰居鏈表的第一個指針，該鏈表下的所有left，都是本節點自己

  
  

關于邊數據結構的字段就顧名思義即可。

基于上述結構設計，在給定了一個M個節點，N調邊的圖所需的空間為：60 * M + 24 * N.

例如：給定1000萬給點，2000萬邊的數據，則需要空間約為：10000000 * 60 + 20000000 * 24 = 1080M.且整個迭代過程中內存環境維持不變。

迭代過程

1、假設我們最開始有5個點，互相之間存在一定的關系（至于什么關系，先不管），如下：

2、假設在進過了步驟1的充分迭代之后發現節點2，應該加入到節點1所在的社區（最開始每個點都是一個社區，而自己就是這個社區的代表），新的社區由節點1代表，如下：

此時節點3，4，5之間以及與節點1，2之間沒有任何歸屬關系。

3、此時應該執行步驟2，將節點1，2組合成的新社區進行折疊，折疊之后的社區看成一個單點，用節點1來代表，如下：

此時數據中共有4個節點（或者說4個社區），其中一個社區包含了兩個節點，而社區3，4，5都只包含一個節點，即他們自己。

4、重新執行步驟1，對社區1，3，4，5進行掃描，假設在充分迭代之后節點5，4，3分別先后都加入了節點1所在的社區，如下：

5、進行步驟2，對新生成的社區進行折疊，新折疊而成的社區看成一個單點，由節點1代表，結構如下：

此時由于整個數據中只剩下1個社區，即由節點1代表的社區。

再進行步驟1時不會有任何一個節點的社區歸屬發生變化，此時也就不需要再執行步驟2，至此， 迭代結束。

代碼實現及測試

一個基于上述結構設計的代碼實現參見：

https://github.com/liuzhiqiangruc/dml/blob/master/cls/louvain.c

在一個實際的圖（70萬點，200萬邊）上進行測試，迭代到完全收斂所需時間為：1.77秒。

實際中往往不需要迭代到每一個點都不發生變化，或者整個圖中有多少比例的節點不在發生變化就退出。

本篇為算法系列文章的第3篇，為大家分享了Louvain算法的原理及設計實現。

本文來自360視頻信息流算法團隊投稿，我們將每周為大家推送一篇算法相關的文章，歡迎大家一起交流學習。

相關推薦

• 深度殘差網絡的一波兩折

• 淺談 梯度下降法/Gradient descent

界世的你當不

只做你的肩膀

無

?360官方技術公眾號?

技術干貨|一手資訊|精彩活動

空·

點關注哦~

總結

以上是生活随笔為你收集整理的Louvain 算法原理及设计实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。