復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分方法

復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分方法已有3661次閱讀2009-4-3008:38|個(gè)人分類:科研筆記|系統(tǒng)分類:科研筆記|關(guān)鍵詞:網(wǎng)絡(luò)，系統(tǒng)，復(fù)雜網(wǎng)絡(luò)，社區(qū)結(jié)構(gòu)，聚類，劃分方法隨著對(duì)網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)共同性質(zhì)，即社區(qū)結(jié)構(gòu)。也就是說(shuō)，整個(gè)網(wǎng)絡(luò)是由若干個(gè)“社區(qū)”或“組”構(gòu)成的。每個(gè)社區(qū)內(nèi)部的結(jié)點(diǎn)間的連接相對(duì)非常緊密，但是各個(gè)社區(qū)之間的連接相對(duì)來(lái)說(shuō)卻比較稀疏[1][2]。揭示網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)，對(duì)于深入了解網(wǎng)絡(luò)結(jié)構(gòu)與分析網(wǎng)絡(luò)特性是很重要的。如社會(huì)網(wǎng)絡(luò)中的社區(qū)代表根據(jù)興趣和背景而形成的真實(shí)的社會(huì)團(tuán)體；引文網(wǎng)絡(luò)中的社區(qū)代表針對(duì)同一主題的相關(guān)論文；萬(wàn)維網(wǎng)中的社區(qū)就是討論相關(guān)主題的若干網(wǎng)站[3]；而生物化學(xué)網(wǎng)絡(luò)或者電子電路中的網(wǎng)絡(luò)社區(qū)可以是某一類功能單元[4][5]。發(fā)現(xiàn)這些網(wǎng)絡(luò)中的社區(qū)有助于我們更加有效的理解和開(kāi)發(fā)這些網(wǎng)絡(luò)。

在復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的研究中，社區(qū)結(jié)構(gòu)劃分算法所要?jiǎng)澐值木W(wǎng)絡(luò)大致可分為兩類，一類是比較常見(jiàn)的網(wǎng)絡(luò)，即僅包含正聯(lián)系的網(wǎng)絡(luò)(網(wǎng)絡(luò)中邊的權(quán)值為正實(shí)數(shù))；另一類是符號(hào)社會(huì)網(wǎng)絡(luò)，即網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負(fù)向聯(lián)系的邊。因此劃分網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法相應(yīng)分為兩大類，而對(duì)于第一類網(wǎng)絡(luò)又提出了許多不同的社區(qū)結(jié)構(gòu)劃分算法，劃分第一類網(wǎng)絡(luò)社區(qū)的傳統(tǒng)算法可分為兩大類，第一類是基于圖論的算法，比如K-L算法[6]、譜平分法[7][8]、隨機(jī)游走算法[9]和派系過(guò)濾算法[10][11]等；第二類是層次聚類算法，比如基于相似度度量的凝聚算法[2]和基于邊介數(shù)度量的分裂算法[1][12][13]等。最近幾年從其他不同的角度又提出了許多劃分第一類網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法，大致可劃分如下：基于電阻網(wǎng)絡(luò)性質(zhì)的算法[14]、基于信息論的算法[15]、基于PCA的算法[16]和最大化模塊度[17]的算法[18-23]等。對(duì)于符號(hào)網(wǎng)絡(luò)，Doreian和Mrvar提出了一種利用局部搜索劃分符號(hào)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法[24]，且BoYang等提出一種基于代理的啟發(fā)式劃分符號(hào)網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法(FEC)[25]。

盡管復(fù)雜網(wǎng)絡(luò)的社區(qū)發(fā)現(xiàn)問(wèn)題得到了大量的研究，但還存在一些尚未解決的基本問(wèn)題，如社區(qū)概念雖然大量使用，但卻缺少嚴(yán)格的數(shù)學(xué)定義；大多數(shù)社區(qū)發(fā)現(xiàn)算法雖然性能優(yōu)越，但所需計(jì)算量卻很大。這說(shuō)明復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的研究還需要付出大量的努力。關(guān)于復(fù)雜網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)問(wèn)題更加系統(tǒng)深入的最新進(jìn)展情況請(qǐng)看2009長(zhǎng)篇綜述文章CommunityDetectioningraphsbySantoFortunato(arXiv:0906.0612)

參考文獻(xiàn)

[1]

GirvanM,NewmanMEJ.Communitystructureinsocialandbiologicalnetworks[J].PNAS,2001,99(12):7821-7826.

[2]

NewmanMEJ.Fastalgorithmfordetectingcommunitystructureinnetworks[J].PhysicalReviewE,2004,69(6):066133.[21]A.Medus,G.Acu?a,andC.O.Dorso.Detectionofcommunitystructuresinnetworksviaglobaloptimization[J].PhysicaA,2005,358:593-604.

[22]J.ReichardtandS.Bornholdt.StatisticalMechanicsofCommunityDetection[J].Phys.Rev.E,2006,74:016110.

[23]NewmanMEJ.Findingcommunitystructureinnetworksusingtheeigenvectorsofmatrices[J].PhysicalReviewE,2006,74(3):036104.

[24]P.DoreianandA.Mrvar.APartitioningApproachtoStructuralBalance[J].Social

Networks,1996,18(2):149-168.

[25]BoYang,WilliamK.Cheung,andJimingLiu.CommunityMiningfromSi