团与密子图：最紧密的子群

Part 2”量”的前几篇文章中，我们学会了量距离（最短路径）、量重要性（中心性）、量社区（社区发现）和量相似性（图相似与同构）。现在进入 Part 2 的最后一站：量密度——图中最致密的子结构在哪里？

在社交网络中，有没有一群人彼此全认识？在金融交易网络中，一组账户之间是否存在异常紧密的转账关系？在蛋白质交互网络中，哪些蛋白质构成了功能模块？这些问题的共同核心是：找出图中最”抱团”的子结构。这个”抱团”可以有不同的严格程度——从最严格的团（每对都连）到较宽松的 k-core（每个节点度数够高），形成一个致密性的层级谱系。

算法范式：回溯 + 剪枝（Bron-Kerbosch）、对偶性（独立集 $\leftrightarrow$ 覆盖）

核心思想：致密性是一个谱系

在深入各个定义和算法之前，先建立一个直觉：致密子图不是一个单一概念，而是一个从严到宽的谱系。

最严格——团（Clique）：每对节点之间都有边。 $k$ 个节点的团有 $k(k-1)/2$ 条边，是 $k$ 个节点所能拥有的最大边数。
次严格——k-truss：每条边都参与至少 $k-2$ 个三角形。不要求全连接，但要求邻居之间也有连接。
较宽松——k-core：每个节点在子图内至少有 $k$ 个邻居。只约束度数，不约束邻居之间是否相连。

这三者形成严格的包含关系：团 $\subset$ k-truss $\subset$ k-core。越严格的定义越难计算——团是 NP-hard，k-core 是线性时间。这个谱系的另一端是独立集——没有任何边的节点集合，恰好与致密性相反，通过对偶性与顶点覆盖关联。

最大团（Max Clique）

定义：完全子图

团（clique）是图 $G = (V, E)$ 中的一个节点子集 $S \subseteq V$ ，使得 $S$ 中每对节点之间都有边。换句话说， $S$ 的导出子图（induced subgraph）是一个完全图（complete graph） $K_{|S|}$ 。

几个关键定义：

极大团（maximal clique）：不能再加入任何节点而保持”团”性质的团。即不存在 $v \notin S$ 使得 $S \cup \{v\}$ 仍是团。
最大团（maximum clique）：节点数最多的极大团。最大团的大小称为团数（clique number），记为 $\omega(G)$ 。
区分”极大”和”最大”：一张图可能有很多极大团（大小不同），最大团是其中最大的那个。

例子：在上图中， $\{A,B,C,D\}$ 是最大团（ $\omega(G) = 4$ ），而 $\{E,G\}$ 也是一个极大团（不能再加入节点扩展它），但不是最大团。

Bron-Kerbosch 算法

枚举所有极大团的经典算法是 Bron 和 Kerbosch 在 1973 年提出的回溯算法。

核心思想：维护三个节点集合——

$R$ （已选集）：当前正在构建的团
$P$ （候选集）：还可以加入 $R$ 的节点（即与 $R$ 中所有节点相邻）
$X$ （排除集）：与 $R$ 中所有节点相邻，但已经在之前的分支中被处理过的节点

基本递归：

BronKerbosch(R, P, X):
    if P = ∅ and X = ∅:
        report R as a maximal clique
    for each v ∈ P:
        BronKerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P = P \ {v}
        X = X ∪ {v}

逐行理解：

P = ∅ and X = ∅：没有候选节点可以加入，也没有被排除的节点说明存在更大的团。所以 $R$ 是极大团。
P ∩ N(v)：加入 $v$ 后，只有 $v$ 的邻居还有可能扩展团（非邻居加入会破坏完全图性质）。
X ∩ N(v)：同理，只关心 $v$ 的邻居中已排除的节点。
P = P \ {v}; X = X ∪ {v}： $v$ 处理完毕，从候选移到排除（避免重复报告包含 $v$ 的团）。

初始调用：BronKerbosch(∅, V, ∅) — 从空团、全部节点作为候选开始。

Pivot 剪枝

