text: 模組度也稱模組化度量值，是目前常用的一種衡量網路強度的方法，最早由提出。模組度的定義為：formula_1模組度值的大小主要取決於網路中結點的社群分配C，即網路的社區劃分情況，可以用來定量的衡量網路社區劃分質量，其值越接近1，表示網路劃分出的社群結構的強度越強，也就是劃分質量越好。因此可以透過最大化模組度Q來獲得最優的網路社區劃分。模組度最最佳化演算法.由於網路所有可能的劃分數量是巨大的，假設網路的結點數和邊數分別為n和m，則所有可能的社區劃分數是一個以n為指數的數。因此，在所有可能的劃分中找出最優劃分是一個NP-hard問題。針對這一問題，目前一些相應演算法已被提出，其可以在合理的時間內找出模組度最大化的近似最優劃分。經典貪心演算法.模組度最大化問題是一個經典的最最佳化問題，Mark Newman 基於貪心思想提出了模組度最大化的貪心演算法FN 。貪心思想的目標是找出目標函式的整體最優值或者近似最優值，它將整體最最佳化問題分解為區域性最最佳化問題，找出每個區域性最優值，最終將區域性最優值整合成整體的近似最優值。FN演算法將模組度最最佳化問題分解為模組度區域性最最佳化問題，初始時，演算法將網路中的每個結點都看成獨立的小社群。然後，考慮所有相連社群兩兩合併的情況，計算每種合併帶來的模組度的增量。基於貪心原則，選取使模組度增長最大或者減小最少的兩個社群，將它們合併成一個社群。如此迴圈迭代，直到所有結點合併成一個社群。隨著迭代的進行，網路總的模組度是不斷變化的，在模組度的整個變化過程中，其最大值對應網路的社區劃分即為近似的最優社區劃分。貪心演算法FN具體步驟：該演算法中，需要注意的是，每次加入的邊只是影響網路的社區劃分，而每次計算網路劃分的模組度時，都是在網路完整的拓撲結構上進行，即網路所有的邊都存在的拓撲結構上。快速模組度最佳化演算法.為了降低演算法的時間複雜度，Vincent Blondel等人提出了另一種層次的貪心演算法。該演算法包括兩個階段，第一階段合併社群，演算法將每個結點當作一個社群，基於模組度增量最大化標準決定哪些鄰居社群應該被合併。經過一輪掃描後開始第二階段，演算法將第一階段發現的所有社群重新看成結點，構建新的網路，在新網路上重複進行第一階段，這兩個階段重複執行，直到網路社區劃分的模組度不再增長，得到網路的社群近似最優劃分。這個簡單演算法具有一下幾個優點：首先，演算法的步驟比較直觀並且易於實現；其次，演算法不需要提前設定網路的社群數，並且該演算法可以呈現網路的完整的，能夠發現線上社交網路的分層的虛擬社群結構，獲得不同解析度的虛擬社群；再次，計算機模擬實驗顯示，在上，演算法的時間複雜度是線性的，在合理的時間內可以處理結點數超過formula_2的網路，因此十分適合線上社交網路這樣超大規模的負責網路中虛擬社群的發現。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 模組度
metadata.url: https://zh.wikipedia.org/wiki?curid=4740065