模塊度

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

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