重疊社團(tuán)檢測是復(fù)雜網(wǎng)絡(luò)中的一個(gè)重要研究領(lǐng)域,在眾多重疊社團(tuán)檢測算法中,基于局部譜提出的LEMON（Local Expansion via Minimum One Norm）算法復(fù)雜度小、效率高,但在處理含有噪聲的數(shù)據(jù)集時(shí)并不能得到很好的社團(tuán)檢測結(jié)果。針對噪聲問題提出了一種基于正則拉普拉斯矩陣的LEMON改進(jìn)算法。該算法通過矩陣擾動(dòng)的方式構(gòu)建正則拉普拉斯矩陣來表征復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)信息,提高了原LEMON算法的抗噪性。在Amazon,Youtube,DBLP,Orkut數(shù)據(jù)集上的實(shí)驗(yàn)表明本文算法相較于原LEMON算法可以獲得更魯棒的結(jié)果。 

【文章來源】：西南科技大學(xué)學(xué)報(bào). 2020,35(02)

【文章頁數(shù)】：6 頁

【部分圖文】：

本文算法與LEMON算法的帶噪實(shí)驗(yàn)結(jié)果

在復(fù)雜網(wǎng)絡(luò)的計(jì)算中，數(shù)據(jù)集常常由大量的節(jié)點(diǎn)與邊組成，如果對所有節(jié)點(diǎn)和邊進(jìn)行逐一計(jì)算無疑會加大計(jì)算成本�？紤]到對于單一節(jié)點(diǎn)來說，它的鄰居(或者距離較近的)節(jié)點(diǎn)群對比于離它較遠(yuǎn)的節(jié)點(diǎn)群來說有更大的概率屬于同一社團(tuán)，通過局部圖[10]方法我們可以圍繞種子節(jié)點(diǎn)來生成一個(gè)子圖GS，替代全圖G進(jìn)行計(jì)算，這樣的話我們既可以盡可能多地找到待測社團(tuán)中的節(jié)點(diǎn)，同時(shí)又能減少計(jì)算復(fù)雜度。構(gòu)建子圖的過程大致如圖1所示，對于初始種子節(jié)點(diǎn)3來說，通過隨機(jī)游走算法我們選擇距離其較近的節(jié)點(diǎn)6,2,5,10,9，剔除掉較遠(yuǎn)的1,4,7,8節(jié)點(diǎn)，構(gòu)建一個(gè)相較于原圖G={1,2,3,4,5,6,7,8,9,10}來說節(jié)點(diǎn)更少的子圖GS={2,10,3,9,5,6}。在本實(shí)驗(yàn)中，我們采用的是局部圖的方法從初始的種子節(jié)點(diǎn)的集合開始隨機(jī)游走選擇出其中概率較大的節(jié)點(diǎn)(概率越大表示越有可能是待測社團(tuán)中的節(jié)點(diǎn))，剔除掉概率較小的節(jié)點(diǎn)。直到概率分布擴(kuò)散到β|C|avg個(gè)節(jié)點(diǎn)當(dāng)中。其中β|C|avg需要足夠大，應(yīng)盡可能多地包含待測社團(tuán)中的節(jié)點(diǎn)。其中β是一個(gè)常數(shù)，|C|avg為數(shù)據(jù)網(wǎng)絡(luò)中社團(tuán)的平均大小。最初的種子集合中一般只含有2個(gè)節(jié)點(diǎn)[6]，算法的迭代過程中，種子集合中不斷加入新的節(jié)點(diǎn)，這些節(jié)點(diǎn)都是大概率為待測社團(tuán)中的節(jié)點(diǎn)。直覺上來說向種子集合中加入與種子節(jié)點(diǎn)不相關(guān)的節(jié)點(diǎn)會不可避免地造成節(jié)點(diǎn)傳導(dǎo)率(conductance)[11]的增加，所以找到一個(gè)低傳導(dǎo)率的集合更能確保集合內(nèi)節(jié)點(diǎn)之間的鏈接更緊密，也就是說其包含的節(jié)點(diǎn)更大概率屬于同一社團(tuán)。同時(shí)，通過對傳導(dǎo)率的計(jì)算[12]，可以對算法的輸出進(jìn)行界定，防止添加過多的不相關(guān)節(jié)點(diǎn)導(dǎo)致社團(tuán)檢測的效率降低。

其中，Acca表示算法a在某一數(shù)據(jù)集上的聚類準(zhǔn)確率，mjaxAcca表示對于同一數(shù)據(jù)集而言參與比較的算法中最高聚類準(zhǔn)確率的值。由上式可知，對于一個(gè)數(shù)據(jù)集來說最好的算法a*代表其Ra*=1，同時(shí)其他的算法。Ra越大，代表算法a在該數(shù)據(jù)集上有更好的表現(xiàn)。因此，對于所有數(shù)據(jù)集的Ra的和可以看作是算法a的魯棒性的度量，和越大表示魯棒性越好。對于本文算法與LEMON算法來說，我們分別在8種不同的數(shù)據(jù)集上對兩種算法進(jìn)行了測試，結(jié)果如圖3所示。本文算法在8種數(shù)據(jù)集上的Ra值分別為1.000,1.000,1.000,0.579,1.000,0.778,1.000,1.000，即本文算法的總Ra=7.357大于原LEMON算法的總Ra=7.106(如柱狀圖3所示，左邊本文算法的總Ra值明顯高于右邊LEMON算法的總Ra值)。綜上所述，雖然本文算法在“Youtube with Noise”以及Orkut數(shù)據(jù)集上的表現(xiàn)稍差于原LEMON算法，但總體而言，本文算法的表現(xiàn)依然優(yōu)于原LEMON算法，即本文算法比LEMON算法更具魯棒性。5 結(jié)論


本文編號：3023609