跳至正文

社区发现：如何在网络中找到隐藏的部落

  • 由
🔵 数值验证 📅 2026年3月 ⏱ 阅读约12分钟

想象一幅巨大的社交地图：每个人是一个点，认识的人之间连一条线。如果你把这张地图放大来看，你会发现它并不是均匀分布的——人们天然地聚成一个个”部落”，有的以地域为界，有的以兴趣相连，有的因职业而集结。这种现象在互联网、大脑神经网络、蛋白质互作网络、乃至金融系统中普遍存在。

这就是社区发现（Community Detection）要解决的核心问题：如何让计算机自动在网络中找出这些”部落”？

听起来直觉上很简单，实则暗藏玄机。你马上会发现：“部落”到底是什么，取决于你怎么定义它。而这一问题的答案，在过去几十年里催生了一整个充满争论与惊喜的研究领域。[1][2]

📑 本文目录

一、网络里的部落：究竟在找什么？

在网络科学中，”社区”并不是一个精确定义的数学对象，而是一种直觉上合理、数学上有多种表达方式的结构。[1][2] 不同路线对应了截然不同的问题逻辑：

🔑 三种主流”部落”定义
  • 密度型：社区内的节点之间的连接，比它们与外部节点的连接更密集。这是最直觉的定义，也是模块度方法的出发点。
  • 信息流型：如果在网络上随机游走，你的路径容易被”困”在某些区域——这些区域就是社区。惜词如金的 Infomap 算法用的就是这个思路。
  • 生成模型型：假设整个网络是由若干”节点群体”按照不同的连接规则生成出来的，社区就是这些生成规则相同的节点集合。随机块模型（SBM）是典型代表。

这不是说哪种定义更”正确”——而是每种定义都在回答一个不同的问题。[1] 正如 Rosvall 等人在综述中指出的：

“不同的算法并不是在求解同一个问题的不同近似方案，而是在求解结构上不同的问题。”
—— Rosvall et al., 2019 [1]

这个认识本身就很重要：下次当两种算法在同一张网络上给出不同答案，你不必困惑哪个”错了”——它们可能都是正确的，只是在回答不同的问题。

二、最流行的尺子：模块度与它的陷阱

在所有社区发现方法中，模块度（Modularity）是被引用最广泛的指标，也是最多算法试图最大化的目标函数。[2] 它的核心思想是：好的社区划分，应该使得”社区内部实际连接数”比”随机情况下预期连接数”多得多。

📐 模块度公式
Q = (1 / 2m) × Σij [ Aij − (kikj / 2m) ] × δ(ci, cj)
  • m：网络中的边总数
  • Aij：邻接矩阵，节点 i 和 j 之间是否有连接
  • ki：节点 i 的度（有多少条连线）
  • δ(ci, cj)：如果 i 和 j 属于同一社区则为 1，否则为 0

翻译成人话：Q 值越高，说明网络里的”部落感”越强——同部落内部的连接，远比随机乱连要密得多。Q 的取值范围大致在 0 到 1 之间，实际应用中 Q > 0.3 通常被认为有较明显的社区结构。

然而，模块度最大化并不像看起来那么美好。研究者发现了两个根本性的缺陷：

缺陷一：分辨率极限

2007 年，Fortunato 和 Barthélemy 提出了一个令人不安的发现：当网络足够大时，模块度最大化会系统性地”看不见”真实存在的小社区——它会把它们错误地合并进大社区里去。[5]

💡 类比理解：卫星地图的分辨率

就像卫星地图有最小分辨率——缩到足够小的时候，小村庄会被周围的城市”吞并”，在地图上消失。模块度同样有一个内置的”分辨率尺”：社区尺寸如果比这把尺短，它就识别不出来。这个问题随网络规模增大而恶化。[5][6]

缺陷二：模块度景观的”平原问题”

更麻烦的问题来自 Good、de Montjoye 和 Clauset 的分析：模块度的”得分景观”极其平坦——大量彼此差异很大的划分，都能拿到几乎相同的高分。[7]

🔬 数值分析发现

研究者对真实网络进行分析，发现模块度最高分附近存在指数级数量的”次优解”，且这些解与最优解的社区结构可能差异显著。[7] 这意味着：即便你找到了”得分最高的划分”，也不能保证它就是最能反映真实结构的那个。

❌ 常见误区：高模块度 = 发现了真实社区

