1、近年來隨著各學(xué)科研究之間的交叉,復(fù)雜網(wǎng)絡(luò)受到了越來越多的科研工作者的關(guān)注?，F(xiàn)實生活中的大多數(shù)復(fù)雜系統(tǒng)都可以簡單地抽象成一個復(fù)雜網(wǎng)絡(luò),進(jìn)而轉(zhuǎn)換成一個圖的形式來進(jìn)行研究。然而復(fù)雜網(wǎng)絡(luò)的一個重要特征就是具有社區(qū)結(jié)構(gòu)。網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)是指網(wǎng)絡(luò)中節(jié)點的分類集合,其主要的特征之一是同一集合內(nèi)的節(jié)點之間連接比較緊密,不同集合之間的連接比較稀疏。了解網(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ù)測網(wǎng)絡(luò)的行為。正因為網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)具有如此重要的價值,而現(xiàn)實社會中的大多數(shù)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)并不是可以直接獲取的,所以說如何在現(xiàn)有的網(wǎng)絡(luò)數(shù)據(jù)的基礎(chǔ)上快速高效的發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)是一項十分重要的工作。發(fā)現(xiàn)網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)通俗的講就是對網(wǎng)絡(luò)中的節(jié)點進(jìn)行分組,而分組遺傳算法是專門針對分組類問題提出的一種進(jìn)化算法?；趶?fù)雜網(wǎng)絡(luò)社區(qū)內(nèi)部連接比較緊密,社區(qū)之間連接比較稀疏的特征,本文提出了一種基于社區(qū)密度下限的分組遺傳算法,進(jìn)而這種

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

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