复杂网络的社团结构分析（PPT讲稿）Community structure in complex networks（中国科学院：章祥荪）

复杂网络的社团结构分析 Community structure in complex networks 章祥荪 http://zhangroup.aporc.org 中国科学院数学与系统科学研究院 全国复杂网络会议,苏州大学,2010,10,17

1 章祥荪 复杂网络的社团结构分析 Community structure in complex networks http://zhangroup.aporc.org 中国科学院 数学与系统科学研究院 全国复杂网络会议，苏州大学，2010，10, 17

Bio-molecular networks(生物分子网) 许多生物问题,特别是人类的疾病,在分子层面 上都可归于“ "systems problems'”- Leroy hood 许多生物问题可以表达成生物分子网络(bio molecular networks)的问题。 生物分子网络包括:蛋白质相互作用网( protein interaction networks),新陈代谢网( metabolic networks),基因调控网( gene regulatory networks),et;他们都有共同的性质 更为有趣的是,许多这样的网是“复杂”网络

Bio-molecular networks （生物分子网）  许多生物问题, 特别是人类的疾病, 在分子层面 上都可归于 “systems problems” -- Leroy Hood  许多生物问题可以表达成生物分子网络（bio￾molecular networks）的问题。  生物分子网络包括：蛋白质相互作用网（ protein interaction networks）, 新陈代谢网（metabolic networks），基因调控网（ gene regulatory networks）, e.t.; 他们都有共同的性质  更为有趣的是，许多这样的网是“复杂”网络 2

复杂网络的典型代表生物分子网络之 蛋白 质相互作用网( Scale-free) 酵母细胞中的蛋白质相互作用网络(A.L. Barabasi, NATURE REVIEWS GENETICS, 2004)

3 复杂网络的典型代表:生物分子网络之一 ---- 蛋白 质相互作用网 （Scale-free) 酵母细胞中的蛋白质相互作用网络 (A.-L. Barabási, NATURE REVIEWS GENETICS, 2004)

Jeong, 2000, Nature 包括太古代( Archae),细菌( Bacterium), 真核生物( Eukaryote)在内的43个物种的新 陈代谢网( Metabolic network)都是 Scale reel 的

Jeong, 2000, Nature 包括太古代（Archae），细菌（ Becterium), 真核生物（Eukaryote）在内的43个物种的新 陈代谢网（ Metabolic network ）都是 Scale￾free的。 4

Protein-protein interaction networks Rui-Sheng Wang, Yong Wang, Ling-Yun Wu, Xiang-Sun Zhang, Luonan Chen Analysis on multi-domain cooperation for predicting protein-protein interaction: BMC Bioinformatics.8: 391.2007 Shihua Zhang, Xue-Mei Ning and Xiang-Sun Zhang Identification of functional modules in a PPI network by clique percolation clustering Computational biology and chemistry, 30(6),445-451, 2006 Luonan Chen, Ling-Yun Wu, Yong Wang and Xiang-Sun Zhang Inferring Protein Interactions from Experimental Data by Association Probabilistic Method Proteins: Structure, Function, and Bioinformatics, Vol. 62, Pp. 833-837, 2006 Xiang-Sun Zhang, Rui-Sheng Wang, Ling-Yun Wu, Shihua Zhang and Luonan Chen Inferring Protein-Protein Interactions by Combinatorial Models IFMBE Proceedings, Vol 14, 2006, 183-186, Springer Berlin Heidelberg

Protein-protein interaction networks  Rui-Sheng Wang, Yong Wang, Ling-Yun Wu, Xiang-Sun Zhang, Luonan Chen. Analysis on multi-domain cooperation for predicting protein-protein interactions. BMC Bioinformatics, 8:391, 2007  Shihua Zhang, Xue-Mei Ning and Xiang-Sun Zhang. Identification of functional modules in a PPI network by clique percolation clustering. Computational biology and chemistry, 30(6), 445-451, 2006.  Luonan Chen, Ling-Yun Wu, Yong Wang and Xiang-Sun Zhang. Inferring Protein Interactions from Experimental Data by Association Probabilistic Method. Proteins: Structure, Function, and Bioinformatics, Vol. 62, pp. 833-837, 2006.  Xiang-Sun Zhang, Rui-Sheng Wang, Ling-Yun Wu, Shihua Zhang and Luonan Chen. Inferring Protein-Protein Interactions by Combinatorial Models. IFMBE Proceedings, Vol.14, 2006, 183--186, Springer Berlin Heidelberg. 5

