生物医学网络科学Biomedical Network Science
Network FoundationsCommunity structure and detection

社团结构与社区发现

研究网络中内部紧密、彼此稀疏的节点群：模块度与随机块模型、主要算法、可检测性、结果评价与生物学验证。

知识页面
19 页
阅读
约 53 分钟
讲解视频
1 段
代码示例
15 个
社团结构弱关系模块度边介数Girvan–Newman 算法Louvain 算法Leiden 算法谱聚类分辨率极限随机块模型度修正随机块模型Infomap映射方程可检测性阈值

网络结构指标与随机图和小世界与无标度网络模型研究的是网络的全局性质（度分布、平均路径）和局部性质（聚集系数）。介于两者之间还有一个尺度：网络常常由若干“内部连接紧密、彼此连接稀疏”的节点群组成，称为社团（community）或模块（module）。在蛋白质网络中，它们可能对应蛋白复合物和信号通路；在代谢网络中，对应相对独立的代谢子系统；在脑网络中，对应视觉、运动、默认模式等功能系统；在疾病网络中，对应疾病模块。

社团发现（community detection）看似只是“把节点分组”，但它同时牵涉三个不同层次的问题：什么算一个社团（定义与基本假设）、怎样找到它（质量函数与优化算法，或生成模型与统计推断），以及找到的东西可信吗（显著性、稳定性、可检测性与外部验证）。本专题按这个顺序组织：

  1. 从社会学的弱关系理论出发，理解社团为何存在，再给出社团的基本假设与形式化定义，说明可能的划分数目为何天文数字般巨大；
  2. 以模块度为中心介绍描述性方法：Girvan–Newman 删边法、Louvain 与 Leiden 算法、谱方法与层次聚类；
  3. 介绍两类“换一个视角”的方法：把社团看作生成模型参数的随机块模型与统计推断，以及把社团看作随机游走描述压缩的映射方程与 Infomap；
  4. 讨论社团发现的理论极限——可检测性阈值；
  5. 放宽“每个节点只属于一个社团、网络不随时间变化”的假设：重叠社团、多分辨率与共识聚类、多层与时变网络的社团；
  6. 最后是方法选择与结果评价：方法比较、划分比较与基准检验、社团结果的验证与解读。

各知识页面中的算法都在代码示例中有可运行的实现。

Contents知识页面

