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

1、復(fù)雜網(wǎng)絡(luò)分析在生物網(wǎng)絡(luò)、社會(huì)組織結(jié)構(gòu)、搜索引擎及推薦系統(tǒng)中被廣泛應(yīng)用。社區(qū)結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)中的一個(gè)重要特征，一個(gè)復(fù)雜網(wǎng)絡(luò)通常包含若干個(gè)社區(qū)，社區(qū)內(nèi)部對(duì)象連接相對(duì)緊密，社區(qū)間對(duì)象連接相對(duì)稀疏。在從大規(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)，以便人們更好地對(duì)其表示的復(fù)雜系統(tǒng)進(jìn)行研究。
　　基于密度的圖聚類(lèi)算法通過(guò)搜索網(wǎng)絡(luò)中局部稠密子圖來(lái)識(shí)別社區(qū)，在社區(qū)發(fā)現(xiàn)中得

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

3、心社區(qū)擴(kuò)展策略確保算法可以發(fā)現(xiàn)網(wǎng)絡(luò)中的重疊社區(qū)結(jié)構(gòu)。與經(jīng)典的基于密度的圖聚類(lèi)方法CPM、k-dense算法在5個(gè)真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的比較結(jié)果表明BDSG算法在模塊性指標(biāo)與時(shí)間效率方面體現(xiàn)了良好性能，同時(shí)中心社區(qū)擴(kuò)展策略能在一定程度上提高CPM、k-dense等基于密度算法的聚類(lèi)有效性。
　?。?）針對(duì)帶權(quán)無(wú)向網(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ū)；最終將未聚類(lèi)節(jié)點(diǎn)按照歸屬度進(jìn)行中心社區(qū)分配，通過(guò)合并優(yōu)化過(guò)程得到最終社區(qū)發(fā)現(xiàn)結(jié)果。與k-dense、CPM、MCODE、HC-PIN、MDOS及BGLL算法在6個(gè)無(wú)權(quán)網(wǎng)絡(luò)和3個(gè)帶權(quán)網(wǎng)絡(luò)的比較結(jié)果表明算法 OCDW在F度量、準(zhǔn)確度、分離度、標(biāo)準(zhǔn)互信息、調(diào)整蘭德系數(shù)、模塊性及運(yùn)行時(shí)間等方面均表現(xiàn)出