快速模組度最佳化是一種快速層次性貪心社團發現算法。該算法包括兩個階段，這兩個階段重複疊代運行，直到網路社區劃分的模組度不再增長。第一階段合併社區，算法將每個節點當作一個社區，基於模組度增量最大化標準決定哪些鄰居社區應該被合併。經過一輪掃描後開始第二階段，算法將第一階段發現的所有的社區重新看作節點，構建新的網路，在新的網路上疊代的進行第一階段。當模組度不再增長時，得到網路的社區近似最優劃分。
基本介紹
- 中文名：快速模組度最佳化算法
- 外文名：Fast modularity optimization method
為了降低算法的時間複雜度，Vincent Blondel等人提出了另一種層次性貪心算法（BGLL算法）。該算法包括兩個階段，這兩個階段重複疊代運行，直到網路社區劃分的模組度不再增長。第一階段合併社區，算法將每個節點當作一個社區，基於模組度增量最大化標準決定哪些鄰居社區應該被合併。經過一輪掃描後開始第二階段，算法將第一階段發現的所有的社區重新看作節點，構建新的網路，在新的網路上疊代的進行第一階段。當模組度不再增長時，得到網路的社區近似最優劃分。
算法的基本步驟如下：
1）.初始化，將每個節點劃分在不同的社區中。
2）.逐一選擇各個節點，根據公式計算將它劃分到它的鄰居社區中得到的模組度增益。如果最大增益大於0，則將它劃分到對應的鄰居社區；否則，保持歸屬於原社區。
3）.重複步驟2，直到節點的社區不再發生變化。
4）.構建新圖。新圖中的點代表上一階段產生的不同社區，邊的權重為兩個社區中所有節點對的邊權重之和。重複步驟2，直到獲得最大的模組度值。
這個簡單的算法具有幾個優點，首先，算法的步驟比較直觀並且易於實現；第二，算法不需要提前設定網路的社區數，並且該算法可以呈現網路完整的分層社區結構，能夠發現線上社交網路的分層的虛擬社區結構，獲得不同解析度的虛擬社區；最後，計算機模擬實驗顯示，在稀疏網路上，算法的時間複雜度是線性的，在合理的時間內可以處理節點數超過10^9的網路，因此十分適合線上社交網路這樣超大規模的複雜網路中虛擬社區的發現。
