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

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

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

【部分圖文】：

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

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

其中，Acca表示算法a在某一數(shù)據(jù)集上的聚類(lèi)準(zhǔn)確率，mjaxAcca表示對(duì)于同一數(shù)據(jù)集而言參與比較的算法中最高聚類(lèi)準(zhǔn)確率的值。由上式可知，對(duì)于一個(gè)數(shù)據(jù)集來(lái)說(shuō)最好的算法a*代表其Ra*=1，同時(shí)其他的算法。Ra越大，代表算法a在該數(shù)據(jù)集上有更好的表現(xiàn)。因此，對(duì)于所有數(shù)據(jù)集的Ra的和可以看作是算法a的魯棒性的度量，和越大表示魯棒性越好。對(duì)于本文算法與LEMON算法來(lái)說(shuō)，我們分別在8種不同的數(shù)據(jù)集上對(duì)兩種算法進(jìn)行了測(cè)試，結(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é)論


本文編號(hào)：3023609