不一定。一次优化运行拿到的高分划分，可能只是众多同样高分划分中的随机一个。不同随机初始化可能给出完全不同的答案。稳妥的做法是多次运行、比较一致性，而不是迷信单次结果。[7][19]

模块度的变体层出不穷——有基于全局/局部差异的版本[8]，有用 Z-Score 做统计显著性修正的版本[9]——但有研究者指出，引入多分辨率参数并不能从根本上解决这些问题，结果仍然强烈依赖网络规模与结构。[6]

三、Louvain 与 Leiden：两个拼图者的故事

知道了模块度是个好用但有缺陷的尺子，接下来的问题是：怎么高效地找到让模块度最高的划分？ 对于大型网络，这是 NP-hard 问题，所以必须靠启发式算法。

Louvain：速度至上的贪心者

Louvain 算法是目前最广泛使用的社区发现算法之一。它的逻辑是贪心的：每次把一个节点移到让模块度增加最多的邻居社区，反复迭代直到无法提升为止，然后把每个社区压缩成一个”超级节点”，在新层级上重复。[4]

它的优势是极快——在数百万节点的网络上也能在秒级内给出结果。但问题是，快速贪心的代价是牺牲了结构质量检查。

🔬 Louvain 的结构缺陷

Traag 等人证明，Louvain 算法可能产生内部不连通的社区——即所谓”社区”内部，有些节点之间根本没有路径可以不经过社区外部而互相到达。[3] 这在网络分析中相当于宣布：你找到的”部落”其实是两个互不相识的群体被强行放在一起。

Leiden：修补匠的反击

为了解决这些问题，Traag、Waltman 和 van Eck 在 2019 年提出了 Leiden 算法。[3] 关键改进是在贪心移动之外，增加了一个 精炼阶段（refinement phase）：在合并社区之前，先把每个社区内部重新打散成子集，检查它们是否真的内部连通，再决定怎么合并。

🔵 Louvain vs Leiden 快速对比
维度 Louvain Leiden
速度 极快 稍慢（增加精炼步骤）
内部连通性 不保证（可能产生不连通社区） 有保证
划分质量 启发式，无质量下界 通常更优或等优
适用规模 百万级节点可用 同级别可用

后续也有研究尝试对 Louvain 的不连通社区问题进行修补，但在新项目中直接选 Leiden 通常是更明智的默认选择。

更深的教训是：启发式方法的流行往往是因为速度，而非正确性。2023 年的一项系统评测发现，常见的模块度最大化启发式算法，往往既达不到理论上的全局最优，也可能离最优结构相差甚远。[19]

四、换一种问法：随机块模型

到目前为止，我们一直在谈”找边更密的团块”。但还有一条完全不同的路：不要去”测量”社区，而是去”推断”它们是怎么产生的。

这正是随机块模型（Stochastic Block Model, SBM）的思路。[10]

🔑 SBM 的核心假设

假设网络是这样生成的：每个节点属于某个”块”（block），块与块之间的连接概率是固定的（同一块内部可能很高，也可能不高）。给定一张网络，我们想反推：节点最可能是按哪种”块结构”生成出来的？

📐 度校正 SBM（DC-SBM）的连接概率
P(Aij = 1) = θi × θj × ωcicj
  • θi：节点 i 的”连接倾向”参数（解释了为何有的人认识很多人，有的认识很少）
  • ωcicj：节点 i 所在块与节点 j 所在块之间的连接强度参数

翻译成人话：节点 i 和 j 之间会不会有连接，取决于两件事：他们各自有多”爱社交”（θ 参数），以及他们所在的两个社区之间关系亲不亲密（ω 参数）。把这两件事分开考虑，比普通 SBM 更符合真实网络中”大 V 连接很多人”的现实。

Karrer 和 Newman 于 2011 年提出的度校正 SBM（degree-corrected SBM）[10]，解决了标准 SBM 难以处理真实网络中”度分布高度不均匀”问题的根本缺陷。

SBM 路线有几个重要优势：

🌍 SBM 能做模块度做不到的事
  • 不只找”密集团”：ω 参数如果对角线低、非对角线高，SBM 也能识别出”二部图结构”或”中心-外围结构”——这些结构用模块度根本找不出来。
  • 自动推断社区数量：通过贝叶斯框架（如 collapsed SBM[11]），可以同时推断”有几个社区”，而不需要预先指定。
  • 扩展到复杂场景：二部网络[14]、有向网络、加权网络都有对应的 SBM 变体。
  • 理论保证：在适当条件下，谱方法与 SBM 结合有严格的统计一致性证明。[12]

