社区发现概述：图聚类的基本问题、应用场景与历史背景
图聚类，说白了就是把图中的节点分成若干组。组内连接紧密，组间连接稀疏。嗯，这就是社区发现的直觉定义。
我第一次接触这个概念，是在做社交网络分析的项目时。老板扔给我一份 Twitter 关注关系数据，说：“你把这个图的社区挖出来。”我当时一脸懵——什么是社区？后来才知道，社区就是那些“你关注他、他关注你、你们还共同关注一群人”的子图。
基本问题
社区发现本质上是图聚类问题。输入是一个图 \( G = (V, E) \)，输出是节点集合的一个划分 \( C = \{C_1, C_2, \dots, C_k\} \)。
问题在于：什么样的划分是“好”的？
- 模块度（Modularity）：衡量社区内边密度与随机图的差异。这是我这些年最常用的指标。
- 覆盖率：社区内边数占图总边数的比例。
- 分割质量：比如 Normalized Cut、Conductance 等。
但社区发现和普通聚类不一样——你没法直接用 K-means。图的拓扑结构决定了节点之间没有欧氏距离，只有连接关系。你想想看，两个用户即使没有直接关注，但有很多共同好友，他们可能属于同一个社区——这种“二阶邻居”的信息，普通聚类算法是抓不到的。
应用场景
社区发现的用途非常广。我举个例子，当年在电商推荐系统里，我们用社区发现找“兴趣圈”——把购买过同一类商品、浏览路径相似的用户聚成一个社区，然后给社区内部做协同过滤。效果比全局推荐提升了不少。
常见的场景有：
| 领域 | 典型问题 | 我的经验 |
|---|---|---|
| 社交网络 | 用户群体划分、意见领袖识别 | 我曾用 Louvain 找过 Twitter 上的谣言传播社区，效果很好 |
| 生物信息学 | 蛋白质交互网络的功能模块 | 蛋白网络稠密，用 Leiden 比 Louvain 稳定 |
| 金融风控 | 欺诈团伙检测 | 把交易图中的异常密集子图挖出来 |
| 推荐系统 | 兴趣群组发现 | 社区平均行为能缓解冷启动问题 |
历史背景
社区发现这个概念最早可以追溯到 1970 年代的社会网络分析。但真正引起计算机科学界广泛关注的，是 2002 年 Girvan 和 Newman 提出的 GN 算法。
GN 算法基于“边介数”反复删除边。我记得当时用这个算法处理一个 1 万个节点的图，跑了整整两天才出来。效率太低了。
2004 年，Newman 提出了模块度概念，从那以后几乎所有社区发现算法都绕不开这个指标。2006 年 Clauset、Newman 和 Moore 提出了 CNM 算法，用贪心的方式优化模块度。速度提升了一个数量级，但质量一般。
真正的突破是在 2008 年——Blondel 等人提出了 Louvain 算法。它用两阶段迭代：先贪心合并节点到邻居社区，再把每个社区收缩成一个超节点，重复这个过程。速度快、效果好，一度成为社区发现的工业标准。
但 Louvain 有个众所周知的 bug——它可能产生断开的社区。你用 Louvain 算出来的社区，内部居然可能是不连通的。我在项目中踩过这个坑：拿 Louvain 的社区划分去做图压缩，结果发现一个社区被分成两个不相连的子图，压缩后信息就断了。
2019 年，Traag 等人提出了 Leiden 算法。它在 Louvain 的基础上多了一步“细化”：把可能断开社区的节点重新分配，保证每个社区内部是连通的。同时，Leiden 还改进了局部移动策略，跑得更快。
一个简单的例子
用 Python 和 networkx 可以快速感受一下。下面是我常用的代码片段：
import networkx as nx
import community as community_louvain
# 创建一个空手道俱乐部图
G = nx.karate_club_graph()
# 运行 Louvain 算法
partition = community_louvain.best_partition(G)
# 打印社区分配
print(partition)输出结果是一个字典，每个节点对应一个社区 ID。你会发现空手道俱乐部图被分成了 4 个社区——这正好对应了实际那场俱乐部里的派系分裂。
社区发现的知识体系
为了让你对整个领域有个整体画面，我画了一张图：
这张图把社区发现的核心问题、挑战、应用和算法演进串起来了。你会发现，社区发现并不是一个孤立的问题，它和聚类、图论、统计学都有交叉。我个人习惯在开始新项目前，先把这张图在心里过一遍——清楚当前场景属于哪个象限，再选算法。
总结
社区发现说白了就是“给图里的节点分堆”。堆得好不好，看模块度；堆得快不快，看算法设计。
你知道 Louvain 为什么当年能火吗？因为它把复杂度压到了准线性，而且写出来的社区在大多数场景下都有意义。我见过不少生产系统，直接用 Louvain 跑千万级节点图，依然几分钟出结果。但后来大家发现它可能把社区“撕裂”，这才催生了 Leiden。
嗯，介绍到这里。接下来的章节我会带你深入 Louvain 和 Leiden 的细节，包括它们的原理、实现和调参技巧。你可以先用今天讲的基础概念，去试试手边的图数据，看看能挖出什么有意思的社区结构来。