整個算法是基于Modularity的計算，然后就是迭代，社區改變，然后收縮，繼續迭代，社區改變，然后收縮，如此以往。
這里貼上算法的流程：

算法形式化描述
1）初始化：
將圖中的每個節點看成一個獨立的社區，社區的數目與節點個數相同；

2）開始first phase迭代 - 社區間節點轉移：
對每個節點i，依次嘗試把節點 i 分配到其每個鄰居節點所在的社區，計算分配前與分配后的模塊度變化ΔQ

3）重復2）- 繼續進行社區間節點轉移評估：
直到所有節點的所屬社區不再變化，即社區間的節點轉移結束，可以理解為本輪迭代的 Local Maximization 已達到；

4）second phase - Rebuilding Graph：
因為在這輪的first phase中，社區 C 中新增了一個新的節點 i，而 i 所在的舊的社區少了一個節點，因此需要對整個圖進行一個rebuild。

對圖進行重構，將所有在同一個社區的節點重構成一個新社區，社區內節點之間的邊的權重更新為新節點的環的權重，社區間的邊權重更新為新節點間的邊權重；

5）重復2）- 繼續開始下一輪的first/second phase：
直到整個圖的模塊度不再發生變化。
（https://www.cnblogs.com/LittleHann/p/9078909.html）

然后其實關于louvain算法，基本理解用自己的話來重復一遍。
每次找一個節點，算它分配到鄰居的社區的ΔQ，將其改為選最大的的那個社區，這樣找一輪下來，（不過不知道這里是同步還是異步的，應該是同步的，及時改變及時用），一輪找下來，每個節點所屬的社區肯定有所變化，再來一輪，再來一輪，直到現在的Q不會再改變，即每個節點的所屬社區不再變化，則進入第二階段。
第二個階段是將之前形成的社區縮成一個節點，比如原本網絡中有200個節點（初始是每個節點一個社區），經過了第一個階段，形成了45個社區，那么第二階段就會將整個網絡轉化成45個節點的網絡（依然是每個節點一個社區），社區內的邊權變成該節點的自環。從而轉換完成。
下面繼續進行第一階段，直到不變。
然后再第二階段，直到不變。

至于louvain算法能夠檢測層次性社區，是因為比如對于社區1，它在第一階段之后，它有20個節點，然后在第二階段縮成一個節點，依然代表社區1。然后繼續第一階段。然后發現此時有社區1有3個節點。那么社區1就有層次性了，其中一開始20個是第一層，而后來新增的兩個節點包含的多個節點就是第二層了。如是便是層次性的體現。

在算法執行過程中，很明顯的就是一開始較為復雜，因為涉及到的節點多，每次都要計算與改變到鄰接節點的ΔQ，計算量比較大。
而一旦涉及到第二階段，再執行第一階段，所有的節點和邊的數目就變小了，所以計算量會變小。
總體來看，越往后，計算量越來越小。

總結

以上是生活随笔為你收集整理的社区发现 louvain(fast unfolding)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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