图论与社区发现：图的基本概念、社区结构定义、模块度优化简介
聊社区检测之前，得先把图论基础打牢。图这个玩意儿，说白了就是一组节点加上它们之间的连线。我最早接触图论是在做社交网络分析时，那时候真是被各种概念绕得头晕。后来发现，只要抓住几个核心点，后面看算法就跟翻书一样简单。
图的基本概念
一个图 G = (V, E)，V 是节点集合，E 是边集合。节点可以代表用户、网页、蛋白质……边代表他们之间的关系或连接。
- 无向图 vs 有向图：无向边就像朋友关系，没有方向；有向边就像关注关系，A→B 不代表 B→A。
- 加权图 vs 无权图：边上带权重，比如通信频率、距离。无权就当成权重都是1。
- 度的概念：无向图中节点的度就是连了多少条边；有向图又分出度和入度。
- 邻接矩阵：用矩阵
A表示，A[i][j] = w表示从 i 到 j 有一条权重为 w 的边。空间复杂度O(n²)，稀疏图用邻接表更划算。
举个例子，用 Python 的 networkx 创建一个无向图并查看度：
import networkx as nx
G = nx.Graph()
G.add_edges_from([(1,2), (1,3), (2,3), (3,4), (4,5), (4,6)])
print("节点度：", dict(G.degree()))
print("邻接矩阵：\n", nx.adjacency_matrix(G).todense())输出：节点 3 的度是 3（连接了1,2,4），节点 4 度是 3（连接3,5,6）。节点 1 度是 2。之前我在一个项目里用邻接矩阵存了 10 万个节点的图，直接内存爆炸——从那以后我学乖了，能用稀疏就用稀疏。
社区结构定义
社区是什么？看图的时候，你会发现有些节点内部连得特别密，和外部连接却很松散。这堆节点就构成一个社区。社区检测的目标就是把这些天然抱团的群体找出来。
| 特性 | 社区内部 | 社区之间 |
|---|---|---|
| 边密度 | 高 | 低 |
| 路径长度 | 短 | 长 |
| 聚类系数 | 高 | 低 |
| 典型例子 | 朋友圈 | 两个不相关群组之间的弱连接 |
社区没有唯一的标准定义。不过业界普遍接受“内部一致性高、外部耦合低”这个直觉。我踩过一个坑：把社区定义搞得太严，结果大部分节点都成了孤岛；定义太松，又什么都混在一起。后来我建议先用模块度扫一遍，再根据领域知识人工微调。
模块度优化简介
模块度（Modularity，记作 Q）是衡量社区划分质量的指标，由 Newman 和 Girvan 在 2004 年提出。公式长这样：
Q = (1 / 2m) * Σ[ A_ij - (k_i * k_j / 2m) ] * δ(c_i, c_j)
其中：
m = 图中总边数
A_ij = 邻接矩阵元素
k_i = 节点 i 的度
δ(c_i, c_j) = 1 如果 i 和 j 在同一社区，否则 0这个式子的核心思想很简单：用实际内部边数减去随机连接下的期望边数。如果实际比期望多很多，就说明这堆节点确实黏在一起。Q 的取值范围一般在 -1 到 1 之间，大于 0.3 就认为有不错的社区结构了。
模块度优化就是通过调整社区归属，使 Q 值不断增大。常见的优化策略有：
- 贪心合并：从每个节点一个社区开始，迭代合并能带来 Q 增量最大的社区对。
- 谱方法：把模块度矩阵的特征向量作为社区划分依据，适合小图。
- Louvain / Leiden 算法：层次化合并+细粒度优化，是目前最主流的方案（也是本课程后续重点）。
优化过程本质上是个 NP-hard 问题，所以实际用的都是启发式算法，不保证全局最优。不过实践中效果已经足够好。
这张图把今天讲的三个层次串在一起：底层是图的构成元素（节点和边），中层是社区结构定义，顶层是用模块度来量化评估。初学者先盯着这张图把概念关系捋顺，再深入具体算法时就不会迷路。