复杂网络的社团结构分析.ppt

1,章祥荪,复杂网络的社团结构分析Communitystructureincomplexnetworks,中国科学院数学与系统科学研究院全国复杂网络会议，苏州大学，2010，10,17,复杂网络的动态性质研究复杂网络的静态结构研究小世界(Smallworld)，尺度无关（Scalefree)，聚类特性(Clustering)的确切数学模型。社团结构(CommunityStructure),2,3,复杂网络的模块化性质,复杂网络中存在模块或者社区结构(ModuleorCommunitystructure)模块或者社区定义为网络中内部连接稠密，与外部连接稀疏的节点的集合(FilippoRadicchiet.al.PNAS,Vol.101,No.9,2658-2663,2004).数学表述:其中V是子图，K是顶点的度。即子图V是模块的条件是模块内顶点的内部连边的度值之和大于模块内顶点的外部连边的度值之和。PNAS-Proc.Natl.Acad.Sci.USA美国科学院院刊,4,模块划分的重要性,许多复杂网络共有的性质。研究模块结构有助于研究整个网络的结构和功能,圣塔菲研究所的科学家合作网：模块代表从事相似领域研究的科学家集合,数学生态学,统计物理,5,MartinRosvall,CarlT.Bergstrom,PNAS,vol.105,no.4.1118-1123,2007,自然科学论文引用网络：6128期刊,约600万次引用，,划分为88个模块和3024条模块间的连接，刻画了学科之间的联系,6,一个社会网络的例子,1970年美国大学里的一个空手道俱乐部关系网络：节点是其34名成员，边是他们两年间的友谊关系，边数为78。俱乐部里的矛盾导致其分裂为两个小的俱乐部。问题是能否用网络的模块结构来重现这个过程？它是模块探测研究中的经典例子。,W.W.Zachary,Aninformationflowmodelforconflictandfissioninsmallgroups,JournalofAnthropologicalResearch33,452-4731977,Girvan,M,Newman,M.,Proc.Natl.Acad.Sci,2002Ravasz,E,Somera,A,Mongru,D,Oltvai,Z,Barabasi,A.,Science,2002Radicchi,F,Castellano,C,Cecconi,F.,Proc.Natl.Acad.Sci,2004Guimera,R,Mossa,S,Turtschi,A.,Proc.Natl.Acad.Sci,2005Guimera,R,Amaral,L.,Nature,2005Newman,M.,Proc.Natl.Acad.Sci,2006Rosvall,M,Bergstrom,C.,Proc.Natl.Acad.Sci,2007Fortunato,S,Barthelemy,M.,Proc.Natl.Acad.Sci,2007Weinan,E,Li,T,Vanden-Eijnden,E.,Proc.Natl.Acad.Sci,2008Rosvall,M,Bergstrom,C.,Proc.Natl.Acad.Sci,2008PeterJ.Mucha,etal.,Science2010Yong-YeolAhn,JamesP.BagrowGuimera,Nature,2005).Resolutionlimit现象,12,极端例子：ringofcliques,Fortunato&Barthelemy,Proc.Natl.Acad.Sci.USA104(1),36-41(2007),13,提出新的模块化指标D值,模块化密度函数D:,ZhenpingLi,ShihuaZhang,Rui-ShengWang,Xiang-SunZhang,LuonanChen,Quantitativefunctionforcommunitydetection.PhysicalReviewE,77,036109,2008,14,D值克服了Q值存在的resolutionlimit问题,15,结果,Q值,D值,划分正确的顶点的比例,错分现象-Misidentification,用Q或D作优化可能得到不满足定义的模块,Qpartitionsthenetworkintothreecommunities(twoKnandoneK5)whenn=16(respectively,n=21),inwhichK5isasub-graphviolatingallreasonablecommunitydefinition.,Xiang-SunZhang,Rui-ShengWang,YongWang,Ji-GuangWang,Yu-QingQiu,LinWang,andLuonanChen.Modularityoptimizationincommunitydetectionofcomplexnetworks.EurophysicsLetters(EPL),87,2009.被评为EPL2009bestpaper,16,17,该文的主要贡献是用离散凸规划的概念对两个重要问题进行解析分析,Q值和D值的最优化模型都是非线性整数规划目标函数的凸性和凹性无法解析得到对两个具有特殊结构的网络进行分析引入离散凸规划（变量是离散的，可以嵌入一个连续的凸规划）的概念进行分析,得到解析解,所有对modularity进行研究的论文(指上面所列的的PNAS,Nature,Sience文章)都是试题论证的,即没有解析的证明.为了彻底分析resolutionlimit和Misidentification现象，我们对两类典型网络建立了优化模型,引入了离散凸分析技术,得到了两类问题的解析解.,生物信息学与最优化方法,18,这两个例子出现在PNAS中几乎所有讨论网络模块探测的论文里,基于特殊结构的凸分析,adhocnetwork,ringofdenselumps,Finding1对,生物信息学与最优化方法,21,Finding2,Finding3,解析解表明，对这两个经典的算例，Q和D都有Resolutionlimit和Misidentification的现象产生，所以Q和D均只是近似的定量评估函数。网络社团划分的问题可以用一个优化问题来精确描述，我们证明了这一模型是NP-hard的。我们相信用优化理论可以彻底解决网络社团划分的问题。网络科学是运筹学的下一个热点。,22,23,为了彻底解决这些问题,提出一个新的OR模型和相应的算法，这一算法不会产生resolutionlimit和mis-identification现象,Xiang-SunZhang,ZhenpingLi,Rui-ShengWang,YongWang.AcombinatorialmodelandalgorithmforgloballysearchingcommunitystructureincomplexnetworksJournalofCombinatorialOptimization(JCO),2010.,DOI:10.1007/s10878-010-9356-0,AnewORmodel,Problemdefinition:Givenanetwork,thecommunityidentificationproblemistopartitionthenetworkintoasmanynon-overlappingsub-networksaspossiblesuchthateachsub-networksatisfiesagivencommunitydefinition.,24,以上文字定义可以用一个整数线性规划来描述,我们证明了这个模型是NP-hard.,25,Aqualifiedmin-cut(QMC)algorithm,Aheuristicprincipleisgiventofindafeasiblepartitionwiththelargestnumberofcommunities.Itisrealizedbyamin-cutoperation:Amin-cutoperationiscalledqualifiedifthetworesultingsub-networkssatisfythemoduledefinition.Thecommunityidentificationproblemcanbesolvedbasedonaseriesofqualifiedmin-cutoperations.,26,Experimentresults(artificialnetworks),Ringsofcliques,Unevenad-hocnetwork,27,Experimentresults(realnetworks),Footballteamnetwork,Jazzmusiciannetwork,28,致谢,This