社团结构分析PPT课件.ppt

1 章祥荪 复杂网络的社团结构分析Communitystructureincomplexnetworks http zhangroup aporc org中国科学院数学与系统科学研究院全国复杂网络会议 苏州大学 2010 10 17 2020 4 9 Bio molecularnetworks 生物分子网 许多生物问题 特别是人类的疾病 在分子层面上都可归于 systemsproblems LeroyHood许多生物问题可以表达成生物分子网络 bio molecularnetworks 的问题 生物分子网络包括 蛋白质相互作用网 proteininteractionnetworks 新陈代谢网 metabolicnetworks 基因调控网 generegulatorynetworks e t 他们都有共同的性质更为有趣的是 许多这样的网是 复杂 网络 2 2020 4 9 3 复杂网络的典型代表 生物分子网络之一 蛋白质相互作用网 Scale free 酵母细胞中的蛋白质相互作用网络 A L Barab si NATUREREVIEWSGENETICS 2004 2020 4 9 Jeong 2000 Nature 包括太古代 Archae 细菌 Becterium 真核生物 Eukaryote 在内的43个物种的新陈代谢网 Metabolicnetwork 都是Scale free的 4 2020 4 9 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 2020 4 9 5 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 2020 4 9 6 LuonanChen Rui ShengWang Xiang SunZhang BiomolecularNetworks MethodsandApplicationsinSystemsBiology JohnWiley Sons Hoboken NewJersey July 2009 BookaboutBiomolecularnetworks 7 2020 4 9 7 可分成564个模块 由950个显著的块间相互作用相连接 Yeastfunctionallinkagenetwork DNAdamagemodule SCIENCEVol306 26 2004 2020 4 9 8 复杂网络的动态性质研究复杂网络的静态结构研究小世界 Smallworld 尺度无关 Scalefree 聚类特性 Clustering 的确切数学模型 社团结构 CommunityStructure 9 2020 4 9 10 复杂网络的模块化性质 复杂网络中存在模块或者社区结构 ModuleorCommunitystructure 模块或者社区定义为网络中内部连接稠密 与外部连接稀疏的节点的集合 FilippoRadicchiet al PNAS Vol 101 No 9 2658 2663 2004 数学表述 其中V是子图 K是顶点的度 即子图V是模块的条件是模块内顶点的内部连边的度值之和大于模块内顶点的外部连边的度值之和 PNAS Proc Natl Acad Sci USA美国科学院院刊 2020 4 9 11 模块划分的重要性 许多复杂网络共有的性质 研究模块结构有助于研究整个网络的结构和功能 圣塔菲研究所的科学家合作网 模块代表从事相似领域研究的科学家集合 数学生态学 统计物理 2020 4 9 12 MartinRosvall CarlT Bergstrom PNAS vol 105 no 4 1118 1123 2007 自然科学论文引用网络 6128期刊 约600万次引用 划分为88个模块和3024条模块间的连接 刻画了学科之间的联系 2020 4 9 13 一个社会网络的例子 1970年美国大学里的一个空手道俱乐部关系网络 节点是其34名成员 边是他们两年间的友谊关系 边数为78 俱乐部里的矛盾导致其分裂为两个小的俱乐部 问题是能否用网络的模块结构来重现这个过程 它是模块探测研究中的经典例子 W W Zachary Aninformationflowmodelforconflictandfissioninsmallgroups JournalofAnthropologicalResearch33 452 4731977 2020 4 9 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 Bagrow SuneLehmann Nature 2010 14 Importanceofthetopic 2020 4 9 社团结构探索方法概述 Alargenumberofmethodshavebeendevelopedfordetectingcommunities whichcanbegenerallycategorizedintolocalandglobalmethods Localmethods 局部方法 forcommunitydetectionidentifyasubsetofnodesasacommunityaccordingtocertainlocalconnectionconditions independentlyfromthestructureoftherestofthenetwork Suchmethodsincludecliqueoverlap basedhierarchicalclustering cliquepercolationmethod andsub graphfitnessmethod Globalmethods 全局方法 forcommunitydetectionoptimizecertainglobalquantitativefunctionsencodingthequalityoftheoverallpartitionofthenetwork suchasinformationtheoreticalmethod Pottsmodel andoptimizationofmodularitymeasures 15 2020 4 9 16 ShihuaZhang Rui ShengWang andXiang SunZhang Identificationofoverlappingcommunitystructureincomplexnetworksusingfuzzyc meansClustering PhysicaA 2007 374 483 490 Rui ShengWang ShihuaZhang YongWang Xiang SunZhang LuonanChen Clusteringcomplexnetworksandbiologicalnetworksbynonnegativematrixfactorizationwithvarioussimilaritymeasures Neurocomputing 2007 ShihuaZhang Rui ShengWangandXiang SunZhang Uncoveringfuzzycommunitystructureincomplexnetworks PhysicalReviewE 76 046103 2007 我们小组在研究这一问题的早期发展了一些基于图论和矩阵谱分解的模块探测算法 localmethod 2020 4 9 17 衡量网络模块化的指标Q值 设网络为N V E Pk V1 E1 Vk Ek 为一个分划 L Vi Vj Eij iinVi jinVj Newman和Girvan PhysicalReviewE 2004 提出一种衡量网络社区结构的指标Q值 2020 4 9 18 指标Q的问题 Resolutionlimit FortunatoandBarth lemy PNAS 2007 利用Q划分网络的计算步骤 目前很大一部分模块探测的方法集中于利用各种启发式算法来极大化Q值 例如模拟退火 遗传算法等 Newman PNAS 2006 Guimera Nature 2005 Resolutionlimit现象 2020 4 9 19 极端例子 ringofcliques Fortunato Barthelemy Proc Natl Acad Sci USA104 1 36 41 2007 2020 4 9 20 提出新的模块化指标D值 模块化密度函数D ZhenpingLi ShihuaZhang Rui ShengWang Xiang SunZhang LuonanChen Quantitativefunctionforcommunitydetection PhysicalReviewE 77 036109 2008 2020 4 9 21 D值克服了Q值存在的resolutionlimit问题 2020 4 9 22 结果 Q值 D值 划分正确的顶点的比例 2020 4 9 错分现象 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 2020 4 9 23 24 该文的主要贡献是用离散凸规划的概念对两个重要问题进行解析分析 Q值和D值的最优化模型都是非线性整数规划目标函数的凸性和凹性无法解析得到对两个具有特殊结构的网络进行分析引入离散凸规划 变量是离散的 可以嵌入一个连续的凸规划 的概念进行分析 得到解析解 2020 4 9 所有对modularity进行研究的论文 指上面所列的的PNAS Nature Sience文章 都是试题论证的 即没有解析的证明 为了彻底分析resolutionlimit和Misidentification现象 我们对两类典型网络建立了优化模型 引入了离散凸分析技术 得到了两类问题的解析解 25 2020 4 9 这两个例子出现在PNAS中几乎所有讨论网络模块探测的论文里 基于特殊结构的凸分析 adhocnetwork ringofdenselumps 2020 4 9 26 Finding1对 2020 4 9 27 28 Finding2 2020 4 9 Finding3 解析解表明 对这两个经典的算例 Q和D都有Resolutionlimit和Misidentification的现象产生 所以Q和D均只是近似的定量评估函数 网络社团划分的问题可以用一个优化问题来精确描述 我们证明了这一模型是NP hard的 我们相信用优化理论可以彻底解决网络社团划分的问题 网络科学是运筹学的下一个热点 29 2020 4 9 直接得到团环网络的社团结构数值解 30 2020 4 9 直接得到adhoc网络的社团结构数值解 31 2020 4 9 32 2020 4 9 33 为了彻底解决这些问题 提出一个新的OR模型和相应的算法 这一算法不会产生resolutionlimit和mis identification现象关键思路 模块分划质量函数的定义要包含社团定义 Xiang SunZhang ZhenpingLi Rui ShengWang YongWang AcombinatorialmodelandalgorithmforgloballysearchingcommunitystructureincomplexnetworksJournalofCombinatorialOptimization JCO 2010 DOI 10 1007 s10878 010 9356 0 2020 4 9 AnewORmodel Problemdefinition Givenanetwork thecommunityidentificationproblemistopartitionthenetworkintoasmanynon overlappingsub networksaspossiblesuchthateachsub networksatisfiesagivencommunitydefinition 给定一个网络和一个社团的定义 社团结构识别的问题就是将整个网络分成尽可能多的满足社团定义的子网络 34 2020 4 9 34 以上文字定义可以用一个整数线性规划来描述 我们证明了这个模型是NP hard 35 2020 4 9 35 Aqualifiedmin cut QMC algorithm Aheuristicprincipleisgive