当然，SBM 的代价是计算开销：精确的贝叶斯推断在大网络上代价高昂。实用化方向包括正则化 SBM[13]、高效 MCMC 推断[11]等。

五、真实的部落：重叠、层级与多重归属

到目前为止，我们一直在讨论”每个节点恰好属于一个社区”的情形。但现实是：真实世界中的节点，往往同时隶属于多个群体。

你既是家庭成员，又是工作同事，又是羽毛球爱好者——这三个圈子里的你，在社交网络中不可能被干净地归入单一社区。[15]

重叠社区：节点的多重身份

重叠社区检测的系统综述[15]（比较了 14 类算法）指出，允许重叠的方法在社会网络、生物网络等”天然重叠”的场景中表现更好，但计算复杂度通常也更高。

🔬 加权网络中的重叠社区

很多经典重叠社区方法只处理无权图（连接要么有要么没有）。但真实网络中边的强度往往大不相同——亲密朋友和点头之交在图中都只是”一条连线”，这显然不合理。Qing（2022）等人专门针对加权网络的重叠社区检测提出了新框架，更贴近真实应用场景。[17]

🔬 以节点为中心的重叠检测

Cohen 等人（2017）展示了如何把 Louvain 风格的局部搜索逻辑推广到重叠场景——允许每个节点在局部移动过程中探索多社区归属，而不只是”选边站”。[16]

层级社区：部落中的部落

真实网络的另一个重要特征是层级性：部落内部有亚部落，亚部落内部还有更小的群体。Schaub 等人（2023）的研究专门建立了层级社区结构的理论框架[18]，指出平面分区是对现实的过度简化。

💡 类比：行政区划的层级

国家 → 省 → 市 → 区 → 街道——这种层级本身就是有意义的信息，不同层级揭示不同粒度的社区结构。真实网络中的社区往往也有类似的”套娃”结构，而 Louvain 这样的算法只给你看一个固定粒度的切割。[18]

把重叠、层级、时间演化和多层关系放在一起，就会发现：任何单一算法都只能照亮真实网络结构的某一个侧面。[1] 这不是算法的失败，而是”社区”本身就是一个多维度概念的体现。

🌍 跨领域应用：社区发现无处不在
  • 神经科学：大脑的功能连接网络（fMRI）中，社区对应不同功能模块（视觉、运动、默认模式网络）。重叠社区方法在这里尤为关键，因为脑区常同时参与多个功能回路。[15]
  • 生物网络：蛋白质互作网络中的社区往往对应功能复合体或代谢通路。SBM 方法在二部网络（如药物-靶标网络）中有天然优势。[14]
  • 社会科学：在线社交平台的社区结构揭示了信息茧房、极化现象和意见传播动力学。Leiden 算法已成为大规模社会网络分析的标准工具。[3]

六、前沿：从优化到学习

社区发现领域最近十年最显著的趋势之一，是从”人工设计目标函数 → 贪心优化”转向”神经网络学习网络结构表示”。

🚀 神经嵌入方法（Neural Embeddings）

Kojaku 等人（2024）在 Nature Communications 上发表了基于神经嵌入的社区发现方法。[20] 核心思路是：先用神经网络把每个节点映射到一个低维连续空间（嵌入向量），使得结构相似的节点在嵌入空间中距离近；然后在这个空间中做聚类，找到社区。

这类方法的优势在于：它可以同时利用网络的拓扑结构和节点属性信息，而不只是看”谁和谁有边”。这对知识图谱、学术引用网络等场景尤其有价值。

🧪 思想实验：如果给每个节点一份”简历”

传统社区发现只看连接关系——谁认识谁。但如果每个节点还有属性（年龄、职业、兴趣），是否应该把这些信息纳入考量？纯图结构方法给不出答案；神经嵌入方法天然地为这个扩展提供了框架。当然，随之而来的问题是：到底是在发现”真实社区”，还是在发现”信息相似的群体”？这两者未必相同。

与此同时，传统统计推断路线也在持续进化：从固定 SBM 到正则化/鲁棒化版本[13]，再到可以处理二部网络[14]等特殊结构的扩展，SBM 家族的边界在不断扩大。

领域的整体趋势可以用一句话概括：从”找答案”到”问对问题”。 不再满足于”给我一个划分”，而是更关注：这个划分稳定吗？能反映真实机制吗？不同方法的结果为什么不一致？

