10
社团结构探索方法概述
A large number of methods have been developed for detecting communities, which can be generally categorized into local and global methods. •
数学生ห้องสมุดไป่ตู้学
圣塔菲研究所的科学家 合作网：模块代表从事 相似领域研究的科学家 集合
统计物理
8
Martin Rosvall, Carl T. Bergstrom, PNAS, vol. 105, no.4. 1118-1123, 2007
自然科学论文引用网络：6128 期刊, 约600万次引用， 划分为88个模块 和3024条 模块间的连接， 刻画了学科之间 的联系
其中V是子图，K是顶点的度。即子图 V 是模块的条件是模块内 顶点的内部连边的度值之和大于模块内顶点的外部连边的度值之 和。 PNAS ---- Proc. Natl. Acad. Sci. USA 美国科学院院刊
7
模块划分的重要性
• 许多复杂网络共有的性质。 • 研究模块结构有助于研究整个网络的结构和功能
4
Yeast functional linkage network
SCIENCE Vol 306(26) 2004
DNA damage module
可分成564 个模块，由 950 个显著的块间相互 作用相连接。
• 复杂网络的动态性质研究
• 复杂网络的静态结构研究
小世界(Small world) ，尺度无关（Scale free)，聚类特性 (Clustering) 的确切数学模型。
复杂网络的社团结构分析
Community structure in complex networks
1
Bio-molecular networks （生物分子网）
• 许多生物问题, 特别是人类的疾病, 在分子层面 上都可归于 “systems problems” -- Leroy Hood • 许多生物问题可以表达成生物分子网络（biomolecular networks）的问题。 • 生物分子网络包括：蛋白质相互作用网（ protein interaction networks）, 新陈代谢网（metabolic networks），基因调控网（ gene regulatory networks）, e.t.; 他们都有共同的性质 • 更为有趣的是，许多这样的网是“复杂”网络
2
复杂网络的典型代表:生物分子网络之一 ---- 蛋白 质相互作用网 （Scale-free)
酵母细胞中的蛋白质相互作用网络 (A.-L. Barabási, NATURE REVIEWS GENETICS, 2004)
3
Jeong, 2000, Nature
包括太古代（ Archae），细菌 （ Becterium), 真核生物（Eukaryote）在内 的43个物种的 新陈代谢网（ Metabolic network ）都是 Scale-free的。
11
我们小组在研究这一问题的早期发展了一些基于图论和
矩阵谱分解的模块探测算法 (local method)
Shihua Zhang, Rui-Sheng Wang, and Xiang-Sun Zhang. Identification of overlapping community structure in complex networks using fuzzy cmeans Clustering. Physica A, 2007, 374, 483–490.
• 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.
9
一个社会网络的例子
W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research 33, 452-473 1977
1970年美国大学里的一个空手道俱乐部关系网络：节点是 其34名成员，边是他们两年间的友谊关系，边数为78。俱 乐部里的矛盾导致其分裂为两个小的俱乐部。问题是能否 用网络的模块结构来重现这个过程？ 它是模块探测研究中的经典例子。
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.
社团结构 (Community Structure) …………
6
复杂网络的模块化性质
• 复杂网络中存在模块或者社区结构 (Module or Community structure) • 模块或者社区定义为网络中内部连接稠密，与外部连 接稀疏的节点的集合 (Filippo Radicchi et. al. PNAS, Vol.101, No.9, 2658-2663, 2004). • 数学表述: