分組遺傳算法在社區(qū)檢測(cè)及鏈路預(yù)測(cè)上的應(yīng)用.pdf

1、近年來(lái)隨著各學(xué)科研究之間的交叉,復(fù)雜網(wǎng)絡(luò)受到了越來(lái)越多的科研工作者的關(guān)注?，F(xiàn)實(shí)生活中的大多數(shù)復(fù)雜系統(tǒng)都可以簡(jiǎn)單地抽象成一個(gè)復(fù)雜網(wǎng)絡(luò),進(jìn)而轉(zhuǎn)換成一個(gè)圖的形式來(lái)進(jìn)行研究。然而復(fù)雜網(wǎng)絡(luò)的一個(gè)重要特征就是具有社區(qū)結(jié)構(gòu)。網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)是指網(wǎng)絡(luò)中節(jié)點(diǎn)的分類集合,其主要的特征之一是同一集合內(nèi)的節(jié)點(diǎn)之間連接比較緊密,不同集合之間的連接比較稀疏。了解網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)可以幫助我們進(jìn)一步分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),理解并更好地解釋網(wǎng)絡(luò)的功能,從而能夠更容易發(fā)現(xiàn)網(wǎng)絡(luò)中一

2、些隱而未現(xiàn)的規(guī)律以及預(yù)測(cè)網(wǎng)絡(luò)的行為。正因?yàn)榫W(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)具有如此重要的價(jià)值,而現(xiàn)實(shí)社會(huì)中的大多數(shù)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)并不是可以直接獲取的,所以說(shuō)如何在現(xiàn)有的網(wǎng)絡(luò)數(shù)據(jù)的基礎(chǔ)上快速高效的發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)是一項(xiàng)十分重要的工作。發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)通俗的講就是對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行分組,而分組遺傳算法是專門(mén)針對(duì)分組類問(wèn)題提出的一種進(jìn)化算法?；趶?fù)雜網(wǎng)絡(luò)社區(qū)內(nèi)部連接比較緊密,社區(qū)之間連接比較稀疏的特征,本文提出了一種基于社區(qū)密度下限的分組遺傳算法,進(jìn)而這種

3、方法應(yīng)用到復(fù)雜網(wǎng)絡(luò)的社區(qū)檢測(cè)上,并將這種方法獲得的社區(qū)結(jié)構(gòu)信息用于鏈路預(yù)測(cè)上,達(dá)到預(yù)測(cè)網(wǎng)絡(luò)行為的實(shí)際應(yīng)用價(jià)值。本文通過(guò)大量的仿真實(shí)驗(yàn),驗(yàn)證了這種方法在處理這兩類問(wèn)題上的有效性。本文的主要工作如下:
　　1.在分組遺傳算法的基礎(chǔ)上,結(jié)合復(fù)雜網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)特點(diǎn),提出一種基于社區(qū)密度下限的分組遺傳算法的社區(qū)檢測(cè)方法。由于真實(shí)網(wǎng)絡(luò)中的所含節(jié)點(diǎn)個(gè)數(shù)很少的微小社區(qū)十分少見(jiàn),考慮微小社區(qū)的存在會(huì)降低整體劃分結(jié)果,所以在分組的過(guò)程中對(duì)存在于微小社

4、區(qū)內(nèi)的節(jié)點(diǎn)進(jìn)行重新分配,在一定程度上減少了微小社區(qū)的存在。文章中用不同的目標(biāo)函數(shù)(HHI,Q, Dλ)作為遺傳過(guò)程中的目標(biāo)函數(shù),分別試驗(yàn)了這種方法的社區(qū)劃分效果,并將這種方法與DenShrink方法,BGLL方法相比較,證明了本文中所提出的方法有效性。
　　2.將社區(qū)結(jié)構(gòu)的信息應(yīng)用到復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測(cè)中,并提出了基于社區(qū)結(jié)構(gòu)信息的鏈路預(yù)測(cè)方法,引入了一種新的計(jì)算兩個(gè)節(jié)點(diǎn)之間相似性的函數(shù)。用Dλ作為度量函數(shù),在不同的分辨率參數(shù)下,運(yùn)