Metabolic and signaling networks Zhenping Li, Rui-Sheng Wang, Xiang-Sun Zhang and Luonan Chen Detecting drug targets with minimum side effects in metabolic networks IET SyStems Biology, 3(6), 523-533, 2009 Chenping Li, Rui-Sheng Wang, Xiang-Sun Zhang Mass Flow Model and Essentiality of Enzymes in Metabolic Networks Lecture Notes in Operations Research, 9, pp. 182-190, World Publishing Co orporation lIang 2008. Jin G, Zhou X, Wang H, Zhao H, Cui K, Zhang Xs, Chen L, Hazen SL, Li K, Wong St The Knowledge-Integrated Network Biomarkers Discovery for Major Adverse Cardiac events I Proteome Res7(9):4013-4021,2008

Metabolic and signaling networks  Zhenping Li, Rui-Sheng Wang, Xiang-Sun Zhang and Luonan Chen. Detecting drug targets with minimum side effects in metabolic networks. IET Systems Biology, 3(6), 523-533, 2009  Zhenping Li, Rui-Sheng Wang, Xiang-Sun Zhang. Mass Flow Model and Essentiality of Enzymes in Metabolic Networks. Lecture Notes in Operations Research, 9, pp. 182-190, World Publishing Corporation, Lijiang, 2008.  Jin G, Zhou X, Wang H, Zhao H, Cui K, Zhang XS, Chen L, Hazen SL, Li K, Wong ST The Knowledge-Integrated Network Biomarkers Discovery for Major Adverse Cardiac Events. J Proteome Res 7(9): 4013-4021,2008 6

Book about biomolecular networks BIOMOLECULAR NETWORKS n时如wg ILEY Luonan Chen, Rui-Sheng Wang, Xiang-Sun Zhang Biomolecular Networks: Methods and Applications in Systems Biology ohn Wiley& Sons, Hoboken, New Jersey. July, 2009

Luonan Chen, Rui-Sheng Wang, Xiang-Sun Zhang. Biomolecular Networks: Methods and Applications in Systems Biology. John Wiley & Sons, Hoboken, New Jersey. July, 2009. Book about Biomolecular networks 7

Yeast functional linkage network DNA repair synthesis poL 9-REV DNA dam (signal transduction 14DUN∠14583 SCIENCE Vol 306(26)2004 us 324-14-MEC314-ASE Clusters for Meiotic energy metabolism Clusters for DNA damage 9-HAD Mitochondrial -RFA3"DouDe- strand Nucleotide excision repair Ribosome Ribosome dna damage module 可分成564个模块,由 950个显著的块间相互 作用相连接 Clusters for cellular transport mRNA splicing Chromatin modeling

可分成564 个模块，由 950 个显著的块间相互 作用相连接。 Yeast functional linkage network DNA damage module SCIENCE Vol 306(26) 2004

°复杂网络的动态性质研究 复杂网络的静态结构研究 >小世界( Small world),尺度无关( Scale free),聚 类特性( Clustering)的确切数学模型。 >社团结构( Community Structure) ●。·●●··●●·

 复杂网络的动态性质研究  复杂网络的静态结构研究 ➢ 小世界(Small world) ，尺度无关（Scale free)，聚 类特性 (Clustering) 的确切数学模型。 ➢ 社团结构 (Community Structure) ➢ ………… 9

复杂网络的模块化性质 复杂网络中存在模块或者社区结构( Module or Community structure) 模块或者社区定义为网络中内部连接稠密,与外部连 接稀疏的节点的集合( Filippo Radicchi et. al. PNas, Vol.101,No.9,2658-2663,2004). 数学表述: ∑h(V)>∑ kout i∈V 其中v是子图,K是顶点的度。即孑子图v是模块的条件是模块内 顶点的内部连边的度值之和大于模块内顶点的外部连边的度值之 和。 PNAS-Proc. Natl. acad.Sci.USA美国科学院院刊

10 复杂网络的模块化性质  复杂网络中存在模块或者社区结构 (Module or Community structure)  模块或者社区定义为网络中内部连接稠密，与外部连 接稀疏的节点的集合 (Filippo Radicchi et. al. PNAS, Vol.101, No.9, 2658-2663, 2004).  数学表述: 其中V是子图，K是顶点的度。即子图V是模块的条件是模块内 顶点的内部连边的度值之和大于模块内顶点的外部连边的度值之 和。 PNAS ---- Proc. Natl. Acad. Sci. USA 美国科学院院刊