基于局部信息的重疊社團(tuán)發(fā)現(xiàn)算法研究.pdf

1、現(xiàn)實(shí)世界中許多系統(tǒng)都可以用復(fù)雜網(wǎng)絡(luò)來(lái)表示,社團(tuán)結(jié)構(gòu)是許多實(shí)際復(fù)雜網(wǎng)絡(luò)中都存在的一個(gè)特征。探索復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu),可以幫助我們了解網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)和特性,進(jìn)而發(fā)現(xiàn)網(wǎng)絡(luò)中存在的規(guī)律,預(yù)測(cè)網(wǎng)絡(luò)的行為和功能。因而,復(fù)雜網(wǎng)絡(luò)中的社團(tuán)發(fā)現(xiàn)得到越來(lái)越多人的關(guān)注。目前,研究者們已經(jīng)對(duì)社團(tuán)發(fā)現(xiàn)投入大量的研究,提出了一系列的社團(tuán)發(fā)現(xiàn)算法。
　　社團(tuán)發(fā)現(xiàn)方法可大致分為全局社團(tuán)發(fā)現(xiàn)和局部社團(tuán)發(fā)現(xiàn)。局部社團(tuán)發(fā)現(xiàn)依據(jù)節(jié)點(diǎn)的局部拓?fù)湫畔?在降低時(shí)間和空間的消耗

2、上具有很大的擴(kuò)展性。同時(shí),現(xiàn)實(shí)中的許多復(fù)雜網(wǎng)絡(luò)系統(tǒng)中,節(jié)點(diǎn)往往具有多個(gè)屬性,使得節(jié)點(diǎn)可能屬于多個(gè)社團(tuán),因而基于局部信息的重疊社團(tuán)發(fā)現(xiàn)具有更大的實(shí)用價(jià)值。
　　Newman提出基于貪婪思想的Newman快速算法,同時(shí)提出評(píng)價(jià)社團(tuán)劃分質(zhì)量的標(biāo)準(zhǔn)——模塊度。Clauset等人在該算法的基礎(chǔ)上,引入堆的數(shù)據(jù)結(jié)構(gòu)計(jì)算和更新模塊度,提出新的算法CNM算法。算法時(shí)間復(fù)雜度接近線性,適用于大規(guī)模網(wǎng)絡(luò)。但CNM算法由于使用全局模塊度優(yōu)化發(fā)現(xiàn)社團(tuán),存

3、在難以發(fā)現(xiàn)小社團(tuán)的問(wèn)題。
　　由Radicchi等人提出的弱社團(tuán)是一種定義比較小的社團(tuán)定義,網(wǎng)絡(luò)中滿足弱社團(tuán)定義的社團(tuán)有很多,因此會(huì)發(fā)現(xiàn)大量的弱社團(tuán)。但是弱社團(tuán)也是一種有實(shí)際意義且被許多學(xué)者認(rèn)可的社團(tuán)定義。
　　在研究和學(xué)習(xí)社團(tuán)發(fā)現(xiàn)算法的基礎(chǔ)上,提出LCNM算法,解決CNM算法難以發(fā)現(xiàn)小社團(tuán)問(wèn)題。使用LFM算法中提出的基于局部信息的局部適應(yīng)度函數(shù)發(fā)現(xiàn)網(wǎng)絡(luò)中的弱社團(tuán),將大量的弱社團(tuán)集構(gòu)成新的網(wǎng)絡(luò)作為CNM算法的輸入。由于一個(gè)節(jié)