01弱关系理论与社团的定义Granovetter 的弱关系理论 1973 年，社会学家 Mark Granovetter 研究人们如何找到工作，发现一个反直觉的现象：帮人找到工作的，多是熟人（weak ti…02社团的基本假设与形式化定义Barabási《Network Science》第 9 章用四条“假设”串起社团发现的逻辑。它们不是定理，而是各类方法赖以成立的前提，理解它们有助于看清每种方法“默认了什么”。 …03模块度思路：与随机期望比较 一个好的划分，社团内部的边应当“多于随机情况下的预期”。问题是：随机预期应该怎么算？如果只按边数平均分配，枢纽节点因为连接多，会被误认为与谁都“紧密”。New…04Girvan–Newman 算法与边介数边介数 社团之间的连边少，所以社团之间的最短路径必须挤过这些少数“桥”。这启发了边介数（edge betweenness）的定义： 边介数：网络中所有节点对之间的最短路径中，经过某…05Louvain 与 Leiden 算法Louvain 算法 Louvain 算法（Blondel 等，2008）是目前最常用的社团发现算法之一，它反复执行两个阶段： 1. 局部移动：开始时每个节点自成一个社团。依次考察…06谱方法与层次聚类模块度谱方法 把模块度写成矩阵形式。定义模块度矩阵 。若把网络一分为二，用 表示节点 属于哪一侧，则 在 只能取 的约束下精确最大化很困难；放松为实数后，最优解就是 的最大特征值对…07随机块模型与统计推断从“找划分”到“拟合模型” 模块度最大化问的是“哪个划分使某个分数最高”；随机块模型（stochastic block model, SBM）问的是“什么样的分组最可能生成了观测到…08映射方程与 Infomap社团是“流”停留的地方 模块度和 SBM 都从连边的分布出发定义社团。Rosvall 与 Bergstrom（2008）换了一个角度：许多网络承载着“流”——信号在通路中传递、信息…09可检测性阈值问题：结构存在，但能找到吗 H3 说随机网络没有社团。反过来问：如果网络确实由含社团的模型生成，但社团之间的差别很弱，算法能不能把它找出来？答案是：存在一个相变式的阈值，低于它时，…10重叠社团上面的方法都把每个节点只分到一个社团。但一个人可以同时属于家庭、同事、球友几个圈子；一个蛋白也可以同时参与多个复合物；一个脑区可以参与多个功能系统。 团渗流（CFinder） 团渗…11多分辨率与共识聚类为什么需要多分辨率 真实网络的社团结构往往是多尺度的：蛋白复合物嵌在通路中，通路又嵌在更大的功能系统中；脑网络中的子系统组合成更大的系统。一个固定的 （或 CPM 的密度阈值、马尔…12多层与时变网络的社团多层模块度 当同一组节点之间有多种关系（多组学网络、多频段脑网络），或网络随时间变化（逐个时间窗估计的功能连接），可以把它们组织为多层网络：每层是一个网络，同一节点在不同层的副本之…13社团发现方法的比较方法 核心思想 速度 需要预设社团数？ 适用情形 --- --- --- --- --- Girvan–Newman 反复删除边介数最大的边 慢， 否（按 选层） 小网络、概念演示…14划分比较与基准检验怎样比较两个划分 评价算法、检查稳定性、与已知分组对照，都需要量化两个划分 、 的相似程度。设 个节点， 为同时属于 中社团 与 中社团 的节点数（列联表）， 、 为边际和。 - …15社团结果的验证与解读找到社团只是第一步，更重要的是判断它是否可靠、有什么含义。 1. 显著性：把实际网络的 与大量保度随机网络上得到的 比较。若随机网络的 也差不多，说明“社团”可能只是随机涨落。推断…16数学推导与算法本节把模块度、Louvain 与 Leiden 算法、谱方法、随机块模型、映射方程、可检测性和团渗流中只陈述的结果完整推一遍。记号： 为无向无权网络的邻接矩阵（加权网络把 换成边权…17研究前沿与开放问题1. 社团发现有没有“正确答案”？ 用节点元数据（如 GO 注释、已知复合物）当作“金标准”来评价算法，隐含了“元数据 = 网络结构真实分组”的假设。Peel、Larremore …18生物医学应用蛋白复合物与功能模块。 Hartwell、Hopfield、Leibler 与 Murray（1999，Nature）提出“功能模块”是细胞生物学的基本组织单位：一组相互作用的分子…19适用范围与常见误用1. 误区：模块度越高，社团结构就越“真实”。→ 正解：随机网络也能得到不低的 ，且 存在分辨率极限和简并性。应把 与保度随机网络的结果比较，并检查划分的稳定性和生物学意义。 2.…

VIDEO讲解视频

内密外疏：网络中的社团与模块度4 分 3 秒
文字稿

大家好，这一期我们来认识网络中的社团结构。比如蛋白质网络里的复合物，大脑里的功能系统，都是这样的结构。前面的指标看的是整体和局部，这一期看介于两者之间的中间尺度。

第一个问题，网络为什么会分成一个个内部紧密的小团体？第二个问题，给定一种划分，我们怎样定量地说它好还是不好？第三个问题，面对一个大网络，有哪些算法能把社团自动找出来？

社会学家 Granovetter 发现，帮人找到工作的，多半是熟人而不是密友。原因在于，密友之间往往彼此认识，形成三角形，信息高度重叠。而弱关系常常是连接不同圈子的桥，手机通话数据也证实了这一点。

