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

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

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

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