復(fù)雜網(wǎng)絡(luò)中的社區(qū)發(fā)現(xiàn)算法研究.pdf

1、隨著復(fù)雜網(wǎng)絡(luò)研究的興起，從復(fù)雜網(wǎng)絡(luò)的角度研究復(fù)雜系統(tǒng)受到了越來越多的關(guān)注?，F(xiàn)實(shí)世界中大量的復(fù)雜系統(tǒng)均可以用復(fù)雜網(wǎng)絡(luò)來描述。社區(qū)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)的重要特性之一，引起了研究者的廣泛關(guān)注。社區(qū)發(fā)現(xiàn)即為挖掘復(fù)雜網(wǎng)絡(luò)中的模塊化的社區(qū)結(jié)構(gòu)的過程，這對(duì)于理解復(fù)雜網(wǎng)絡(luò)的功能、發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中隱藏的規(guī)律和預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)的行為具有重要的意義。然而，隨著網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大，網(wǎng)絡(luò)結(jié)構(gòu)更加復(fù)雜，社區(qū)發(fā)現(xiàn)也變得異常困難。目前，已有的社區(qū)發(fā)現(xiàn)算法還存在以下問題：（1）現(xiàn)有

2、的社區(qū)發(fā)現(xiàn)算法難以準(zhǔn)確地發(fā)現(xiàn)穩(wěn)定的重疊社區(qū)結(jié)構(gòu)；（2）基于節(jié)點(diǎn)的社區(qū)發(fā)現(xiàn)算法難以發(fā)現(xiàn)網(wǎng)絡(luò)中重疊度較高的社區(qū)結(jié)構(gòu)；（3）傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法僅僅關(guān)注網(wǎng)絡(luò)中的模塊化社區(qū)結(jié)構(gòu)，無法進(jìn)一步識(shí)別社區(qū)中的層次關(guān)系。本文針對(duì)上述問題展開研究，主要工作和研究成果如下：
　　1.提出了一種基于非重疊極大子團(tuán)的標(biāo)簽傳播社區(qū)發(fā)現(xiàn)算法。該算法在標(biāo)簽傳播算法的基礎(chǔ)上，對(duì)其進(jìn)行三個(gè)方面的改進(jìn)：在標(biāo)簽初始化階段，通過查找網(wǎng)絡(luò)中非重疊的極大子團(tuán)結(jié)構(gòu)，賦予每個(gè)非重疊

3、的極大子團(tuán)唯一的標(biāo)簽；在標(biāo)簽傳播階段，通過選取具有最大標(biāo)簽傳播率的標(biāo)簽來更新節(jié)點(diǎn)標(biāo)簽；在社區(qū)調(diào)整階段，通過合并相似度較高的社區(qū)來提升社區(qū)發(fā)現(xiàn)的質(zhì)量。將該算法分別應(yīng)用于計(jì)算機(jī)生成網(wǎng)絡(luò)和真實(shí)的社會(huì)網(wǎng)絡(luò)，實(shí)驗(yàn)結(jié)果表明：該算法很好地解決了標(biāo)簽傳播算法的魯棒性問題，并能準(zhǔn)確地發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)。
　　2.提出了一種基于核心鏈路的重疊社區(qū)發(fā)現(xiàn)算法。相較于當(dāng)前的基于節(jié)點(diǎn)的重疊社區(qū)發(fā)現(xiàn)算法，該算法從鏈路的角度出發(fā)，通過選取核心鏈路，并根據(jù)鏈路影

4、響力的強(qiáng)弱不斷吸引外層鏈路進(jìn)而形成鏈路社區(qū)結(jié)構(gòu)；再將鏈路社區(qū)轉(zhuǎn)化為節(jié)點(diǎn)社區(qū)，經(jīng)過節(jié)點(diǎn)社區(qū)調(diào)整后，得到全局最優(yōu)的重疊社區(qū)結(jié)構(gòu)。該算法是一種無監(jiān)督算法，無需輸入額外參數(shù)。將該算法分別應(yīng)用于計(jì)算機(jī)生成網(wǎng)絡(luò)和真實(shí)的社會(huì)網(wǎng)絡(luò)，實(shí)驗(yàn)結(jié)果表明，相較于其它算法，該算法能夠更好地發(fā)現(xiàn)重疊度較高的社區(qū)結(jié)構(gòu)。
　　3.提出了一種基于種子節(jié)點(diǎn)集的社區(qū)層次結(jié)構(gòu)發(fā)現(xiàn)算法。該算法通過選取種子節(jié)點(diǎn)，并根據(jù)余弦相似度的大小添加其最近鄰節(jié)點(diǎn)共同構(gòu)成種子節(jié)點(diǎn)集；再由種