基于局部擴(kuò)充與優(yōu)化的重疊社群檢測(cè)算法的研究.pdf

1、生物信息學(xué)、社會(huì)網(wǎng)絡(luò)、web分析等方面的發(fā)展積累了大量的復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)信息，及時(shí)快速的挖掘出這類數(shù)據(jù)中的社群結(jié)構(gòu)已成為數(shù)據(jù)挖掘領(lǐng)域一項(xiàng)重要的工作。傳統(tǒng)算法在對(duì)社群定義中的一個(gè)特點(diǎn)是社群之間是不相交的，而現(xiàn)實(shí)數(shù)據(jù)圖結(jié)構(gòu)中，一個(gè)節(jié)點(diǎn)往往是從屬于多個(gè)社群的，即社群之間存在重疊。加之?dāng)?shù)據(jù)圖結(jié)構(gòu)的多樣性特點(diǎn)，使開發(fā)一種快速而準(zhǔn)確的算法對(duì)數(shù)據(jù)圖結(jié)構(gòu)進(jìn)行重疊社群檢測(cè)成為一種極具挑戰(zhàn)性的工作。本文主要對(duì)重疊社群檢測(cè)算法進(jìn)行了研究。
　　2009年A

2、ndreaLancichinetti等人提出的LFK算法，是一種高效的重疊社群檢測(cè)算法，它提出了一種高效的局部擴(kuò)充優(yōu)化的模型對(duì)社群進(jìn)行檢測(cè)，并針對(duì)社群重疊的情形設(shè)計(jì)了高效的實(shí)驗(yàn)評(píng)估指標(biāo)用于算法準(zhǔn)確度的評(píng)估。在此基礎(chǔ)上，2010年ConradLee等人提出了GreedyCliqueExpansion(GCE)算法，解決了LFK算法對(duì)于某些特殊種子循環(huán)擴(kuò)充而無(wú)法停止的問(wèn)題。這類算法簡(jiǎn)單高效，同時(shí)存在一些不足和可供改進(jìn)的地方：①算法內(nèi)部流程可

3、調(diào)整拆分，使算法存在并行化可能；②局部擴(kuò)充優(yōu)化函數(shù)中的α因子可被考慮進(jìn)社群成長(zhǎng)過(guò)程，從而使算法自適應(yīng)的選取α，減少運(yùn)算前手動(dòng)的對(duì)α的選取，從而使算法能更快收斂至最優(yōu)結(jié)果。
　　本文針對(duì)GCE算法中這些可供改進(jìn)的地方，進(jìn)行了一系列具有針對(duì)性的研究，研究?jī)?nèi)容和取得成果如下：
　?、賹ⅵ烈蜃拥淖赃m應(yīng)機(jī)制引入到GCE算法中。
　　新方法中，通過(guò)分析社群成長(zhǎng)的局部擴(kuò)充優(yōu)化函數(shù)，變換調(diào)整了社群局部擴(kuò)充優(yōu)化的機(jī)制，使算法在保持準(zhǔn)確性

4、的基礎(chǔ)上能對(duì)α因子進(jìn)行自適應(yīng)的選取，從而去除了在算法開始前，手動(dòng)設(shè)定α因子值大小的繁瑣操作。并且在引入α因子自適應(yīng)機(jī)制后，通過(guò)在此模型基礎(chǔ)上對(duì)擴(kuò)展備選集合的進(jìn)一步縮減，從而提升了算法速度，彌補(bǔ)了α因子自適應(yīng)模型中的性能丟失。
　?、趯⒉⑿谢Ｐ鸵氲紾CE算法中。
　　新方法在分析現(xiàn)有GCE算法流程及原理的基礎(chǔ)上，通過(guò)將GCE算法中種子的擴(kuò)充過(guò)程和備選社群的過(guò)濾過(guò)程進(jìn)行分拆至不同CPU上，使算法足以在任務(wù)級(jí)上達(dá)到并行。同時(shí)將

5、各個(gè)環(huán)節(jié)的任務(wù)拆分為處理子數(shù)據(jù)集的子任務(wù)，使得算法進(jìn)一步在數(shù)據(jù)級(jí)上同步，并運(yùn)用當(dāng)前計(jì)算機(jī)的多核優(yōu)勢(shì)進(jìn)行并行計(jì)算，從而提升算法的執(zhí)行速率。
　?、蹖?duì)上述算法的改進(jìn)進(jìn)行了實(shí)驗(yàn)分析和驗(yàn)證。
　　首先在眾多評(píng)價(jià)指標(biāo)中確定了以改進(jìn)的NMI標(biāo)準(zhǔn)互信息量指標(biāo)作為算法準(zhǔn)確度評(píng)價(jià)指標(biāo)。然后根據(jù)LFR模型構(gòu)造出了不同類別的人造數(shù)據(jù)圖結(jié)構(gòu)，對(duì)GCE算法及改進(jìn)后算法進(jìn)行了實(shí)驗(yàn)分析和驗(yàn)證。最后通過(guò)對(duì)來(lái)源于Combined-AP/MS網(wǎng)絡(luò)的蛋白質(zhì)交互信