知識星球本文經授權轉載自微信公眾號「ECOLE」。
社群（Community）結構在複雜網路中普遍存在，整個網路由許多個社群組成，同一社群內的節點與節點之間連線緊密，而社群與社群之間的連線比較稀疏。
為了發現及分析複雜網路中的社群結構，許多社群發現（Community Detection）演演算法被提出。
一般而言，複雜網路中的社群發現是一個 NP 難問題，而多數現有社群發現演演算法都是基於貪婪演演算法，因此，當面臨大規模複雜網路時，這類演演算法的效能有時不能達到使用者的要求與期望。
與此同時，很多社群發現演演算法需要關於社群結構的先驗資訊，而在實際社會網路中，很難獲得此類資訊。為此，越來越多的研究者們開始關註基於演化演演算法的社群發現演演算法。
今天我們將與大家分享 5 篇基於演化演演算法的社群發現相關論文，由於筆者能力有限，因此，如果分享過程中疏漏了重要工作，還請大家不吝賜教與指正。
GECCO 2008
■ 論文 | Community Detection in Social Networks with Genetic Algorithms
■ 連結 | https://www.paperweekly.site/papers/1775
■ 作者 | Clara Pizzuti
本文發表在 GECCO 2008，作者提出了一種用以在社交網路中發現社群的遺傳演演算法。演演算法基於構成社群的節點中存在的鏈路數量和拓撲來定義社群中網路劃分的質量度量，並且透過執行遺傳演演算法來最佳化這些社群。
在演演算法結束時，網路結構中的所有密集社群都是透過選擇性地探索搜尋空間獲得的，而不需要事先知道社群數的確切數量。
演演算法在實際網路中進行實驗，結果表明遺傳演演算法能夠正確的檢測社群，並且結果與當時最好的社群發現演演算法相當。
LION 2012
■ 論文 | Community Detection in Social and Biological Networks using Differential Evolution
■ 連結 | https://www.paperweekly.site/papers/1776
■ 作者 | Guanbo Jia / Zixing Cai / Mirco Musolesi / Yong Wang / Dan A. Tennant / Ralf. J. M. Weber / John K. Heath / Shan He
本文提出了一種基於差分進化的社群發現演演算法 DECD。在 DECD 中，DE 將網路模組化作為適應值函式來搜尋網路的最佳分割槽。
考慮到 DECD 中個體是以社群識別符號為基礎的，傳統交叉運算元無法很好使用，文章提出了一種在演化過程中能有效傳輸相關社群結構化重要資訊的基於標準 DE 交叉運算元的二項式交叉運算元。
此外，DECD 採用了偏向初始化過程和清理過程，透過糾正進入錯誤社群的節點來提升種群中個體的質量。
不同於其它社群檢測演演算法，DECD 不需要有關社群結構的任何先驗知識，這使得 DECD 能夠更好的應用於沒有先驗資訊的實際問題中。演演算法在人工和兩個實際社交網路中進行實驗，結果表明 DECD 能夠得到更好的結果。
Applied Soft Computing 2014
■ 論文 | Multi-level Learning Based Memetic Algorithm for Community Detection
■ 連結 | https://www.paperweekly.site/papers/1777
■ 作者 | Lijia Ma / Maoguo Gong / Jie Liu / Qing Cai / Licheng Jiao
本文提出了透過最佳化模型進行社群檢測的基於多級學習策略的模因演演算法 MLCD。MLCD 採用遺傳演演算法做全域性搜尋並提出了多層學習策略來加速收斂。
多層學習策略分別在網路的結點、聚類和網路分割槽層上工作。透過迭代執行遺傳演演算法和多層學習策略，能夠準確、穩定的獲得具有高模組化的網路部分。
文章同時使用了模組化標簽傳播規則，在每次操作時更新每個節點的聚類識別符號，簡單的更新規則也保證了演演算法的執行速度。
MLCD 演演算法在 GN、LFR 和 12 個實際網路中進行了實驗，並與其它演演算法進行比較，實驗結果表明 MLCD 在尋找網路的適當社群結構時有優越的效能。
IEEE TEVC 2017
■ 論文 | A Maximal Clique Based Multiobjective Evolutionary Algorithm for Overlapping Community Detection
■ 連結 | https://www.paperweekly.site/papers/1778
■ 作者 | Xuyun Wen / Wei-Neng Chen / Ying Lin / Tianlong Gu / Huaxiang Zhang / Yun Li / Yilong Yin / Jun Zhang
針對重疊社群檢測，本文提出了一種基於最大組合的多標的進化演演算法 MCMOEA。文章引入了基於最大組合圖的新的表示方法，最大組合圖定義為使用一組最大組合作為節點、最大組之間的連線作為邊。
由於最大組合圖是根據使用原始圖的一組最大組合作為節點定義的，並且允許兩個最大組合共享原始圖的相同節點，因此重疊是最大組合圖的固有屬性，基於此，新的表示方法允許 MOEAs 以類似於分離社群檢測的方法來處理重疊社群檢測，從而簡化最佳化問題。
MCMOEA 演演算法在人造網路和實際網路中進行實驗，並與其它演演算法進行比較，結果表明 MCMOEA 更加高效。
IEEE TEVC 2017
■ 論文 | Evolutionary Computation for Community Detection in Networks: a Review
■ 連結 | https://www.paperweekly.site/papers/1780
■ 作者 | Clara Pizzuti
文章對基於演化演演算法提出的社群結構發現方法進行了總結，特別是歸納了基於遺傳運算元的策略，並討論了最常使用的測試函式。文章涵蓋了近期針對不同型別網路模型（動態、多維度）提出的單標的、多標的方法。
文章主要從問題定義、問題建模、編碼方案、遺傳運算元、適應值函式及多標的最佳化等六個方面進行綜述。
1. 問題定義
在該部分文章給出了社群網路結構的圖表示方法，並對該圖中的節點、邊、權重等資訊的意義進行了詳細說明。
2. 問題建模
在該部分，文章將社群結構發現抽象成了最佳化問題，並根據問題的特性，將其抽象成單標的最佳化問題和多標的最佳化問題兩種型別。並對問題的解空間、標的空間，給出了定義。
3. 編碼方案
在一個演演算法中解的表示是重要部分，現有的方法對子圖網路中的劃分進行編碼。這些方法通常從用於透過演化方法解決經典資料聚類問題的編碼改編而來。文章將這些編碼方法分為四類，並分別進行綜述：
基於層的表示方法：在這類方法中基因型是一個長度為 n 的整數向量，其中 n 是節點數目。位置 1≤i≤n 對應於節點，因此，如果 k 是社群的數量，則每個基因可以在字母表 {1，…，k} 中給定一個值。該值是標識節點 i 所屬的社群標簽。這類方法廣泛的應用於資料聚類，在引入到社群結構發現中後，成為了最常用的解決複雜網路的方法。
基於軌跡的表示方法：這類方法最早被提出用於資料聚類，並被開發為多標的聚類方法。在這類方法中，個體由 n 個基因組成，並且每個基因可以假定等位基因值在區間 {1，…，n} 中，分配給第 i 個基因的值 j 被解釋為節點 i 和 j 之間的連結。這使得將網路劃分為連線的元件，透過子圖表示出來常常是樹形。
基於中心的表示方法：這類方法使用維數 k 為的陣列，其中社群數量 k 必須作為輸入引數。陣列的第 i 個元素包含組成社群的節點之一。
基於置換的表示方法：由於前述方法不允許節點參與多個社群。為此新的課產生重貼社群的方法被提出。這類方法中，同一節點可以提高不止一個社群的適應值，從而增加到許多社群，產生重疊社群。
此外，在這部分文章還分析了四種編碼方法各自的優缺點。
4. 遺傳運算元
在這部分，文章對社群發現中常用的幾種遺傳運算元進行了綜述。
交叉運算元：將傳統的交叉運算元應用於社群發現會出現諸多問題，並且這些問題與所用的表示方法有關。為此，諸多適用於社群發現不同編碼型別的交叉運算元被提出。
變異運算元：變異的任務是修改基因值，以便能夠在搜尋空間中尚未檢查的區域探索。 然而，變異不能太具有破壞性使得無法找到最佳解決方案。為此，根據社群發現的自身性質，桌多變異運算元被提出。
種群初始化：種群初始化通常透過為每個個體分配隨機值來產生。然而，這樣的策略會給出質量差的網路的初步劃分，導致真正的社群高度混合。為此，諸多針對社群發現不同編碼型別的不同初始化方法被提出。
區域性搜尋運算元：遺傳運算元通常可以產生將節點分配到錯誤社群的解決方案。為了提高社群分工質量，一些啟髮式方法被提出。
5. 適應值函式
適應值函式是尋找優質解的重要部件，在社群檢測中，最常用的函式是模組化的。為此在這部分，文章對常用的這些適應值函式進行了分析和綜述。
6. 多標的最佳化
社群發現多數情況下被視為單標的問題進行最佳化，雖然這些單標的方法在人工和現實世界網路中都獲得了非常好的結果，但社群中的直覺概念是社群邊的數量應該遠遠高於連線到圖的剩餘節點的邊的數量，有兩個不同的標的：最大化內部連結並最大限度地減少外部連結。
因此，社群檢測問題自然是由多個相互競爭的標的組成的。為此，將社群發現問題視為多標的最佳化問題處理會更合理。在該部分，文章對現有提出的解決社群發現問題的多標的演化演演算法進行了綜述。
此外，文章對社群網路中的多個不同型別的網路以：簽名網路、多層網路、重疊社群發現分別進行了詳細介紹，及求解這些問題所用的方法進行了詳細綜述。此外文章對近年來的用於求解社群發現問題的其他生物啟發方法進行了綜述。
最後，文章對歸納的所有社群發現方法進行了詳細的總結。
延伸閱讀
■ 論文 | A Survey on Network Community Detection Based on Evolutionary Computation
■ 連結 | https://www.paperweekly.site/papers/1779
■ 作者 | Qing Cai / Ma Lijia / Maoguo Gong / Dayong Tian
除了以上最新的演化計算在社群發現中應用的綜述文獻外，稍早一篇發表在 International Journal of Bio-Inspired Computation 上的文章，對這類方法進行了詳細綜述。
# 作 者 招 募 #
我是彩蛋
解鎖新功能：熱門職位推薦！
PaperWeekly小程式升級啦
今日arXiv√猜你喜歡√熱門職位√
找全職找實習都不是問題
解鎖方式
1. 識別下方二維碼開啟小程式
2. 用PaperWeekly社群賬號進行登陸
3. 登陸後即可解鎖所有功能
職位釋出
請新增小助手微信（pwbot02）進行諮詢
長按識別二維碼，使用小程式
*點選閱讀原文即可註冊
關於PaperWeekly
PaperWeekly 是一個推薦、解讀、討論、報道人工智慧前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號後臺點選「交流群」，小助手將把你帶入 PaperWeekly 的交流群裡。
▽ 點選 | 閱讀原文 | 加入社群一起刷論文
