社团结构分析PPT课件.ppt

.,1,章祥荪,复杂网络的社团结构分析Communitystructureincomplexnetworks,中国科学院数学与系统科学研究院全国复杂网络会议，苏州大学，2010，10,17,.,2,Bio-molecularnetworks（生物分子网）,许多生物问题,特别是人类的疾病,在分子层面上都可归于“systemsproblems”-LeroyHood许多生物问题可以表达成生物分子网络（bio-molecularnetworks）的问题。生物分子网络包括：蛋白质相互作用网（proteininteractionnetworks）,新陈代谢网（metabolicnetworks），基因调控网（generegulatorynetworks）,e.t.;他们都有共同的性质更为有趣的是，许多这样的网是“复杂”网络,.,3,复杂网络的典型代表:生物分子网络之一-蛋白质相互作用网（Scale-free),酵母细胞中的蛋白质相互作用网络(A.-L.Barabsi,NATUREREVIEWSGENETICS,2004),.,4,Jeong,2000,Nature,包括太古代（Archae），细菌（Becterium),真核生物（Eukaryote）在内的43个物种的新陈代谢网（Metabolicnetwork）都是Scale-free的。,.,5,Protein-proteininteractionnetworks,Rui-ShengWang,YongWang,Ling-YunWu,Xiang-SunZhang,LuonanChen.Analysisonmulti-domaincooperationforpredictingprotein-proteininteractions.BMCBioinformatics,8:391,2007ShihuaZhang,Xue-MeiNingandXiang-SunZhang.IdentificationoffunctionalmodulesinaPPInetworkbycliquepercolationclustering.Computationalbiologyandchemistry,30(6),445-451,2006.LuonanChen,Ling-YunWu,YongWangandXiang-SunZhang.InferringProteinInteractionsfromExperimentalDatabyAssociationProbabilisticMethod.Proteins:Structure,Function,andBioinformatics,Vol.62,pp.833-837,2006.Xiang-SunZhang,Rui-ShengWang,Ling-YunWu,ShihuaZhangandLuonanChen.InferringProtein-ProteinInteractionsbyCombinatorialModels.IFMBEProceedings,Vol.14,2006,183-186,SpringerBerlinHeidelberg.,5,.,6,Metabolicandsignalingnetworks,ZhenpingLi,Rui-ShengWang,Xiang-SunZhangandLuonanChen.Detectingdrugtargetswithminimumsideeffectsinmetabolicnetworks.IETSystemsBiology,3(6),523-533,2009ZhenpingLi,Rui-ShengWang,Xiang-SunZhang.MassFlowModelandEssentialityofEnzymesinMetabolicNetworks.LectureNotesinOperationsResearch,9,pp.182-190,WorldPublishingCorporation,Lijiang,2008.JinG,ZhouX,WangH,ZhaoH,CuiK,ZhangXS,ChenL,HazenSL,LiK,WongSTTheKnowledge-IntegratedNetworkBiomarkersDiscoveryforMajorAdverseCardiacEvents.JProteomeRes7(9):4013-4021,2008,6,.,7,LuonanChen,Rui-ShengWang,Xiang-SunZhang.BiomolecularNetworks:MethodsandApplicationsinSystemsBiology.JohnWileyGuimera,Nature,2005).Resolutionlimit现象,.,19,极端例子：ringofcliques,Fortunato&Barthelemy,Proc.Natl.Acad.Sci.USA104(1),36-41(2007),.,20,提出新的模块化指标D值,模块化密度函数D:,ZhenpingLi,ShihuaZhang,Rui-ShengWang,Xiang-SunZhang,LuonanChen,Quantitativefunctionforcommunitydetection.PhysicalReviewE,77,036109,2008,.,21,D值克服了Q值存在的resolutionlimit问题,.,22,结果,Q值,D值,划分正确的顶点的比例,.,23,错分现象-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,23,.,24,该文的主要贡献是用离散凸规划的概念对两个重要问题进行解析分析,Q值和D值的最优化模型都是非线性整数规划目标函数的凸性和凹性无法解析得到对两个具有特殊结构的网络进行分析引入离散凸规划（变量是离散的，可以嵌入一个连续的凸规划）的概念进行分析,得到解析解,.,25,所有对modularity进行研究的论文(指上面所列的的PNAS,Nature,Sience文章)都是试题论证的,即没有解析的证明.为了彻底分析resolutionlimit和Misidentification现象，我们对两类典型网络建立了优化模型,引入了离散凸分析技术,得到了两类问题的解析解.,.,26,这两个例子出现在PNAS中几乎所有讨论网络模块探测的论文里,基于特殊结构的凸分析,adhocnetwork,ringofdenselumps,.,27,Finding1对,.,28,Finding2,.,29,Finding3,解析解表明，对这两个经典的算例，Q和D都有Resolutionlimit和Misidentification的现象产生，所以Q和D均只是近似的定量评估函数。网络社团划分的问题可以用一个优化问题来精确描述，我们证明了这一模型是NP-hard的。我们相信用优化理论可以彻底解决网络社团划分的问题。网络科学是运筹学的下一个热点。,.,30,直接得到团环网络的社团结构数值解,.,31,直接得到adhoc网络的社团结构数值解,.,32,.,33,为了彻底解决这些问题,提出一个新的OR模型和相应的算法，这一算法不会产生resolutionlimit和mis-identification现象关键思路：模块分划质量函数的定义要包含社团定义。,Xiang-SunZhang,ZhenpingLi,Rui-ShengWang,YongWang.AcombinatorialmodelandalgorithmforgloballysearchingcommunitystructureincomplexnetworksJournalofCombinatorialOptimization(JCO),2010.,DOI:10.1007/s10878-010-9356-0,.,34,AnewORmodel,Problemdefinition:Givenanetwork,thecommunityidentificationproblemistopartitionthenetworkintoasmanynon-overlappingsub-networksaspossiblesuchthateachsub-networksatisfiesagivencommunitydefinition.给定一个网络和一个社团的定义，社团结构识别的问题就是将整个网络分成尽可能多的满足社团定义的子网络。,34,.,35,以上文字定义可以用一个整数线性规划来描述,我们证明了这个模型是NP-hard.,35,.,36,Aqualifiedmin-cut(QMC)algorithm,Aheuristicprincipleisgiventofindafeasiblepartitionwiththelargestnumberofcommunities.Itisrealizedbyamin-cutoperation:Amin-cutoperationiscalledqualifiedifthetworesultingsub-networkssatisfythemoduledefinition.Thecommunityidentificationproblemcanbesolvedbasedonaseriesofqualifiedmin-cutoperations.,36,.,37,Experimentresults(artificialnetworks),Ringsofcliques,Unevenad-hocnetwork,37,.,38,Experimentresults(realnetworks),Footballteamnetwork,Jazzmusiciannetwork,38,.,39,学术性的，实用性的问题远远没有解决,Yong-YeolAhn,JamesP.Bagrow&SuneLehmann，Nature,2010Linkcommunitie