1章祥荪章祥荪复杂网络的社团结构分析复杂网络的社团结构分析Community structure in complex networks中国科学院中国科学院 数学与系统科学研究院数学与系统科学研究院全国复杂网络会议，苏州大学，全国复杂网络会议，苏州大学， 2010，10, 17Bio-molecular networks （生物分（生物分子网）子网） 许多生物问题许多生物问题, 特别是人类的疾病特别是人类的疾病, 在分子层面在分子层面上都可归于上都可归于 “systems problems” - Leroy Hood 许多生物问题可以表达成生物分子网络（许多生物问题可以表达成生物分子网络（bio-molecular networks）的问题。的问题。生物分子网络包括：蛋白质相互作用网（生物分子网络包括：蛋白质相互作用网（ protein interaction networks）, 新陈代谢网新陈代谢网（metabolic networks），），基因调控网基因调控网（ gene regulatory networks）, e.t.; 他们都有共同的他们都有共同的性质性质 更为有趣的是，许多这样的网是更为有趣的是，许多这样的网是“复杂复杂”网络网络23复杂网络的典型代表复杂网络的典型代表:生物分子网络之一生物分子网络之一 - - 蛋白蛋白质相互作用网质相互作用网 （Scale-free)Scale-free)酵母细胞中的蛋白质相互作用网络酵母细胞中的蛋白质相互作用网络 (A.-L. Barabsi, NATURE REVIEWS GENETICS, 2004)Jeong, 2000, Nature 包括太古代（包括太古代（ Archae），细菌（细菌（ Becterium), 真核生物（真核生物（Eukaryote）在内在内的的43个物种的个物种的新陈代谢网（新陈代谢网（ Metabolic network ）都是都是 Scale-free的。的。4Protein-protein interaction networksRui-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. 5Metabolic and signaling networksZhenping 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 6Luonan 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 networks7可分成可分成564 个模块，由个模块，由 950 个显著的块间相互个显著的块间相互作用相连接。作用相连接。 Yeast functional linkage networkDNA damage moduleSCIENCE Vol 306(26) 2004 复杂网络的动态性质研究复杂网络的动态性质研究 复杂网络的静态结构研究复杂网络的静态结构研究小世界小世界(Small world)(Small world) ，尺度无关尺度无关（Scale free)Scale free)，聚类特性聚类特性 (Clustering)(Clustering) 的确切数学模型的确切数学模型。 社团结构社团结构 (Community Structure) (Community Structure) 910复复杂网网络的模的模块化性化性质复杂网络中存在模块或者社区结构复杂网络中存在模块或者社区结构 (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 美国科学院院刊美国科学院院刊11模模块划分的重要性划分的重要性许多复杂网络共有的性质。许多复杂网络共有的性质。研究模块结构有助于研究整个网络的结构和功能研究模块结构有助于研究整个网络的结构和功能圣塔菲研究所的科学家圣塔菲研究所的科学家合作网：模块代表从事合作网：模块代表从事相似领域研究的科学家相似领域研究的科学家集合集合数学生态学统计物理12Martin Rosvall, Carl T. Bergstrom, PNAS, vol. 105, no.4. 1118-1123, 2007自然科学论文引用网络：自然科学论文引用网络：6128期刊期刊, 约约600万次引用万次引用，划分为划分为88个模块个模块和和3024条条模块间的连接，模块间的连接，刻画了学科之间刻画了学科之间的联系的联系13一个社会网络的例子一个社会网络的例子l19701970年美国大学里的一个空手道俱乐部关系网络：节点是年美国大学里的一个空手道俱乐部关系网络：节点是其其3434名成员，边是他们两年间的友谊关系，边数为名成员，边是他们两年间的友谊关系，边数为7878。俱。俱乐部里的矛盾导致其分裂为两个小的俱乐部。问题是能否乐部里的矛盾导致其分裂为两个小的俱乐部。问题是能否用网络的模块结构来重现这个过程？用网络的模块结构来重现这个过程？l它是模块探测研究中的经典例子。它是模块探测研究中的经典例子。W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452-473 1977Girvan, 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, 2008 Rosvall, M, Bergstrom, C., Proc. Natl. Acad. Sci, 2008 Peter J. Mucha, et al., Science 2010 Yong-Yeol Ahn, James P. Bagrow & Sune Lehmann，Nature, 2010生物信息学与最优化方法14Importance of the topic社社团结构探索方法概述构探索方法概述 A large number of methods have been developed for detecting communities, which can be generally categorized into local and global methods. Local methods （局部方法）（局部方法） for community detection identify a subset of nodes as a community according to certain local connection conditions, independently from the structure of the rest of the network. Such methods include clique overlap-based hierarchical clustering, clique percolation method, and sub-graph fitness method. Global methods （全局方法）（全局方法）for community detection optimize certain global quantitative functions encoding the quality of the overall partition of the network, such as information theoretical method, Potts model, and optimization of modularity measures. 1516Shihua Zhang, Rui-Sheng Wang, and Xiang-Sun Zhang. Identification of overlapping community structure in complex networks using fuzzy c-means Clustering. Physica A, 2007, 374, 483490. Rui-Sheng Wang, Shihua Zhang, Yong Wang, Xiang-Sun Zhang, Luonan Chen. Clustering complex networks and biological networks by nonnegative matrix factorization with various similarity measures. Neurocomputing, 2007Shihua Zhang, Rui-Sheng Wang and Xiang-Sun Zhang. Uncovering fuzzy community structure in complex networks. Physical Review E, 76, 046103, 2007l我们小组在研究这一问题的早期发展了一些基于图论和我们小组在研究这一问题的早期发展了一些基于图论和矩阵谱分解的模块探测算法矩阵谱分解的模块探测算法 (local method)17衡量网衡量网络模模块化的指化的指标Q值 设网络为设网络为 N=（V，E）, Pk = (V1, E1), , (Vk, Ek) 为为一个分划。一个分划。L(Vi, Vj) =|Eij|, i in Vi, j in Vj.Newman 和和 Girvan (Physical Review E, 2004) 提出一提出一种衡量网络社区结构的指标种衡量网络社区结构的指标 Q 值值 18指指标Q的的问题 (Resolution limit)Fortunato and Barthlemy, PNAS, 2007利用利用Q 划分网络的计算步骤划分网络的计算步骤: 目前很大一部分模块探测的方法集中于利用各种启目前很大一部分模块探测的方法集中于利用各种启发式算法来极大化发式算法来极大化Q值值 ，例如模拟退火、遗传算法，例如模拟退火、遗传算法等等(Newman, PNAS, 2006; Guimera, Nature, 2005). Resolution limit 现象现象19极端例子：极端例子：ring of cliquesFortunato & Barthelemy, Proc. Natl. Acad. Sci. USA 104 (1), 36-41 (2007)20提出新的模提出新的模块化指化指标D值模块化密度函数模块化密度函数 D:Zhenping Li, Shihua Zhang, Rui-Sheng Wang, Xiang-Sun Zhang, Luonan Chen, Quantitative function for community detection. Physical Review E, 77, 036109, 200821D值克服了值克服了Q值存在的值存在的 resolution limit 问题问题22结果果Q值D值划分正确的顶点的比例错分分现象象-Misidentification用Q或D作优化可能得到不满足定义的模块Q partitions the network into three communities (two Kn and one K5) when n=16 (respectively, n=21), in which K5 is a sub-graph violating all reasonable community definition.Xiang-Sun Zhang, Rui-Sheng Wang, Yong Wang, Ji-Guang Wang, Yu-Qing Qiu, Lin Wang, and Luonan Chen. Modularity optimization in community detection of complex networks. Europhysics Letters (EPL), 87, 2009. 被评为被评为 EPL 2009 best paper2324该文的主要文的主要贡献是用离散凸献是用离散凸规划的划的概念概念对两个重要两个重要问题进行解析分析行解析分析Q 值和值和D 值的最优化模型都是非线性整数规划值的最优化模型都是非线性整数规划目标函数的凸性和凹性无法解析得到目标函数的凸性和凹性无法解析得到对两个具有特殊结构的网络进行分析对两个具有特殊结构的网络进行分析引入离散凸规划（变量是离散的，可以嵌入一个连续的引入离散凸规划（变量是离散的，可以嵌入一个连续的凸规划）的概念进行分析凸规划）的概念进行分析, 得到解析解得到解析解所有对所有对modularity进行研究的论文进行研究的论文( (指上面所列的指上面所列的的的PNAS,Nature,Sience文章文章) )都是试题论证的都是试题论证的, ,即即没有解析的证明没有解析的证明. .为了彻底分析为了彻底分析resolution limitresolution limit和和 MisidentificationMisidentification 现象，我们对两类典型网络建现象，我们对两类典型网络建立了优化模型立了优化模型, ,引入了离散凸分析技术引入了离散凸分析技术, ,得到了两类得到了两类问题的解析解问题的解析解. . 生物信息学与最优化方法25这两个例子出现在这两个例子出现在PNAS中几乎所有讨论网络模块中几乎所有讨论网络模块探测的论文里探测的论文里基于特殊基于特殊结构的凸分析构的凸分析ad hoc networkring of dense lumps Finding 1 对生物信息学与最优化方法28Finding 2Finding 3解析解表明，对这两个经典的算例，解析解表明，对这两个经典的算例，Q和和D都有都有Resolution limit和和Misidentification的现象产生，的现象产生，所以所以Q 和和D均只是近似的定量评估函数。均只是近似的定量评估函数。 网络社团划分的问题可以用一个优化问题来精确网络社团划分的问题可以用一个优化问题来精确 描述，我们证明了这一模型是描述，我们证明了这一模型是NP-hard的。的。 我们相信用优化理论可以彻底解决网络社团划分我们相信用优化理论可以彻底解决网络社团划分 的问题。的问题。网络科学是运筹学的下一个热点。网络科学是运筹学的下一个热点。29直接得到直接得到团环网网络的社的社团结构数构数值解解30直接得到直接得到ad hoc网网络的社的社团结构数构数值解解313233为了了彻底解决底解决这些些问题 提出一个新的提出一个新的 OR 模型和相应的算法，这一算法不会产生模型和相应的算法，这一算法不会产生resolution limit 和和 mis-identification 现象现象关键思路：模块分划质量函数的定义要包含社团定义。关键思路：模块分划质量函数的定义要包含社团定义。Xiang-Sun Zhang, Zhenping Li, Rui-Sheng Wang, Yong Wang. A combinatorial model and algorithm for globally searching community structure in complex networksJournal of Combinatorial Optimization (JCO), 2010. A new OR model Problem definition: Given a network, the community identification problem is to partition the network into as many non-overlapping sub-networks as possible such that each sub-network satisfies a given community definition. 给定一个网络和一个社团的定义，社团结构识别给定一个网络和一个社团的定义，社团结构识别的问题就是将整个网络分成尽可能多的满足社团定的问题就是将整个网络分成尽可能多的满足社团定义的子网络。义的子网络。34以上文字定以上文字定义可以用一个整数可以用一个整数线性性规划来描述划来描述我们证明了这个模型是我们证明了这个模型是 NP-hard .35A qualified min-cut (QMC) algorithmA heuristic principle is given to find a feasible partition with the largest number of communities.It is realized by a min-cut operation: A min-cut operation is called qualified if the two resulting sub-networks satisfy the module definition. The community identification problem can be solved based on a series of qualified min-cut operations.36Experiment results (artificial networks)Rings of cliquesUneven ad-hoc network37Experiment results (real networks)Football team networkJazz musician network38学学术性的，性的，实用性的用性的问题远远没有解决没有解决Yong-Yeol Ahn, James P. Bagrow & Sune Lehmann，Nature, 2010 Link communities reveal multiscale complexity in networks39致致谢This work is cooperated with Dr. 李珍萍，李珍萍，Dr. 王瑞省，王瑞省，Dr. 王勇，王勇，Dr. 张世华，张世华， Dr. 王吉光，王吉光，Dr. 张俊华张俊华This work is supported by 国家自然科学重点基金国家自然科学重点基金10631070 973项目项目2066CB503905 国家自然科学基金项目国家自然科学基金项目60873205 40 ThanksWelcome to visit us at