怎样衡量一个划分的好坏？Newman 和 Girvan 提出了模块度。思路是把实际情况和随机情况做比较。前一项是实际落在社团内部的边占全部边的比例。后一项是在保持每个节点度不变、随机连边时，预期落在社团内部的比例。实际比随机多得越多，模块度就越高，说明划分越好。把整个网络当成一个社团时，模块度正好等于0。举个例子，两个三角形用一条边相连，按三角形划分，模块度约为0.36。

现在来看第一种算法，Girvan 和 Newman 的删边法。社团之间的边很少，所以社团之间的最短路径都要挤过这几座桥。我们统计每条边被多少条最短路径经过，这叫边介数。每次删掉边介数最大的边，然后重新计算，再删，网络就逐渐裂开。整个过程会形成一棵树状图，越往下切，社团就越多越小。大家注意右上角的模块度，它先升后降，我们取最高的那一层。在空手道俱乐部上，第一次分裂就几乎复现了俱乐部真实的分裂。

删边法要反复计算边介数，太慢，大网络上常用的是 Louvain 算法。改进的 Leiden 算法保证每个社团内部连通，是目前推荐的默认选择。谱方法则用模块度矩阵最大特征值的特征向量，按正负号把节点一分为二。层次聚类先定义节点相似度，再逐步合并，基因共表达分析常用它。

第一，随机网络做模块度最大化，也可能得到0.3以上的值，必须和随机网络比较。第二，模块度有分辨率极限，网络很大时，小而紧密的社团会被合并。第三，算法有随机性，要固定种子，并检查多次运行的结果是否稳定。

在蛋白质网络中，社团常常对应蛋白复合物或信号通路，可以用来预测未知蛋白的功能。在脑功能网络中，社团对应视觉、运动、默认模式等功能系统。在网络医学中，同一种疾病的相关基因往往聚集在一个局部区域。

小结一下，社团是内部连接紧密、对外连接稀疏的节点群。模块度用实际的社团内边比例减去随机期望来衡量划分的好坏。常用算法有删边法、Louvain 和 Leiden，以及谱方法和层次聚类。找到社团之后，还要检验它是否显著、是否稳定、是否有生物学意义。

请打开模块度演示，自己点击节点改变分组，看看模块度怎么变。然后在代码示例中亲手算一次模块度，再跑一跑这几种算法。也欢迎大家把自己研究中的网络拿来，试一试社团发现。下一期，我们进入网络上的传播动力学。

INTERACTIVE交互可视化

CODE计算实现

15 个完整可运行的 Python 示例，每个都给出代码、输出图和解读；可在浏览器中直接运行，或下载 Jupyter Notebook · Python 脚本。

按定义计算模块度Girvan–Newman 算法Louvain、分辨率参数与随机网络的模块度谱方法——模块度矩阵的主特征向量划分空间有多大——Bell 数与小网络上的穷举最优模块度划分之间的比较——NMI、ARI 与信息变差（VI）随机块模型与可检测性阈值标准 SBM 与度修正 SBM（DC-SBM）在空手道网络上的最大似然划分Infomap 的目标函数——两层映射方程（map equation）Leiden 算法、连通性检查与常数 Potts 模型（CPM）多分辨率扫描与共识聚类LFR 基准网络上的算法比较节点在社团中的角色——模块内度 z 分数与参与系数 P重叠社团——团渗流（CFinder）与连边聚类（link communities）时变网络的多层模块度与节点灵活性

Papers论文精读

经典分子网络与基因调控网络基础理论Statistical Applications in Genetics and Molecular Biology · 2005

加权基因共表达网络分析的一般框架

A general framework for weighted gene co-expression network analysis
Zhang B, Horvath S

提出用“软阈值”把基因间相关转为连续连接权重，构建加权共表达网络，并把连接度、拓扑重叠、聚集系数推广到加权情形。

相关专题：基因调控网络推断与共表达分析 生物分子网络与拓扑特征 社团结构与社区发现
经典网络基础理论▶ 视频PNAS · 2006

网络中的模块度与社团结构

Modularity and community structure in networks
Newman MEJ

把模块度写成模块度矩阵的二次型，按其主特征向量的正负号二分网络，得到快速而高质量的社团发现算法。

