歡迎光臨
每天分享高質量文章

演化演算法(EA)在社區發現方面的進展

本文經授權轉載自微信公眾號「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 的交流群里。


▽ 點擊 | 閱讀原文 | 加入社區一起刷論文

赞(0)

分享創造快樂