复杂网络社区结构划分方法已有3661次阅读2009-4-3008:38|个人分类:科研笔记|系统分类:科研笔记|关键词:网络，系统，复杂网络，社区结构，聚类，划分方法随着对网络性质的物理意义和数学特性的深入研究，人们发现许多实际网络都具有一个共同性质，即社区结构。也就是说，整个网络是由若干个“社区”或“组”构成的。每个社区内部的结点间的连接相对非常紧密，但是各个社区之间的连接相对来说却比较稀疏[1][2]。揭示网络的社区结构，对于深入了解网络结构与分析网络特性是很重要的。如社会网络中的社区代表根据兴趣和背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站[3]；而生物化学网络或者电子电路中的网络社区可以是某一类功能单元[4][5]。发现这些网络中的社区有助于我们更加有效的理解和开发这些网络。在复杂网络社区结构划分的研究中，社区结构划分算法所要划分的网络大致可分为两类，一类是比较常见的网络，即仅包含正联系的网络(网络中边的权值为正实数)；另一类是符号社会网络，即网络中既包含正向联系的边，也包含负向联系的边。因此划分网络中社区结构的算法相应分为两大类，而对于第一类网络又提出了许多不同的社区结构划分算法，划分第一类网络社区的传统算法可分为两大类，第一类是基于图论的算法，比如K-L算法[6]、谱平分法[7][8]、随机游走算法[9]和派系过滤算法[10][11]等；第二类是层次聚类算法，比如基于相似度度量的凝聚算法[2]和基于边介数度量的分裂算法[1][12][13]等。最近几年从其他不同的角度又提出了许多划分第一类网络社区结构的算法，大致可划分如下：基于电阻网络性质的算法[14]、基于信息论的算法[15]、基于PCA的算法[16]和最大化模块度[17]的算法[18-23]等。对于符号网络，Doreian和Mrvar提出了一种利用局部搜索划分符号网络社区结构的算法[24]，且BoYang等提出一种基于代理的启发式划分符号网络社区结构的算法(FEC)[25]。尽管复杂网络的社区发现问题得到了大量的研究，但还存在一些尚未解决的基本问题，如社区概念虽然大量使用，但却缺少严格的数学定义；大多数社区发现算法虽然性能优越，但所需计算量却很大。这说明复杂网络中社区发现的研究还需要付出大量的努力。关于复杂网络社区发现问题更加系统深入的最新进展情况请看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.[3]FellDA,WagnerA.Thesmallworldofmetabolism[J].Nature(Biotechnology,2000,(18):1121-1122.[4]Pooll,KochenM.ContactsandInfluence[J].SocialNetworks,1978,(1):1-48.[5]MilgramS.Thesmallworldproblem[J].PsychologyToday,1967,(2):60-67.[6]KernighanBW,LinS.Anefficientheuristicprocedureforportioninggraphs[J].BellSystemTechnicalJournal,1970,49:291-307.[7]FiedlerM.Algebraicconnectivityofgraphs[J].CzechoslovakMathematicalJournal,1973,23(98):298-305.[8]PothenA,SimonH,LiouKP.Partitioningsparsematriceswitheigenvectorsofgraphs[J].SIAMJournalonMatrixAnalysisandApplications.1990,11(3):430-452.[9]P.PonsandM.Latapy.ComputingCommunitiesinLargeNetworksUsingRandomWalks[J].ComputerandInformationSciences.2005,284-293.[10]G.Palla,I.Derenyi,I.Farkasetal.UncoveringtheOverlappingCommunityStructureofComplexNetworksinNatureandSociety[J].Nature,2005435(7043):814-818.[11]G.Palla,I.Farkas,P.Pollner,I.Derenyietal.Directednetworkmodules[J].Phys.New.J,2007,186.[12]TylerJ,WilkinsonD,HubermanB.Emailasspectroscopy:Automateddiscoveryofcommunitystructurewithinorganizations[C].InternationalConferenceonCommunitiesandTechnologies,2003,81-96.[13]F.Radicchi,C.Castellano,F.Cecconietal.Definin...