相关专题：社团结构与社区发现
经典网络基础理论Journal of Statistical Mechanics · 2008

大规模网络中社团的快速展开

Fast unfolding of communities in large networks
Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E

提出“局部移动 + 聚合”反复迭代的模块度优化算法（Louvain），在上亿节点的网络上几小时内完成社团发现。

相关专题：社团结构与社区发现

References核心文献

Girvan & Newman 2002：Community structure in social and biological networks

  • 出处：PNAS 99: 7821–7826。DOI：10.1073/pnas.122653799。论文精读：Girvan 2002
  • 背景：传统的层次聚类从“最相似的节点”开始合并，容易把边缘节点孤立出来；作者转而从“最不像社团内部的边”入手。
  • 核心发现：提出基于边介数的分裂式算法，在计算机生成的有社团网络上验证了效果；在空手道俱乐部网络上基本复现了真实的分裂；在科学家合作网络和海洋食物网中找到了有意义的社团。
  • 阅读提示：本文尚未提出模块度（模块度在 Newman 与 Girvan 2004 年的论文中正式提出，Phys. Rev. E 69: 026113，DOI），注意作者当时如何判断“分到第几层”。对照阅读 2004 年的论文，理解模块度为何成为后来的标准。
  • 思考题：边介数的计算依赖最短路径。如果网络是加权的（例如脑功能网络），应该怎样定义边介数？

Blondel, Guillaume, Lambiotte & Lefebvre 2008：Fast unfolding of communities in large networks

  • 出处：Journal of Statistical Mechanics P10008。DOI：10.1088/1742-5468/2008/10/P10008。论文精读：Blondel 2008
  • 背景：模块度最大化是 NP 难问题，已有的贪心算法在百万节点规模上太慢。
  • 核心发现：提出“局部移动 + 聚合”的两阶段算法（即 Louvain 算法），在数百万节点的网络上几分钟内得到高模块度划分，并自然产生多层次结构。
  • 阅读提示：注意作者对“中间层次划分也有意义”的讨论，这与分辨率极限有关；之后阅读下面的 Traag 等 2019，理解 Louvain 可能产生内部不连通社团的原因。
  • 思考题：Louvain 算法中节点的访问顺序会影响结果。在你自己的研究中，你会怎样设计分析来报告这种不确定性？

Traag, Waltman & van Eck 2019：From Louvain to Leiden: guaranteeing well-connected communities

  • 出处：Scientific Reports 9: 5233。DOI：10.1038/s41598-019-41695-z
  • 背景：Louvain 被广泛使用，但它得到的社团是否满足“社团应当连通”这一最基本的要求，此前很少被检查。
  • 核心发现：证明 Louvain 可能产生任意差的连接甚至不连通的社团，并在实验中观察到较高比例的连接不良社团；提出 Leiden 算法，通过细化阶段保证社团连通，迭代收敛后所有社团的所有子集都处于局部最优，且速度更快。
  • 阅读提示：重点理解细化阶段为何能让“已经聚合的社团”在下一层被拆开；文中对模块度与 CPM 两种质量函数都做了实验。
  • 思考题：如果一个算法保证社团连通，是否就意味着它找到的社团更“真实”？连通性与分辨率极限是两个独立的问题吗？

Fortunato & Barthélemy 2007：Resolution limit in community detection

  • 出处：PNAS 104: 36–41。DOI：10.1073/pnas.0605965104
  • 背景：模块度最大化被广泛使用，但它能识别多小的社团，一直没有系统分析。
  • 核心发现：证明模块度存在一个与网络总边数相关的固有尺度，小于这一尺度的社团可能无法被识别，即使它们是完全连接的团；用“团组成的环”等例子说明了这一问题。
  • 阅读提示：理解“团环”例子的构造和计算，这是理解分辨率极限最直接的途径。
  • 思考题：一个包含 2 万个蛋白、30 万条相互作用的网络中，一个由 5 个蛋白组成的复合物有可能被模块度最大化单独识别出来吗？你会如何验证？

