復雜網(wǎng)絡社區(qū)結構劃分方法

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

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

盡管復雜網(wǎng)絡的社區(qū)發(fā)現(xiàn)問題得到了大量的研究，但還存在一些尚未解決的基本問題，如社區(qū)概念雖然大量使用，但卻缺少嚴格的數(shù)學定義；大多數(shù)社區(qū)發(fā)現(xiàn)算法雖然性能優(yōu)越，但所需計算量卻很大。這說明復雜網(wǎng)絡中社區(qū)發(fā)現(xiàn)的研究還需要付出大量的努力。關于復雜網(wǎng)絡社區(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