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

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

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

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

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