k 核分解与核数

算法（剥洋葱）：反复删除当前度小于 $k$ 的节点（删除后邻居的度会减小，可能引发连锁删除），剩下的就是 k 核；令 $k=1,2,\dots$ 依次剥离，得到每个节点的核数。按当前度排序的桶实现（Batagelj 与 Zaversnik 2003）总代价 $O(M)$，适合百万级网络。

算例：一个三角形 $\{a,b,c\}$ 加一个只连在 $a$ 上的节点 $d$：$d$ 的度为 1，先被剥离，核数为 1；剩下的三角形每个节点度为 2，核数为 2。注意 $a$ 的度为 3，但核数只有 2，核数衡量的是节点所处“核心”的稠密程度，而不只是自己的度。空手道网络的最大核数为 4，最内层的 4 核包含 10 个节点（含两位核心人物 0 与 33）。

性质与用途：

• 核数是粗粒度的排序，大量节点并列，适合分层而不是精细排名；
• 核数对“位于边缘的枢纽”有区分力：一个连接着许多叶子的高度节点，核数可能很低。Kitsak 等（2010）在几个社会网络上做 SIR 模拟，发现单个传播源最终感染范围更好地由核数预测，而不是度或介数（论文精读：Kitsak 2010；传播背景见网络上的传播与免疫）；
• 加权推广为 s 核（所有节点强度 $\ge s$ 的极大子图，BCT 的 score_wu）；
• ER 网络中 $k\ge3$ 的 k 核以不连续方式突然出现（Pittel、Spencer 与 Wormald 1996），这与巨分支的连续相变形成对照；不同度分布下 k 核的组织见 Dorogovtsev 等（2006）。