复杂网络的社团结构

复杂网络的社团结构章祥荪张世华(报告人)中国科学院数学与系统科学研究院生物信息学研究中心CenterofBioinformatics(COBI)主任章祥荪学术委员会主任王志新学科介绍随着人类基因组计划（HGP）等大型国际项目的实施与迅速发展,分子生物信息的研究已经成为了当前一个研究热点和前沿领域。一门新兴的边缘学科——生物信息学应运而生。它是以核酸、蛋白质等生物大分子数据为主要对象，以数学、生物学、信息科学为主要手段，以计算机硬件、软件和网络为主要工具，从浩如烟海的原始数据中获取基因编码、基因调控、核酸和蛋白质结构与功能等知识，从而探索生命起源、生物进化，以及细胞、器官和个体的发生、发育、衰亡等生命科学中的重大问题。它对进入后基因组时代的21世纪生命科学，具有不可估量的推动作用。NetworksasauniversallanguageDiseaseSpread[Krebs]ProteinInteractions[Barabasi]SocialNetworkFoodWebNeuralNetwork[Cajal]ElectronicCircuitInternet[Burch&Cheswick]Whattopics?:MethodsandApplicationsinSystemsBiology.JohnWiley&Sons,Hoboken,NewJersey.July,2009.Wefocusonbiomolecularnetworks.6复杂网络结构分析•复杂网络的动态性质研究•复杂网络的静态结构研究小世界(Smallworld)，尺度无关（Scalefree)，聚类特性(Clustering)的确切数学模型。社团结构(CommunityStructure)…………8ZhangS.,JinG.,X.S.Zhang,L.ChenProteomics,7(16),2856-69,2007.9生物分子网络的模块结构——复杂网络的模块化性质•复杂网络包括生物网络中存在模块或者社区结构(ModuleorCommunitystructure)(Girvan,M,Newman,M.,PNAS，2002；RivesandGalitski，2003)•模块或者社区定义为网络中内部连接稠密，与外部连接稀疏的节点的集合(FilippoRadicchiet.al.PNAS,101,2658-2663,2004).•数学表述:其中V是子图，K是顶点的度。即子图V是模块的条件是模块内顶点的内部连边的度值之和大于模块内顶点的外部连边的度值之和10社团(模块)结构识别的重要性•许多复杂网络共有的性质。•研究模块结构有助于研究整个网络的结构和功能圣塔菲研究所的科学家合作网：模块代表从事相似领域研究的科学家集合数学生态学统计物理社团(模块)结构识别的重要性Guimera,R,Amaral,L.,Nature,200512RosvallandBergstrom,PNAS,2007自然科学论文引用网络：6128期刊,约600万次引用，划分为88个模块和3024条模块间的连接，刻画了学科之间的联系社团(模块)结构识别的重要性•Girvan,M,Newman,M.,PNAS,2002•Ravasz,E,Somera,A,Mongru,D,etal.,Science,2002•Radicchi,F,Castellano,C,Cecconi,F.,PNAS,2004•Guimera,R,Mossa,S,Turtschi,A.,PNAS,2005•Guimera,R,Amaral,L.,Nature,2005•Pallaetal.,Nature,2005•Newman,M.,PNAS,2006•Rosvall,M,Bergstrom,C.,PNAS,2007•Fortunato,S,Barthelemy,M.,PNAS,2007•Weinan,E,Li,T,Vanden-Eijnden,E.,PNAS,2008•Rosvall,M,Bergstrom,C.,PNAS,2008•PeterJ.Mucha,etal.,Science,2010•Ahn,Y.Y,Bagrow,J.P.&Lehmann,S.,Nature,201013这一课题引起广泛关注！社团结构探索方法概论14SantoFortunato,PhysicsReports,2010.PPI网络的模块结构到复杂网络的社团结构(2005)•基于k-clique渗透理论overlappingcommunitystructure•可是当时三个物种的PPI网络中，Yeast相对比较稠密Fly非常稀疏，几乎没有什么cliquePallaetal.,Nature,200516Fuzzy/overlapping社团结构识别S.Zhang,R.S.Wang,andX.-SZhang.PhysicaA,2007.S.Zhang,R.S.Wang,andX.-SZhang.PhysicalReviewE,2007.基本想法：1.推广Modularity指标如Q，到Fuzzy划分的评价；2.考虑传统的Fuzzyclustering方法。算例——科学合作网络S.Zhang,X.M.Ning,andX.-SZhang.EPJB,2007.19衡量网络模块化的指标Q值•设网络为N=(V,E),Pk={(V1,E1),…,(Vk,Ek)}为一个分划。L(Vi,Vj)=|Eij|,iinVi,jinVj.•Newman和Girvan(PhysicalReviewE,2004)提出一种衡量网络社区结构的指标Q值:20指标Q的问题(Resolutionlimit)FortunatoandBarthélemy,PNAS,2007•利用Q划分网络的计算步骤:•目前很大一部分模块探测的方法集中于利用各种算法来极大化Q值，例如模拟退火、遗传算法、谱分解等(Newman,PNAS,2006;GuimeraandAmaral,Nature,2005).•Resolutionlimit现象kiinVkkkQQkii1||1maxmaxmax21极端例子：ringofcliquesFortunato&Barthelemy,PNAS,2007.22提出新的模块化指标D值•模块化密度函数D:•一个整数规划模型求解：Z.Li*,S.Zhang*,R.S.Wang,X.-S.Zhang,L.Chen.PhysicalReviewE,77,036109,200823D值克服了Q值存在的resolutionlimit问题25多尺度度量D指标在生物网络上的应用S.Zhang,X.M.Ning,C.DingandX.-SZhang.BMCSystemsBiology(2010)针对D指标的优化问题，设计了谱分解算法求解！生物复合物作为benchmark的比较进一步Prof.Zhang运用运筹学的方法分析了错分现象---Misidentification•用Q或D作优化可能得到不满足定义的模块Qpartitionsthenetworkintothreecommunities(twoKnandoneK5)whenn=16(respectively,n=21),inwhichK5isasub-graphviolatingallreasonablecommunitydefinition.X.S.Zhang,R.S.Wang,Y.Wang,J.G.Wang,Y.QQiu,L.Wang,andL.Chen.EurophysicsLetters(EPL),2009.被评为EPL2009bestpaper•解析解表明，对这两个经典的算例，的现象产生，所以Q和D均只Q和D都有Resolutionlimit和Misidentification是近似的定量评估函数。•网络社团划分的问题可以用一个优化问题来精确描述，我们证明了这一模型是NP-hard的。•我们相信用优化理论可以彻底解决网络社团划分的问题。网络科学是运筹学的下一个热点。3132为了解决这些问题•提出一个新的OR模型和相应的算法，这一算法不会产生resolutionlimit和mis-identification现象X.S.Zhang,Z.Li,R.S.Wang,Y.Wang.JournalofCombinatorialOptimization,2011.定义可以用一个整数线性规划来描述•我们证明了这个模型是NP-hard.困惑依旧社团结构识别问题为什么成为这么热闹的研究领域？单纯从算法的角度是否有进一步的必要？我们是否可能找到一个万能有效的方法/指标？出路在那里？进一步的问题/方向？社团结构的演化？比如：时序网络中社团结构的识别？。。。社团结构对其他属性的影响？比如：疾病/谣言/信息传播的影响？有向网络社团结构的定义、识别，是否可能？一个有向网络网络模体Science,298:799-804,2002致谢ThisworkiscooperatedwithDr.李珍萍，Dr.王瑞省，Dr.王勇，Dr.宁雪梅Dr.王吉光，Dr.张俊华等等Thisworkissupportedby国家自然科学重点基金10631070973项目2066CB503905国家自然科学基金项目608732053839欢迎访问ZHANGroup,