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

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

在復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分的研究中，社區(qū)結(jié)構(gòu)劃分算法所要劃分的網(wǎng)絡(luò)大致可分為兩類，一類是比較常見的網(wǎng)絡(luò)，即僅包含正聯(lián)系的網(wǎng)絡(luò)(網(wǎng)絡(luò)中邊的權(quán)值為正實數(shù))；另一類是符號社會網(wǎng)絡(luò)，即網(wǎng)絡(luò)中既包含正向聯(lián)系的邊，也包含負向聯(lián)系的邊。因此劃分網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的算法相應(yīng)分為兩大類，而對于第一類網(wǎng)絡(luò)又提出了許多不同的社區(qū)結(jié)構(gòu)劃分算法，劃分第一類網(wǎng)絡(luò)社區(qū)的傳統(tǒng)算法可分為兩大類，第一類是基于圖論的算法，比如K-L算法[6]、譜平分法[7][8]、隨機游走算法[9]和派系過濾算法[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]等。對于符號網(wǎng)絡(luò)，Doreian和Mrvar提出了一種利用局部搜索劃分符號網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法[24]，且BoYang等提出一種基于代理的啟發(fā)式劃分符號網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)的算法(FEC)[25]。

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

參考文獻

[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