復(fù)雜網(wǎng)絡(luò)環(huán)境下的社區(qū)發(fā)現(xiàn)技術(shù)研究.pdf

1、近年來，隨著互聯(lián)網(wǎng)及其上虛擬網(wǎng)絡(luò)的規(guī)模日趨龐大，拓?fù)浣Y(jié)構(gòu)也越來越復(fù)雜。在這種復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)中，個體偏好和群體關(guān)系具有很大的應(yīng)用價值，而社區(qū)發(fā)現(xiàn)技術(shù)，是挖掘個體偏好及群體關(guān)系的基礎(chǔ)性方法，得到了研究者的廣泛關(guān)注。但是，當(dāng)前的社區(qū)發(fā)現(xiàn)算法存在需要人為設(shè)定一些參數(shù)以獲得準(zhǔn)確的社區(qū)結(jié)構(gòu)的問題，還有一些經(jīng)典的社區(qū)發(fā)現(xiàn)算法無法挖掘網(wǎng)絡(luò)重疊社區(qū)，這些問題都影響到復(fù)雜網(wǎng)絡(luò)環(huán)境下社區(qū)發(fā)現(xiàn)的準(zhǔn)確性。針對以上問題，本論文以復(fù)雜網(wǎng)絡(luò)為研究環(huán)境，重點對社區(qū)屬性以

2、及重疊社區(qū)進(jìn)行了分析研究，提出了一種能夠適用于復(fù)雜網(wǎng)絡(luò)的預(yù)處理模型以及一種重疊社區(qū)發(fā)現(xiàn)算法。
　　論文的研究工作得到了國家自然科學(xué)基金項目(No.61172072、61271308)、北京市自然科學(xué)基金項目(No.4112045)和高等學(xué)校博士學(xué)科點專項科研基金(No.20100009110002)的支持。本論文的主要工作包括以下兩個方面:
　　(1)以馬爾科夫聚類算法為基礎(chǔ)，提出復(fù)雜網(wǎng)絡(luò)社區(qū)的預(yù)處理模型。該預(yù)處理模型能夠從

3、復(fù)雜網(wǎng)絡(luò)中分析出節(jié)點的重要性信息，得到網(wǎng)絡(luò)中的中心節(jié)點，并能夠根據(jù)得到的網(wǎng)絡(luò)邊結(jié)構(gòu)信息，對已知的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行邊權(quán)賦值。結(jié)合中心節(jié)點與邊權(quán)賦值結(jié)果，進(jìn)而得到預(yù)處理網(wǎng)絡(luò)。該預(yù)處理網(wǎng)絡(luò)中包含社區(qū)發(fā)現(xiàn)算法所需的先驗性信息，因此能夠降低人為設(shè)定參數(shù)對社區(qū)發(fā)現(xiàn)算法準(zhǔn)確性的影響。
　　(2)提出了一種基于隨機游走的多標(biāo)簽重疊社區(qū)發(fā)現(xiàn)算法(Multi-Label Propagation algorithm based on Random Wa

4、lk，簡稱RW-MLP算法)。本論文中，RW-MLP算法結(jié)合隨機游走的全局性優(yōu)勢，利用經(jīng)過預(yù)處理得到的網(wǎng)絡(luò)結(jié)構(gòu)信息，構(gòu)建標(biāo)簽矩陣并進(jìn)行標(biāo)簽傳播，最后根據(jù)標(biāo)簽得到社區(qū)劃分結(jié)果。RW-MLP算法在保證社區(qū)劃分全局性的同時，起到了減小隨機性、平衡社區(qū)規(guī)模的作用。
　　本論文還分別在人工網(wǎng)絡(luò)數(shù)據(jù)集與實際網(wǎng)絡(luò)數(shù)據(jù)集上對預(yù)處理模型和RW-MLP算法進(jìn)行了測試。數(shù)值計算結(jié)果表明，預(yù)處理模型能夠得到準(zhǔn)確的網(wǎng)絡(luò)結(jié)構(gòu)信息，并且能夠提高社區(qū)發(fā)現(xiàn)算法的劃