Mark Newman基於貪心思想提出了模組度最大化的貪心算法，基於貪心原則，選取使模組度增長最大或者減小最少的兩個社區，將它們合併成一個新的社區。如此循環疊代，直到所有節點合併成一個社區。隨著疊代的進行，網路總的模組度是不斷變化的，在模組度的整個變化過程中，其最大值對應的網路的社區劃分即為近似的最優社區劃分
基本介紹
- 中文名：Fast Girvan Newman社團發現算法
- 外文名：Fast GN community detection method
模組度最大化問題是一個典型的最最佳化問題，Mark Newman基於貪心思想提出了模組度最大化的貪心算法FN。貪心思想的目標是為了找出目標函式的整體最優值或者近似最優值，它將整體最最佳化問題分解為局部最最佳化問題，找出每個小的局部最優值，最終將局部最優值整合成整體的近似最優值。FN算法將模組度最最佳化問題分解為模組度局部最最佳化問題，初始時，算法將網路中的每個節點都單獨的看作獨立的小社區。然後，考慮所有相連社區兩兩合併的情況，計算每種合併帶來的模組度的增量。基於貪心原則，選取使模組度增長最大或者減小最少的兩個社區，將它們合併成一個新的社區。如此循環疊代，直到所有節點合併成一個社區。隨著疊代的進行，網路總的模組度是不斷變化的，在模組度的整個變化過程中，其最大值對應的網路的社區劃分即為近似的最優社區劃分。
貪心算法FN具體步驟如下所述：
（1）去掉網路中所有的邊，網路的每個節點都單獨作為一個社區；
（2）網路中的每個連通部分作為一個社區，將還未加入網路的邊分別重新加回網路，如果加入網路的邊連線了兩個不同的社區，即合併了兩個社區，則計算形成的新的社區劃分的模組度的增量。選擇使模組度增長最大或者減小最少的兩個社區進行合併；
（3）如果網路的社區數大於1，則返回步驟 （2） 繼續疊代，否則轉到步驟 （4）；
（4）遍歷每種社區劃分對應的模組度的值，選取模組度最大的社區劃分作為網路的最優劃分。