基本版在最坏情况下会产生大量不必要的递归。pivot 优化选择一个”pivot 节点” $u \in P \cup X$ （通常选度最大的），只对 $P \setminus N(u)$ 中的节点进行递归：

BronKerboschPivot(R, P, X):
    if P = ∅ and X = ∅:
        report R as a maximal clique
    choose pivot u ∈ P ∪ X maximizing |P ∩ N(u)|
    for each v ∈ P \ N(u):
        BronKerboschPivot(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P = P \ {v}
        X = X ∪ {v}

为什么 pivot 有效？ 如果 $v \in P \cap N(u)$ ，那么包含 $v$ 的极大团必然也包含 $u$ （或者在处理 $u$ 时已经被覆盖）。因此跳过 $N(u)$ 中的节点不会遗漏任何极大团，但大幅减少了搜索分支。

走查：6 节点图上的 Bron-Kerbosch

用一个具体例子走一遍算法。图有 6 个节点 A-F，边集：A-B, A-C, A-D, B-C, B-D, C-D, D-E, E-F。最大团是 $\{A,B,C,D\}$ （4-团）。

步骤	R	P	X	动作
1	$\emptyset$	$\{A,B,C,D,E,F\}$	$\emptyset$	选 pivot=D（度最高=4）， $N(D)=\{A,B,C,E\}$ ，遍历 $P \setminus N(D) = \{D,F\}$
2	$\{D\}$	$\{A,B,C,E\}$	$\emptyset$	进入 $v{=}D$ 分支： $P \cap N(D) = \{A,B,C,E\}$
3	$\{D,A\}$	$\{B,C\}$	$\emptyset$	子调用选 $v{=}A$ ： $P \cap N(A) = \{B,C\}$
4	$\{D,A,B\}$	$\{C\}$	$\emptyset$	继续扩展 $B$ ， $C$ 与 $A,B,D$ 都相邻
5	$\{D,A,B,C\}$	$\emptyset$	$\emptyset$	报告最大团 $\{A,B,C,D\}$
6	$\{D,E\}$	$\emptyset$	$\emptyset$	回到步骤 2，子调用选 $v{=}E$ ： $P \cap N(E) = \emptyset$ ，报告极大团 $\{D,E\}$
7	$\{F\}$	$\{E\}$	$\emptyset$	回到步骤 1，进入 $v{=}F$ 分支： $P \cap N(F) = \{E\}$
8	$\{F,E\}$	$\emptyset$	$\emptyset$	报告极大团 $\{E,F\}$

算法找到 3 个极大团： $\{A,B,C,D\}$ 、 $\{D,E\}$ 、 $\{E,F\}$ 。最大的是 $\{A,B,C,D\}$ ， $\omega(G) = 4$ 。

NP-hard：为什么没有多项式算法

最大团问题是 NP-hard（准确地说，判定版本”图中是否存在大小为 $k$ 的团？“是 NP-complete）。

直觉： $n$ 个节点的图有 $2^n$ 个子集。最坏情况下，需要检查指数多个子集才能确定最大团。Moon 和 Moser（1965）证明了一个图最多有 $3^{n/3}$ 个极大团——这是一个指数级的数。

实际意义：

Bron-Kerbosch（带 pivot）的最坏时间复杂度为 $O(3^{n/3})$ （Tomita, Tanaka & Takahashi, 2006 证明了这个上界是 tight 的）
对于稀疏图（ $m \ll n^2$ ），Eppstein, Löffler & Strash (2013) 给出了 $O(d \cdot n \cdot 3^{d/3})$ 的复杂度，其中 $d$ 是退化度（degeneracy）。在现实世界的稀疏图中， $d$ 通常很小，算法表现良好
除非 P = NP，否则不存在找最大团的多项式时间算法。关于 NP-hard 问题和近似策略，详见 Art. 15: NP-hard 与近似

k-core 分解

团要求”每对都连”，这太严格了——现实中很少有完美的完全子图。k-core 是一个更实用的致密性度量。

定义

图 $G = (V, E)$ 的 $k$ -core 是一个极大子图 $H \subseteq G$ ，使得 $H$ 中每个节点的度数至少为 $k$ ：

$\forall v \in V(H): \deg_H(v) \geq k$

注意度数是在子图 $H$ 内计算的，不是在整个图 $G$ 中。

每个节点的 core number（核心数） $\text{core}(v)$ 是包含 $v$ 的最大 $k$ 值的 $k$ -core 的 $k$ ：

$\text{core}(v) = \max \{k : v \in k\text{-core of } G\}$

关键性质：

$k$ -core 一定是 $(k-1)$ -core 的子图： $k\text{-core} \subseteq (k-1)\text{-core}$ 。等价地说，如果一个节点在 $k$ -core 中，它一定也在所有 $j$ -core（ $j < k$ ）中。
整张图本身是 0-core（每个节点度数 $\geq 0$ ）。
最内层的 core 是最致密的区域。

线性时间算法：逐步剥离

k-core 分解最优雅的性质是它可以在 $O(n + m)$ 线性时间内完成，使用一个简单的”洋葱剥皮”算法（Batagelj & Zaversnik, 2003）：

KCoreDecomposition(G):
    计算所有节点的度数 deg[v]
    将节点按度数排入桶（bucket sort）
    for each v in degree-ascending order:
        core[v] = deg[v]      // v 的 core number = 删除时的度数
        for each neighbor u of v (where u not yet processed):
            if deg[u] > deg[v]:
                deg[u] -= 1   // u 的有效度数减 1
                更新 u 在桶中的位置

直觉：从度最小的节点开始”剥”——度为 0 的先剥掉（core=0），然后度为 1 的（core=1），以此类推。每次剥掉一个节点，它的邻居有效度数减 1，可能导致更多节点被”连锁剥离”。最后剩下的是核心最致密的区域。

复杂度分析：

桶排序 $O(n)$
每条边最多被处理两次（两个端点各一次）→ $O(m)$
总计 $O(n + m)$

这比找最大团（NP-hard）容易得多！k-core 是可以大规模使用的致密性工具。

走查：10 节点图上的 k-core 分解

下面的交互组件展示”洋葱剥皮”过程。观察如何从外层逐步删除低度节点，最终留下最致密的核心。

k-core 分解走查无向图 · 10 节点 · 14 条边

步骤 1/7: 初始状态：10 个节点，14 条边。我们将逐步删除低度节点，从 k=1 开始"剥洋葱"。

1 / 7

注意关键时刻：

H 和 J 只有 1 个邻居（度=1），最先被剥离，core number = 1
E, F, G, I 在剩余图中度数=2，第二轮被剥离，core number = 2
A, B, C, D 构成完全图 $K_4$ ，每个度数=3，无法继续剥离，core number = 3

k-core 与社区发现的关系

在 Art. 8: 社区发现中，k-core 已经作为一种社区发现的预处理手段出现。高 core number 的区域通常对应紧密的社区核心。在大规模图分析中，常见的策略是：

先做 k-core 分解，找出致密核心区域
在高 k-core 上运行更精细的社区发现算法（如模块度优化、标签传播）
这样既缩小了搜索空间，又聚焦在真正有结构的区域

k-truss：比 k-core 更严格

k-core 只约束度数——一个节点度数够高，但它的邻居之间可能完全不相连。k-truss 引入了更强的约束：基于三角形。

定义

图 $G$ 的 $k$ -truss 是一个极大子图 $H$ ，使得 $H$ 中每条边都参与至少 $k-2$ 个三角形：

$\forall (u, v) \in E(H): |\{w \in V(H) : (u,w) \in E(H) \land (v,w) \in E(H)\}| \geq k - 2$

换句话说，每条边的两个端点至少有 $k-2$ 个共同邻居在子图内。

k-truss vs k-core：

k-core 只看节点的度数（邻居数量）
k-truss 看边参与的三角形数量（邻居之间的连接）
因此 k-truss 保证了更强的局部连通性——不只是”我有很多邻居”，而是”我的邻居之间也互相认识”

算法：k-truss 分解可以通过类似 k-core 的迭代剥离完成——反复删除参与三角形数少于 $k-2$ 的边。时间复杂度取决于三角形计数，通常为 $O(m^{3/2})$ 。

独立集与顶点覆盖

致密子图寻找的另一面是独立集——图中最大的”互不相连”的节点集合。看似和团无关，但它们通过精美的对偶关系紧密联系。

定义

独立集（independent set）： $S \subseteq V$ ， $S$ 中没有任何两个节点相邻。独立数 $\alpha(G) =$ 最大独立集的大小。
顶点覆盖（vertex cover）： $C \subseteq V$ ，图中每条边至少有一个端点在 $C$ 中。顶点覆盖数 $\beta(G) =$ 最小顶点覆盖的大小。

直觉：独立集选的是”互不干涉”的节点，顶点覆盖选的是”覆盖所有关系”的节点。

Gallai 定理：完美对偶

定理（Gallai, 1959）：对于任意图 $G = (V, E)$ ，

$\alpha(G) + \beta(G) = |V|$

证明：设 $S$ 是一个最大独立集。则 $C = V \setminus S$ 是顶点覆盖——因为如果某条边 $(u,v)$ 的两个端点都不在 $C$ 中，那么 $u, v \in S$ ，但 $S$ 是独立集， $u$ 和 $v$ 不相邻，矛盾。反之， $S$ 是独立集当且仅当 $V \setminus S$ 是顶点覆盖。因此最大独立集 + 最小顶点覆盖 = $|V|$ 。

这个对偶关系的实际意义是：找最大独立集等价于找最小顶点覆盖——解决一个问题就自动解决了另一个。

团与独立集的关系

另一个有趣的联系：图 $G$ 中的最大团 = 补图 $\bar{G}$ 中的最大独立集。

$\bar{G}$ 是 $G$ 的补图（complement graph）： $G$ 中有边的地方 $\bar{G}$ 没有， $G$ 中没有边的地方 $\bar{G}$ 有。

在 $G$ 中，团要求”每对都连”。在 $\bar{G}$ 中，这些”每对都连”的节点变成了”每对都不连”——恰好是独立集。

NP-hard

最大独立集、最小顶点覆盖（一般图）、最大团——这三个问题都是 NP-hard 的。它们之间的规约非常直接：

最大独立集 $\leftrightarrow$ 最小顶点覆盖：Gallai 定理
最大团 $\leftrightarrow$ 最大独立集：补图变换

所以本质上它们是”同一个问题”的不同面貌。

有一个重要的特例：在二部图（bipartite graph）上，最小顶点覆盖 = 最大匹配（König 定理）。这意味着二部图上的顶点覆盖（和独立集）可以在多项式时间内求解——通过最大匹配算法。这将在 Art. 13: 匹配中深入讨论。

复杂度对比表

问题/方法	时间复杂度（最坏）	适用场景	NP-hard?
k-core 分解	$O(n + m)$	大规模图的致密区域发现	否
k-truss 分解	$O(m^{3/2})$	比 k-core 更严格的致密性	否
枚举所有极大团 (Bron-Kerbosch + pivot)	$O(3^{n/3})$ 最坏；稀疏图 $O(d \cdot n \cdot 3^{d/3})$	小图或稀疏图的完整团枚举	—
最大团	NP-hard	小图精确求解	是
最大独立集	NP-hard	小图精确求解	是
最小顶点覆盖（一般图）	NP-hard	小图精确求解	是
最小顶点覆盖（二部图）	$O(\sqrt{n} \cdot m)$ via Hopcroft-Karp	二部图 — König 定理	否

关键洞察：致密性要求越严格，计算代价越高。k-core 线性时间、k-truss 次二次、团问题 NP-hard。实际应用中，k-core 和 k-truss 往往是更务实的选择。

应用场景

欺诈检测：紧密交易圈

在金融交易网络中，一组账户之间频繁互相转账形成”循环转账圈”。这样的紧密交易圈在图上表现为高 k-core 或团。PayPal 和 Ant Financial（蚂蚁金服）的反欺诈系统使用 k-core 分解作为第一步筛选：核心数异常高的子图是值得深入调查的可疑区域。一个 2019 年的案例分析（Pourhabibi et al., Fraud detection in financial networks）中，k-core 将需要审查的交易子图从百万级缩减到数千级。

蛋白质交互网络

在蛋白质-蛋白质交互（PPI）网络中，致密子图对应蛋白质功能模块——一组协同工作的蛋白质。Bader & Hogue (2003) 的 MCODE 算法本质上就是在 PPI 网络中寻找高权重的 k-core 结构。人类蛋白质交互网络约有 20,000 个节点和 300,000+ 条边，k-core 分解的线性时间复杂度使得大规模分析成为可能。

社交圈发现

Facebook 的 ego-network 研究（McAuley & Leskovec, 2012）发现用户的”朋友圈”自然对应不同层次的 k-core。核心朋友圈（core number 高）是日常互动最频繁的小群体，外围（core number 低）是点头之交。k-truss 在这里比 k-core 更精准——因为真正的朋友圈不只是”大家都认识我”，而是”大家也互相认识”。

🔁 迭代机器视角 — Bron-Kerbosch (Maximum Clique)CST: 约束满足

Graph	搜索树（隐式）
State[v]	当前 clique R + 候选集 P + 排除集 X
SELECT	LIFO（DFS 回溯）+ pivot 剪枝
COMBINE	尝试将节点加入当前 clique → 检查完全连接
重入	可回退
TERMINATE	P 和 X 都为空（极大团）或穷尽
求解方法	B&P

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — k-core DecompositionSTR: 结构计算

Graph	原图（逐步剥离）
State[v]	节点度数 + core number
SELECT	最小度节点优先（类似 PQ-min）
COMBINE	删除节点 → 更新邻居度数
重入	无
TERMINATE	所有节点已处理
求解方法	FI

k-core 剥离过程类似 Kahn 拓扑排序——都是反复删除'最弱'节点

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文建立了图中致密子结构的完整谱系——从最严格到最宽松：

团（Clique）：每对节点都直接相连。找最大团是 NP-hard，Bron-Kerbosch（回溯 + pivot 剪枝）是枚举所有极大团的经典算法
k-truss：每条边参与至少 $k-2$ 个三角形。比 k-core 更严格， $O(m^{3/2})$ 可解
k-core：每个节点度数 $\geq k$ 。洋葱剥皮算法 $O(n + m)$ 线性时间——是大规模图分析中最实用的致密性工具
独立集 $\leftrightarrow$ 顶点覆盖：Gallai 定理给出完美对偶 $\alpha(G) + \beta(G) = |V|$ ；一般图上都是 NP-hard，但二部图上可通过 König 定理 + 最大匹配高效求解
核心洞察：致密性要求越严格 → 计算越困难。实践中 k-core/k-truss 是务实选择

Part 2”量”到此告一段落。我们从距离、重要性、社区、相似性一路量到致密性，对图的度量手段已经相当丰富。接下来进入 Part 3”优”——不再只是”看清图是什么样的”，而是”在图上做出最好的决策”。第一站是 Art. 11: 最小生成树——用最小的代价连通所有节点。

实现指引

算法	库	函数/方法
所有极大团枚举	NetworkX	`nx.find_cliques(G)`
最大团大小	NetworkX	`nx.graph_clique_number(G)`
k-core 分解	NetworkX	`nx.core_number(G)`, `nx.k_core(G, k)`
k-truss	NetworkX	`nx.k_truss(G, k)`
最大独立集	NetworkX	`nx.maximal_independent_set(G)` (贪心近似)
最小顶点覆盖	NetworkX	`nx.min_weighted_vertex_cover(G)` (2-近似)
k-core	igraph	`g.coreness()`, `g.k_core(k)`
团枚举	igraph	`g.cliques(min=k)`
k-core 分解	Neo4j GDS	`gds.kcore.stream(graph)`
三角形计数	NetworkX	`nx.triangles(G)`
k-core 分解	scipy	无直接支持，用 NetworkX 或 igraph