Karrer & Newman 2011：Stochastic blockmodels and community structure in networks

  • 出处：Physical Review E 83: 016107。DOI：10.1103/PhysRevE.83.016107
  • 背景：标准随机块模型假设同组节点度相同，用于度异质的真实网络时会按度而不是按社团分组。
  • 核心发现：提出度修正随机块模型，给出只依赖划分的轮廓似然 ∑rsmrsln⁡[mrs/(κrκs)]\sum_{rs}m_{rs}\ln[m_{rs}/(\kappa_r\kappa_s)]；在空手道俱乐部与政治博客网络上，度修正模型恢复了真实分组，而标准模型没有。
  • 阅读提示：对照本专题推导 F，自己从泊松似然推出两种目标函数。
  • 思考题：DC-SBM 的最大似然仍需预先给定组数。你会如何决定一个 PPI 网络应分成多少组？

Rosvall & Bergstrom 2008：Maps of random walks on complex networks reveal community structure

  • 出处：PNAS 105: 1118–1123。DOI：10.1073/pnas.0706851105
  • 背景：模块度只看连边密度，对于以“流动”为意义的有向、加权网络（如引文网络）未必合适。
  • 核心发现：把社团发现表述为随机游走轨迹的最优压缩问题，提出映射方程及其优化算法（Infomap）；在大型期刊引文网络上得到了与学科划分相符的“科学地图”。
  • 阅读提示：先在纸上为一个小网络的两种划分各设计一套码本，体会“短码可以在不同模块中重复使用”为何能降低描述长度。
  • 思考题：信号转导网络是有向的。对它分别使用有向模块度和映射方程，你预计结果在哪些地方会不同？

Decelle, Krzakala, Moore & Zdeborová 2011：Inference and phase transitions in the detection of modules in sparse networks

  • 出处：Physical Review Letters 107: 065701。DOI：10.1103/PhysRevLett.107.065701
  • 背景：社团发现算法在什么条件下必然失败？这是一个与算法无关的信息论问题。
  • 核心发现：用统计物理的空腔方法与置信传播分析稀疏随机块模型，给出可检测性阈值 |cin−cout|=qc|c_{\text{in}}-c_{\text{out}}|=q\sqrt c，并指出 qq 较大时存在“可检测但计算困难”的区域。
  • 阅读提示：对照本专题推导 H的启发式论证，理解阈值中 c\sqrt c 的来源。
  • 思考题：一个实验测得的 PPI 网络平均度只有约 5。若其中的功能模块之间连接较多，你应如何解读社团发现“失败”的结果？

Peixoto 2019：Bayesian stochastic blockmodeling

  • 出处：收于 Doreian、Batagelj 与 Ferligoj 编 Advances in Network Clustering and Blockmodeling（Wiley），pp. 289–332。DOI：10.1002/9781119483298.ch11
  • 背景：随机块模型的最大似然无法自行确定组数，且只给出点估计。
  • 核心发现：系统介绍以非参数贝叶斯方法推断 SBM 的框架：微正则模型、最小描述长度、嵌套 SBM、度修正、重叠与加权扩展、MCMC 抽样与模型比较。
  • 阅读提示：这是一篇教程式的综述，配合 graph-tool 文档中的示例阅读最有效；Peixoto 2023 的短书进一步讨论了描述性与推断性方法的区别。
  • 思考题：在一个完全随机的 ER 网络上，模块度最大化与贝叶斯 SBM 分别会报告什么？为什么？

Data & tools相关数据与软件

软件/工具包Brain Connectivity Toolbox（MATLAB）脑网络图论指标的标准 MATLAB 函数集。软件/工具包WGCNA加权基因共表达网络分析的 R 包。软件/工具包NetworkXPython 中最常用的通用网络创建、分析与可视化库。软件/工具包igraph以 C 为核心、提供 R 与 Python 接口的高效网络分析库。软件/工具包graph-tool以 C++ 实现核心算法的高性能 Python 网络分析库。数据集SNAP 大型网络数据集斯坦福大学整理的大型真实网络数据集合。数据库Netzschleudergraph-tool 作者维护的网络数据目录与仓库。

