模組度

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

$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}$的網路，因此十分適合線上社群網路這樣超大規模的負責網路中虛擬社群的發現。