模組度

模組度也稱模組化度量值，是目前常用的一種衡量網絡社區結構強度的方法，最早由馬克·紐曼提出。模組度的定義為：

$Q={\frac {1}{2m}}*\sum _{ij}\left[A_{ij}-{\frac {k_{i}*k_{j}}{2m}}\right]\delta (C_{i},C_{j})$

模組度值的大小主要取決於網絡中結點的社區分配C，即網絡的社區劃分情況，可以用來定量的衡量網絡社區劃分質素，其值越接近1，表示網絡劃分出的社區結構的強度越強，也就是劃分質素越好。因此可以通過最大化模組度Q來獲得最佳的網絡社區劃分。

模組度最佳化演算法

由於網絡所有可能的劃分數量是巨大的，假設網絡的結點數和邊數分別為n和m，則所有可能的社區劃分數是一個以n為指數的數。因此，在所有可能的劃分中找出最佳劃分是一個NP-hard問題。針對這一問題，目前一些相應演算法已被提出，其可以在合理的時間內找出模組度最大化的近似最佳劃分。

經典貪婪演算法

模組度最大化問題是一個經典的最佳化問題，馬克·紐曼基於貪心思想提出了模組度最大化的貪婪演算法FN 。貪心思想的目標是找出目標函數的整體最佳值或者近似最佳值，它將整體最佳化問題分解為局部最佳化問題，找出每個局部最佳值，最終將局部最佳值整合成整體的近似最佳值。FN演算法將模組度最佳化問題分解為模組度局部最佳化問題，初始時，演算法將網絡中的每個結點都看成獨立的小社區。然後，考慮所有相連社區兩兩合併的情況，計算每種合併帶來的模組度的增量。基於貪心原則，選取使模組度增長最大或者減小最少的兩個社區，將它們合併成一個社區。如此迴圈迭代，直到所有結點合併成一個社區。隨着迭代的進行，網絡總的模組度是不斷變化的，在模組度的整個變化過程中，其最大值對應網絡的社區劃分即為近似的最佳社區劃分。
貪婪演算法FN具體步驟：

1. 去掉網絡中所有的邊，網絡的每個結點都單獨作為一個社區；
2. 網絡中的每個連通部分作為一個社區，將還未加入網絡的邊分別重新加回網絡，每次加入一條邊，如果加入網絡的邊連接了兩個不同的社區，則合併兩個社區，並計算形成新社區劃分的模組度增量。選擇使模組度增量最大或者減小最少的兩個社區進行合併。
3. 如果網絡的社區數大於1，則返回步驟（2）繼續迭代，否則轉到步驟（4）；
4. 遍歷每種社區劃分對應的模組度值，選取模組度最大的社區劃分作為網絡的最佳劃分。
   

該演算法中，需要注意的是，每次加入的邊只是影響網絡的社區劃分，而每次計算網絡劃分的模組度時，都是在網絡完整的拓撲結構上進行，即網絡所有的邊都存在的拓撲結構上。

快速模組度最佳化演算法

為了降低演算法的時間複雜度，Vincent Blondel等人提出了另一種層次的貪婪演算法。該演算法包括兩個階段，第一階段合併社區，演算法將每個結點當作一個社區，基於模組度增量最大化標準決定哪些鄰居社區應該被合併。經過一輪掃描後開始第二階段，演算法將第一階段發現的所有社區重新看成結點，構建新的網絡，在新網絡上重複進行第一階段，這兩個階段重複執行，直到網絡社區劃分的模組度不再增長，得到網絡的社區近似最佳劃分。
這個簡單演算法具有一下幾個優點：首先，演算法的步驟比較直觀並且易於實現；其次，演算法不需要提前設定網絡的社區數，並且該演算法可以呈現網絡的完整的分層社區結構，能夠發現線上社交網絡的分層的虛擬社區結構，獲得不同解像度的虛擬社區；再次，電腦模擬實驗顯示，在稀疏網絡上，演算法的時間複雜度是線性的，在合理的時間內可以處理結點數超過$10^{9}$的網絡，因此十分適合線上社交網絡這樣超大規模的負責網絡中虛擬社區的發現。