Further延伸资源

类型 资源 说明
教材 Barabási, Network Science, Ch. 9 Communities（networksciencebook.com/chapter/9，CC BY-NC-SA 2.0） 免费在线教材：基本假设、层次聚类、模块度、重叠社团、社团检验、社团的刻画；Advanced Topics 含层次模型、模块度推导、Louvain 与 Infomap、团渗流阈值
公开课 Stanford CS224W（主页） 英文公开课，偏图机器学习；“强弱关系”与社团检测部分可与本专题对照，视频在 YouTube（需境外网络）
综述 Fortunato 2010, “Community detection in graphs”, Physics Reports 486: 75–174（DOI） 社团发现领域最全面的综述，篇幅很长，建议按需查阅相关章节
综述 Fortunato & Hric 2016, “Community detection in networks: A user guide”, Physics Reports 659: 1–44（DOI） 面向使用者的指南：社团的定义、方法类别、验证与常见陷阱，比 2010 年的综述更易读
综述 Peixoto 2023, Descriptive vs. Inferential Community Detection in Networks（Cambridge Elements，DOI） 系统论述两类方法的区别及模块度的统计问题
综述 Sporns & Betzel 2016, “Modular brain networks”, Annu. Rev. Psychol. 67: 613–640（DOI） 脑网络中社团发现的方法与应用
方法论文 Newman 2006, “Modularity and community structure in networks”, PNAS（DOI） 模块度矩阵与谱方法，推导简洁；论文精读见 Newman 2006
方法论文 Lancichinetti, Fortunato & Radicchi 2008, Phys. Rev. E 78: 046110（DOI）；Lancichinetti & Fortunato 2009, Phys. Rev. E 80: 056117（DOI） LFR 基准网络的构造，以及在其上对多种算法的系统比较
方法论文 Lancichinetti & Fortunato 2012, “Consensus clustering in complex networks”, Sci. Rep. 2: 336（DOI） 共识聚类的算法与实验
方法论文 Mucha et al. 2010, Science 328: 876–878（DOI） 多层与时变网络的模块度
软件 NetworkX 社团模块文档（networkx.org） girvan_newman、louvain_communities、leiden_communities、k_clique_communities、modularity、LFR_benchmark_graph 等，配合本专题代码示例使用
软件 leidenalg（文档） Leiden 算法的官方实现，支持模块度、CPM、多层网络等多种质量函数
软件 graph-tool（graph-tool.skewed.de） 贝叶斯随机块模型（嵌套、度修正、加权、多层）推断的主要实现
软件 Infomap（mapequation.org） 映射方程与 Infomap 的官方实现、在线演示与教程
软件 Brain Connectivity Toolbox（网站） 脑网络常用的模块度、共识、参与系数与模块内 zz 分数函数
经典数据 Zachary 1977, 空手道俱乐部原始论文（DOI） 了解这个“标准考题”的来历和实际的分裂过程

Open questions开放问题

  1. 在你的研究方向中，“社团”可能对应什么生物学实体（蛋白复合物、通路、细胞类型、脑功能系统、症状簇……）？如果你用社团发现算法得到了一个划分，你会用什么独立证据来验证它的生物学意义？
  2. 有人说“模块度最大化找到的社团，很大程度上取决于你选择的分辨率参数，所以社团发现是主观的”。你同意吗？请结合分辨率极限、稳定性分析和生物学验证，讨论怎样让社团分析的结论更可信。
  3. 你的网络更适合描述性方法还是推断性方法？如果用贝叶斯 SBM 得到“只有一个组”，而 Leiden 得到了 12 个模块，你会如何解读和报告？
  4. 对一个稀疏、存在大量未测相互作用的分子网络，怎样估计其中的社团结构是否处于可检测范围之内？可以设计什么样的模拟来回答这个问题？