基于稠密子圖的社區(qū)發(fā)現(xiàn)算法研究.pdf

1、復(fù)雜網(wǎng)絡(luò)分析在生物網(wǎng)絡(luò)、社會組織結(jié)構(gòu)、搜索引擎及推薦系統(tǒng)中被廣泛應(yīng)用。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中的一個重要特征，一個復(fù)雜網(wǎng)絡(luò)通常包含若干個社區(qū)，社區(qū)內(nèi)部對象連接相對緊密，社區(qū)間對象連接相對稀疏。在從大規(guī)模的復(fù)雜網(wǎng)絡(luò)中進(jìn)行社區(qū)發(fā)現(xiàn)已經(jīng)成為眾多領(lǐng)域研究的熱點(diǎn)之一。發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)有助于分析和理解復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以便人們更好地對其表示的復(fù)雜系統(tǒng)進(jìn)行研究。
　　基于密度的圖聚類算法通過搜索網(wǎng)絡(luò)中局部稠密子圖來識別社區(qū)，在社區(qū)發(fā)現(xiàn)中得

2、到了廣泛應(yīng)用。然而，此類算法會產(chǎn)生大量無法劃入社區(qū)的未聚類節(jié)點(diǎn)。針對此問題，本文對基于稠密子圖的重疊聚類算法進(jìn)行研究，主要包括以下兩方面工作：
　　（1）針對無權(quán)無向網(wǎng)絡(luò)，給出了一種基于稠密子圖的軟聚類算法(BDSG)。算法首先根據(jù)密度閾值搜索網(wǎng)絡(luò)中的稠密子圖得到中心社區(qū)；對無法加入中心社區(qū)的未聚類節(jié)點(diǎn)，定義了一種結(jié)點(diǎn)對社區(qū)的歸屬度，并以此為主要依據(jù)給出中心社區(qū)擴(kuò)展策略，將未聚類節(jié)點(diǎn)分配至某些中心社區(qū)，得到最終的社區(qū)發(fā)現(xiàn)結(jié)果。該中

3、心社區(qū)擴(kuò)展策略確保算法可以發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)。與經(jīng)典的基于密度的圖聚類方法CPM、k-dense算法在5個真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的比較結(jié)果表明BDSG算法在模塊性指標(biāo)與時間效率方面體現(xiàn)了良好性能，同時中心社區(qū)擴(kuò)展策略能在一定程度上提高CPM、k-dense等基于密度算法的聚類有效性。
　?。?）針對帶權(quán)無向網(wǎng)絡(luò)，給出了基于加權(quán)稠密子圖的重疊社區(qū)發(fā)現(xiàn)算法（OCDW）。算法首先綜合考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及網(wǎng)絡(luò)本身邊權(quán)重信息，給出了一種網(wǎng)絡(luò)中

4、邊權(quán)重的定義方法，進(jìn)而給出點(diǎn)權(quán)重定義方式，選擇權(quán)重最大的節(jié)點(diǎn)作為種子節(jié)點(diǎn)；定義了子圖的社區(qū)適應(yīng)度函數(shù)，將種子節(jié)點(diǎn)逐步擴(kuò)展成為稠密子圖作為中心社區(qū)；最終將未聚類節(jié)點(diǎn)按照歸屬度進(jìn)行中心社區(qū)分配，通過合并優(yōu)化過程得到最終社區(qū)發(fā)現(xiàn)結(jié)果。與k-dense、CPM、MCODE、HC-PIN、MDOS及BGLL算法在6個無權(quán)網(wǎng)絡(luò)和3個帶權(quán)網(wǎng)絡(luò)的比較結(jié)果表明算法 OCDW在F度量、準(zhǔn)確度、分離度、標(biāo)準(zhǔn)互信息、調(diào)整蘭德系數(shù)、模塊性及運(yùn)行時間等方面均表現(xiàn)出