基于局部?jī)?yōu)化的重疊社區(qū)發(fā)現(xiàn)方法研究.pdf

1、現(xiàn)實(shí)世界中的很多事物都是以網(wǎng)絡(luò)形態(tài)存在的，例如在線社交，人際關(guān)系，人體蛋白質(zhì)模型等。隨著人們對(duì)復(fù)雜網(wǎng)絡(luò)研究的深入，社區(qū)結(jié)構(gòu)作為復(fù)雜網(wǎng)絡(luò)中的一個(gè)重要特性被逐漸重視起來(lái)。社區(qū)能夠有效地反應(yīng)網(wǎng)絡(luò)中節(jié)點(diǎn)之間的關(guān)系，對(duì)于復(fù)雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的研究有助于人們更加深入的了解網(wǎng)絡(luò)系統(tǒng)的結(jié)構(gòu)特性及其演化規(guī)律，以便人們更好的改善現(xiàn)實(shí)生活。這也正是近年來(lái)社區(qū)發(fā)現(xiàn)問題成為復(fù)雜網(wǎng)絡(luò)領(lǐng)域研究熱點(diǎn)的原因。而重疊社區(qū)的發(fā)現(xiàn)可以更為準(zhǔn)確的理解網(wǎng)絡(luò)內(nèi)部的拓?fù)浣Y(jié)構(gòu)信息，在近些

2、年的研究中得到了越來(lái)越多的關(guān)注。
　　針對(duì)重疊社區(qū)的發(fā)現(xiàn)問題，目前已出現(xiàn)了許多研究成果，總體上可以分為全局優(yōu)化和局部?jī)?yōu)化兩大類。基于全局優(yōu)化的社區(qū)發(fā)現(xiàn)方法主要從全局的角度劃分整個(gè)網(wǎng)絡(luò)，需要整個(gè)網(wǎng)絡(luò)結(jié)構(gòu)信息，目前主要包括圖劃分、層次聚類、模塊度優(yōu)化、譜聚類及基于模型的方法等?；诰植繑U(kuò)展的方法一般根據(jù)定義的社區(qū)局部度量，從給定的初始節(jié)點(diǎn)逐步合并引起最大的社區(qū)度量增量的近鄰節(jié)點(diǎn)，如局部擴(kuò)展優(yōu)化、標(biāo)簽傳播、派系過濾、局部邊聚類優(yōu)化等，并

3、在社交網(wǎng)絡(luò)分析中有廣泛的應(yīng)用。
　　本文圍繞局部拓展優(yōu)化中的代表算法 LFM，針對(duì)其在社區(qū)劃分過程中存在的劃分速度較慢和結(jié)果不夠穩(wěn)定兩大問題開展研究，提出針對(duì)性的解決方案。本文主要研究工作包括如下：
　　首先，針對(duì)LFM算法劃分速度較慢的情況，提出了一種基于“核心區(qū)域”的改進(jìn)LFM算法，在改進(jìn)算法中提出了“核心區(qū)域”的概念，并論證在社區(qū)的拓展階段，如果一個(gè)鄰接點(diǎn)屬于該節(jié)點(diǎn)的核心區(qū)域則可以不必再次重復(fù)計(jì)算適應(yīng)度函數(shù)值，從而減少

4、計(jì)算時(shí)間，達(dá)到提高社區(qū)劃分速度的目的。
　　其次，針對(duì)LFM算法得到的社區(qū)劃分結(jié)果不夠穩(wěn)定的問題，提出了一種基于種子節(jié)點(diǎn)篩選的改進(jìn)LFM算法。主要思路是：借鑒GCE算法和CPM算法的思想，在算法開始時(shí)選擇較為優(yōu)質(zhì)的節(jié)點(diǎn)作為種子節(jié)點(diǎn)即對(duì)初始的種子節(jié)點(diǎn)進(jìn)行篩選。具體做法是：引入臨節(jié)點(diǎn)度閾值k，對(duì)于鄰接點(diǎn)度達(dá)不到閾值的節(jié)點(diǎn)不會(huì)被加入種子節(jié)點(diǎn)庫(kù)，從而對(duì)達(dá)到篩選優(yōu)質(zhì)節(jié)點(diǎn)作為種子節(jié)點(diǎn)的目的，進(jìn)而優(yōu)化社區(qū)劃分結(jié)果。
　　最后，對(duì)上述提出的

5、兩種改進(jìn)算法，分別在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)數(shù)據(jù)集中進(jìn)行實(shí)驗(yàn)驗(yàn)證。對(duì)于真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集，我們選取的是認(rèn)同度較高的Zachary’s karate club, American College football, Dolphin social network等五組公開數(shù)據(jù)集，使用模塊度函數(shù)作為評(píng)價(jià)指標(biāo)。人工合成網(wǎng)絡(luò)數(shù)據(jù)集則是采用LFR基準(zhǔn)程序進(jìn)行構(gòu)造，使用NMI作為評(píng)價(jià)指標(biāo)。同時(shí)與LFM算法，CPM算法及Copra算法進(jìn)行比較。實(shí)驗(yàn)結(jié)果