基于多目標免疫算法的動態(tài)網(wǎng)絡社區(qū)檢測.pdf

1、近年來，隨著社會網(wǎng)絡研究的興起，對社會網(wǎng)絡中的社區(qū)結(jié)構進行檢測，逐漸成為了研究的熱點。社區(qū)結(jié)構是社會網(wǎng)絡最重要的拓撲結(jié)構屬性之一，它揭示了社會網(wǎng)絡的隱藏規(guī)律和行為特征。而現(xiàn)實世界中的社會網(wǎng)絡多數(shù)都是動態(tài)網(wǎng)絡，動態(tài)網(wǎng)絡的社區(qū)結(jié)構會隨著時間不斷演化，因此它比靜態(tài)網(wǎng)絡社區(qū)檢測更富有挑戰(zhàn)性。目前對于動態(tài)網(wǎng)絡社區(qū)檢測問題，進行的研究還只是處于起步階段，所提出的方法也不多見。針對于傳統(tǒng)的方法不能夠自動識別社區(qū)個數(shù)，而且需要預先設定權重參數(shù)來控制對兩

2、個代價函數(shù)的不同側(cè)重，本文基于多目標免疫算法，提出了三種動態(tài)網(wǎng)絡社區(qū)檢測算法來解決動態(tài)網(wǎng)絡社區(qū)檢測問題。本文的主要工作如下：
　　 (1)以基于人工免疫系統(tǒng)的的多目標優(yōu)化算法，即非支配鄰域免疫算法(NNIA)為基礎，提出了一種新的動態(tài)網(wǎng)絡社區(qū)檢測算法。該算法以模塊度和規(guī)范化的互信息熵作為優(yōu)化的目標函數(shù)，用社團劃分得分(CS)作為每個時刻最優(yōu)解的選擇標準，這樣就可以克服傳統(tǒng)算法的缺點，新算法不僅可以找到相對較好的解，發(fā)現(xiàn)每個時刻比

3、較準確的社區(qū)結(jié)構，而且得到的結(jié)果也相對比較穩(wěn)定。
　　 (2)針對非支配鄰域免疫算法對稀疏區(qū)域的個體搜索不完善的缺點，將拉馬克學習策略引入到該算法中，提出了基于拉馬克多目標免疫算法的動態(tài)網(wǎng)絡社區(qū)檢測算法。通過在非支配種群的產(chǎn)生階段加入局部搜索策略，來加強原算法的全局尋優(yōu)能力和快速收斂能力。通過仿真試驗，證明了加入局部搜索能進一步提高算法的性能。
　　 (3)為了克服基于鄰接點編碼方式的缺陷以及局部搜索方向不可控，我們提出

4、了一種新的基于多目標密母算法的動態(tài)社區(qū)檢測算法。該算法采用直接編碼的方式，使用簡單的啟發(fā)式搜索對初始種群進行預處理，而且根據(jù)直接編碼方式的特點，采用雙路交叉與單點變異方式來替代原算法中的重組和超變異操作，同時為了提高算法的性能，我們加入了基于多目標密母算法的局部搜索策略，而在選擇最優(yōu)解時，我們使用了模塊密度作為選擇標準來彌補模塊度函數(shù)的不足。通過一系列的實驗，證明了新的算法不僅可以準確的檢測出每個時刻的社區(qū)結(jié)構，而且可以追蹤到詳細的社區(qū)