基于多目標(biāo)優(yōu)化算法的網(wǎng)絡(luò)社區(qū)檢測方法研究.pdf

1、近年來，對于復(fù)雜網(wǎng)絡(luò)的研究受到了廣泛關(guān)注。現(xiàn)實(shí)世界中的許多系統(tǒng)，如社會關(guān)系網(wǎng)、互聯(lián)網(wǎng)、生物網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等等都可以建模成為復(fù)雜網(wǎng)絡(luò)，用網(wǎng)絡(luò)中的節(jié)點(diǎn)表示現(xiàn)實(shí)世界中的各個事物，而事物間的聯(lián)系用網(wǎng)絡(luò)中節(jié)點(diǎn)間的連接表示。社區(qū)結(jié)構(gòu)是網(wǎng)絡(luò)的重要特征之一，它表征著該網(wǎng)絡(luò)中節(jié)點(diǎn)的不同劃分。歸于同一個網(wǎng)絡(luò)社區(qū)的節(jié)點(diǎn)間聯(lián)系較緊密，而不同社區(qū)中的節(jié)點(diǎn)之間聯(lián)系較為稀疏。檢測出網(wǎng)絡(luò)中的社區(qū)，有助于我們分析該網(wǎng)絡(luò)中各個事物間的關(guān)系，把握網(wǎng)絡(luò)的整體結(jié)構(gòu)。因此，對于網(wǎng)

2、絡(luò)社區(qū)檢測方法的研究是一個非常有意義的課題。
　　 現(xiàn)有的很多網(wǎng)絡(luò)社區(qū)檢測算法需要預(yù)先設(shè)定社區(qū)數(shù)目，如基于譜方法的社區(qū)檢測算法，而實(shí)際問題中，我們往往未知網(wǎng)絡(luò)的社區(qū)數(shù)目，這就要求我們提出可以自動檢測出所給網(wǎng)絡(luò)中社區(qū)數(shù)目的方法?；谀繕?biāo)優(yōu)化的社區(qū)檢測算法通常可以解決這一問題。但是基于單目標(biāo)優(yōu)化算法的網(wǎng)絡(luò)社區(qū)檢測方法一次運(yùn)行只能得到一個對網(wǎng)絡(luò)的劃分，而現(xiàn)實(shí)網(wǎng)絡(luò)大多具有層次性，因此，可以輸出對網(wǎng)絡(luò)不同層次劃分的社區(qū)檢測方法更具有實(shí)用價

3、值。
　　 本文提出一種基于多目標(biāo)優(yōu)化的社區(qū)檢測方法，該算法利用了非支配鄰域免疫算法(Non-dominated Neighbor Immune Algorithm，NNIA)對兩個目標(biāo)函數(shù)進(jìn)行優(yōu)化，從而檢測出網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)。同時，在演化聚類理論框架下提出動態(tài)網(wǎng)絡(luò)社區(qū)檢測方法，同樣利用NNIA作為優(yōu)化算法，對動態(tài)網(wǎng)絡(luò)中的社區(qū)檢測問題進(jìn)行嘗試性研究。本文的創(chuàng)新點(diǎn)如下：
　　 1.提出一種新的基于locus-based基因

4、表示方式的種群初始化方法，實(shí)驗證明該種群初始化方法較現(xiàn)有方法效率顯著提高。
　　 2.提出了一種基于NNIA的網(wǎng)絡(luò)社區(qū)檢測方法NNIA-Net，該方法對兩個目標(biāo)函數(shù)進(jìn)行優(yōu)化，每次運(yùn)行可產(chǎn)生一組解，這組解對應(yīng)著對網(wǎng)絡(luò)不同層次的劃分，每個解可以自動確定網(wǎng)絡(luò)中社區(qū)數(shù)目。
　　 3.在演化聚類框架下，提出一種動態(tài)網(wǎng)絡(luò)社區(qū)檢測方法DNNIA-Net，該方法對于逐步變化的動態(tài)網(wǎng)絡(luò)，根據(jù)當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)并結(jié)合其歷史信息進(jìn)行社區(qū)檢測，得到較