基于重疊模塊度的社區(qū)離群點(diǎn)挖掘算法研究.pdf

1、近年來，網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)得到了廣泛而深入的研究。傳統(tǒng)的社區(qū)發(fā)現(xiàn)算法針對的是數(shù)據(jù)間的關(guān)聯(lián)特性，而忽略了數(shù)據(jù)的固有屬性。然而，結(jié)合數(shù)據(jù)的社區(qū)特性和固有屬性挖掘得到的離群點(diǎn)可解釋性更強(qiáng)，社區(qū)離群點(diǎn)就是其中之一?，F(xiàn)有的社區(qū)離群點(diǎn)挖掘算法針對傳統(tǒng)無重疊社區(qū)采用概率模型進(jìn)行挖掘。為了達(dá)到更準(zhǔn)確的社區(qū)劃分，社區(qū)間的重疊現(xiàn)象成了社區(qū)離群點(diǎn)檢測中不可忽略的一部分。因此，優(yōu)秀的社區(qū)離群點(diǎn)檢測算法要做到準(zhǔn)確的社區(qū)劃分和離群點(diǎn)檢測。為了評估社區(qū)劃分的結(jié)果，New

2、man等提出的NG模塊度作為衡量網(wǎng)絡(luò)劃分好壞的標(biāo)準(zhǔn)也引起了學(xué)者的廣泛關(guān)注。但是NG模塊度在應(yīng)用上存在著分辨率限制的缺陷，即通過模塊度優(yōu)化不能檢測到規(guī)模較小但結(jié)構(gòu)顯著的社區(qū)。
　　 因此，挖掘社區(qū)離群點(diǎn)首先需要:1）克服分辨率極限問題，以達(dá)到更準(zhǔn)確的社區(qū)劃分;2）結(jié)合網(wǎng)絡(luò)的社區(qū)特性和對象的固有屬性，在重疊社區(qū)中挖掘到更準(zhǔn)確的社區(qū)離群點(diǎn)。論文的主要工作如下:
　　 (1)提出模塊密度的概念，即模塊內(nèi)平均邊數(shù)與總邊數(shù)的商，并在

3、此基礎(chǔ)上重新構(gòu)造了重疊模塊度函數(shù)—CQ來評價(jià)社區(qū)的劃分，從而解決NG模塊度的分辨率限制、不能分辨小于一定規(guī)模的社區(qū)的問題。理論方式證明，提出的重疊模塊度克服了NG模塊度函數(shù)的分辨率極限問題，經(jīng)典網(wǎng)絡(luò)和真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)驗(yàn)證了構(gòu)造的模塊度的準(zhǔn)確性和有效性。
　　 (2)提出基于重疊模塊度的社區(qū)離群點(diǎn)挖掘算法OCODA(Overlappingcommunityoutlierdetectionalgorithm)以克服現(xiàn)有社區(qū)離群點(diǎn)檢測

4、算法由于忽略社區(qū)間的重疊現(xiàn)象而導(dǎo)致社區(qū)離群點(diǎn)劃分不準(zhǔn)確的問題。兩個(gè)對象屬性值的偏差程度越大，對象間的相似度越小，屬于同一社區(qū)的概率也越小。據(jù)此，提出屬性偏離程度和屬性貢獻(xiàn)因子，并分別引入到相似度和模塊度的計(jì)算中，從而使其適用于社區(qū)離群點(diǎn)挖掘。OCODA首先根據(jù)節(jié)點(diǎn)間的相似度對節(jié)點(diǎn)進(jìn)行聚類，并根據(jù)固有屬性的偏離程度進(jìn)行離群點(diǎn)判斷，若屬性偏離程度高于閾值λ，則將此節(jié)點(diǎn)劃分為社區(qū)離群點(diǎn)，然后根據(jù)重疊模塊度的變化進(jìn)行迭代聚類，若前后兩次的重疊模