模組度

模組度也稱模組化度量值，是目前常用的一種衡量網路社區結構強度的方法。

基本介紹

• 中文名：模組度
• 外文名：Modularity

模組度介紹

模組度也稱模組化度量值，是目前常用的一種衡量網路社區結構強度的方法，最早由Mark NewMan 提出了。模組度的定義為：

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

最最佳化算法

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

經典貪心算法

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

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

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

快速模組度最佳化算法

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