基於進化多目標最佳化的社區發現算法是一種基於遺傳算法的社區發現算法，通過將模組度拆分為兩個目標，進而最佳化模組度，最終發現社區。
基本介紹
- 中文名：基於進化多目標最佳化的社區發現算法
- 外文名：Community discovery algorithm based on evolutionary multiobjective optimization
遺傳算法（簡稱GA）是一種由生物進化理論指導搜尋算法。通過搜尋來找到最優或者接近最優的解。
首先回顧模組度的數學意義，即網路中連線兩個同種類型的節點的邊（即同一社區內部的邊）的比例減去在同樣社區結構下任意連線這兩個節點的邊的比例的期望值。
第一個目標是使得每個社團內部的邊數儘可能多，同時第二個目標是小使得網路儘可能劃分為很多度較少的社團。這兩個相互衝突的子目標反映了一個好的社團劃分中兩個不同的方面：內部連結緊密（即第一個子式），外部連結稀疏（即第二個子式）。模組度Q本質上就是這兩個目標的折中。
當採用進化算法解決社團發現問題時，需要用基因型（genotype）來表示一個社團劃分，即為該劃分進行編碼。同樣，也需要對基因型進行解碼，即表示它的劃分結果。在此，我們使用了鄰接點表示法，每個基因型包含了n個基因（n為網路中結點個數），每個基因表示了節點i的一個鄰居結點編號。因此，第i個基因的值j表示了結點i和j之間有邊相連，從社團劃分結果來看，即結點i和j被劃分到了同一社團。解碼過程需要對圖中每一個連通分量進行識別，隸屬於同一個連通分量的所有結點被劃分到同一個社團。
