在將復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問題建模為多目標(biāo)優(yōu)化問題時,采用帶精英策略的非支配排序遺傳算法（NSGA-Ⅱ）的方法來尋找問題最優(yōu)解。該算法解決了拓展后的模塊度密度問題中的分辨率限制參數(shù)調(diào)整問題,以及優(yōu)化模塊度密度函數(shù)的分辨率限制問題,使得算法運行一次可得到一組不同的劃分結(jié)果,以便決策者根據(jù)需要進(jìn)行選擇。另外,遺傳算法的交叉和變異算子加入了網(wǎng)絡(luò)頂點的鄰域信息,符合真實網(wǎng)絡(luò)的特性,且基于圖的編碼方式保證了社區(qū)數(shù)目的自適應(yīng)性。實驗結(jié)果證明,采用基于非支配排序遺傳算法的社區(qū)發(fā)現(xiàn)算法能有效的發(fā)現(xiàn)出社區(qū)結(jié)構(gòu)。 

【文章來源】：信陽農(nóng)林學(xué)院學(xué)報. 2020,30(03)

【文章頁數(shù)】：6 頁

【部分圖文】：

基于NSGA-II的社區(qū)發(fā)現(xiàn)算法在真實世界網(wǎng)絡(luò)上所得PF

空手道俱樂部網(wǎng)絡(luò)是由社會學(xué)家Zachary用了兩年時間在大學(xué)空手道俱樂部中觀察34名俱樂部成員之間的社會關(guān)系網(wǎng)絡(luò)[9-10]。最后，一個社區(qū)變成了兩個社區(qū)，如圖1所示。這主要是因為空手道教練辭職后有部分隊員與教練一同離開，形成了新的社交關(guān)系網(wǎng)絡(luò)。USA大學(xué)生足球聯(lián)賽俱樂部社交網(wǎng)絡(luò)數(shù)據(jù)集是Newman和Girvan兩人觀察的2000年秋 季USA大學(xué)生足球聯(lián)賽常規(guī)賽季 的比賽網(wǎng)絡(luò)數(shù)據(jù)[11-12],根據(jù)賽區(qū)劃分將球隊分成115個節(jié)點,因此,網(wǎng)絡(luò)中每個節(jié)點表示一個球隊,兩個節(jié)點之 間進(jìn)行的比賽由 網(wǎng)絡(luò)中的連接線表示。每個節(jié)點在常規(guī)賽季中平均要有11條連接線,包括7條賽區(qū) 內(nèi)的連接和4條賽區(qū)間的連接。該社交網(wǎng)絡(luò)數(shù)據(jù)集中共有115個球隊和616場比賽,所有的球隊被劃分成12個賽區(qū),也就是12個社區(qū)。

為了進(jìn)一步證明本算法的有效性,這里隨機(jī)選取算法在karate網(wǎng)絡(luò)上所得解并給出其對應(yīng)的社區(qū)劃分情況,如圖3。圖3(a)與(b)得到了與真實劃分一致的解,(c)中所得劃分得到了三個社區(qū),其中將原有的一個大社區(qū)分為了兩個,(d)所得劃分與(c)類似,同樣是將大的社區(qū)劃分為兩個小社區(qū)。如此一來,我們可以根據(jù)決策者的需要選取合適的劃分,這也是采用多目標(biāo)算法進(jìn)行優(yōu)化社區(qū)發(fā)現(xiàn)的最主要的優(yōu)點。圖3 隨機(jī)選取Karate網(wǎng)絡(luò)PF中的解對應(yīng)的社區(qū)劃分情況

【參考文獻(xiàn)】：
期刊論文
[1]基于特征向量局部相似性的社區(qū)檢測算法[J]. 楊旭華,沈敏.  計算機(jī)科學(xué). 2020(02)
[2]基于貪婪局部路徑重連的隨機(jī)并行社區(qū)檢測[J]. 單康康,郭曄,陳文智.  計算機(jī)工程. 2019(06)



本文編號：3508748