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

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

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

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

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

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