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

1、現(xiàn)實世界中許多系統(tǒng)都可以用復雜網(wǎng)絡來表示,社團結構是許多實際復雜網(wǎng)絡中都存在的一個特征。探索復雜網(wǎng)絡中的社團結構,可以幫助我們了解網(wǎng)絡的內部結構和特性,進而發(fā)現(xiàn)網(wǎng)絡中存在的規(guī)律,預測網(wǎng)絡的行為和功能。因而,復雜網(wǎng)絡中的社團發(fā)現(xiàn)得到越來越多人的關注。目前,研究者們已經對社團發(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)絡系統(tǒng)中,節(jié)點往往具有多個屬性,使得節(jié)點可能屬于多個社團,因而基于局部信息的重疊社團發(fā)現(xiàn)具有更大的實用價值。
　　Newman提出基于貪婪思想的Newman快速算法,同時提出評價社團劃分質量的標準——模塊度。Clauset等人在該算法的基礎上,引入堆的數(shù)據(jù)結構計算和更新模塊度,提出新的算法CNM算法。算法時間復雜度接近線性,適用于大規(guī)模網(wǎng)絡。但CNM算法由于使用全局模塊度優(yōu)化發(fā)現(xiàn)社團,存

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