🧭 混沌笔记点评

🎯 这篇文章的关键认知
  • 社区没有唯一正确答案：不同方法优化不同目标，它们的分歧不是错误，而是对”社区”定义本身分歧的映射。[1][2]
  • 模块度是把双刃剑：直觉合理、应用广泛，但有分辨率极限[5]和退化景观[7]两大根本缺陷，不能盲目信任单次最优结果。
  • Leiden 比 Louvain 更可靠：在有足够计算资源时，优先选 Leiden，它对连通性有保证，整体质量更稳定。[3]
  • SBM 是更诚实的框架：它明确地问”这张网是怎么产生的”，而不只是”边密不密”，适合需要可解释性的科学分析场景。[10]
  • 真实网络是重叠且层级的：任何平面非重叠划分都是对现实的简化，在解读结果时要保持清醒。[15][18]
  • 实践黄金法则：多种方法对比、多次运行检查稳定性、结合领域知识解读，比迷信某一个算法更重要。[19]

📚 参考文献

  1. Rosvall M, Dall J, Lancichinetti A, Larremore DB, Fortunato S. Different approaches to community detection. 2019. DOI: 10.1002/9781119483298.ch4 | arXiv
  2. Fortunato S. Community detection in graphs. Physics Reports. 2010. DOI: 10.1016/j.physrep.2009.11.002
  3. Traag VA, Waltman L, van Eck NJ. From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports. 2019. DOI: 10.1038/s41598-019-41695-z | PubMed
  4. Traag VA. Faster unfolding of communities: speeding up the Louvain algorithm. Physical Review E. 2015. DOI: 10.1103/PhysRevE.92.032801 | arXiv
  5. Fortunato S, Barthélemy M. Resolution limit in community detection. PNAS. 2007. DOI: 10.1073/pnas.0605965104
  6. Lancichinetti A, Radicchi F, Ramasco JJ, Fortunato S. Limits of modularity maximization in community detection. Physical Review E. 2011. DOI: 10.1103/PhysRevE.84.066122 | arXiv
  7. Good BH, de Montjoye YA, Clauset A. The performance of modularity maximization in practical contexts. Physical Review E. 2010. DOI: 10.1103/PhysRevE.81.046106 | arXiv
  8. Chen S, et al. Global vs local modularity for network community detection. PLOS ONE. 2018. DOI: 10.1371/journal.pone.0205284 | PubMed
  9. Miyauchi A, Kawase Y. Z-Score-Based Modularity for Community Detection in Networks. PLOS ONE. 2016. DOI: 10.1371/journal.pone.0147805 | PubMed
  10. Karrer B, Newman MEJ. Stochastic blockmodels and community structure in networks. Physical Review E. 2011. DOI: 10.1103/PhysRevE.83.016107
  11. McDaid AF, Greene D, Hurley N. Clustering in networks with the collapsed Stochastic Block Model. Statistical Analysis and Data Mining. 2013. arXiv
  12. Lei J, Rinaldo A. Consistency of spectral clustering in stochastic block models. Annals of Statistics. 2015. DOI: 10.1214/14-AOS1274 | arXiv
  13. Lu X, et al. A Regularized Stochastic Block Model for the robust community detection in complex networks. Scientific Reports. 2019. DOI: 10.1038/s41598-019-49580-5 | PubMed
  14. Yen T, et al. Community detection in bipartite networks with stochastic block models. Physical Review E. 2020. DOI: 10.1103/PhysRevE.102.032309 | PubMed
  15. Xie J, Kelley S, Szymanski BK. Overlapping Community Detection in Networks: the State of the Art and Comparative Study. ACM Computing Surveys. 2013. DOI: 10.1145/2501654.2501657 | arXiv
  16. Cohen Y, et al. Node-Centric Detection of Overlapping Communities in Social Networks. 2017. arXiv
  17. Qing H. Overlapping community detection in weighted networks. 2022. DOI: 10.1007/s00362-025-01758-y | arXiv
  18. Schaub MT, et al. Hierarchical community structure in networks. Physical Review E. 2023. DOI: 10.1103/PhysRevE.107.054305 | PubMed
  19. Aref S, et al. Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar. 2023. arXiv
  20. Kojaku S, et al. Network community detection via neural embeddings. Nature Communications. 2024. DOI: 10.1038/s41467-024-52355-w | PubMed