k-核分解

定义

剥离算法

从 $k=1$ 开始，反复删去当前度小于 $k$ 的节点（删除会降低邻居的度，可能引发连锁删除），直到没有可删的节点，剩下的就是 $k$-核；然后 $k\leftarrow k+1$。Batagelj 与 Zaversnik（2011, Advances in Data Analysis and Classification）用“按当前度分桶”的方法使整个分解的时间复杂度为 $O(L)$。伪代码见数学推导与算法，代码示例用最小堆实现，复杂度 $O(L\log N)$，并与 nx.core_number 逐节点对照。

算例：一个三角形 $\{a,b,c\}$ 加上一条挂在 $c$ 上的路径 $c-d-e$。删去度为 1 的 $e$，$d$ 的度降为 1，也被删去；剩下三角形中每个节点度为 2，于是 $a,b,c$ 的核数为 2，$d,e$ 的核数为 1。注意 $c$ 的度为 3，但核数只有 2：核数衡量的是“嵌在多稠密的子图里”，而不是边数。

核数、度与度相关

核数与度高度相关但不等同。度相同的节点可以处在不同的壳层（代码示例中，幂律随机网络里度为 6 的节点分布在 2、3、4 三个壳层）；一个连着很多叶子的枢纽可能核数很低。度相关直接影响核结构：同配网络中高度节点彼此相连，形成深而稠密的内核；异配网络的内核浅。代码示例中，同一度序列的网络经同配重连后，最大核数从 9 升到 20。还要注意，BA 网络中每个新节点恰好带 $m$ 条边加入，整张图就是一个 $m$-核，壳层结构是平凡的，不适合作为 k-核分析的模型示例。

应用

• 影响力传播者：Kitsak 等（2010, Nature Physics）在多个真实网络的 SIR/SIS 模拟中发现，单个起始节点的传播范围由其核数比由度或介数中心性预测得更好（精读见 Kitsak 2010，与网络上的传播与免疫相联系）。
• 相互作用组的“骨架”：Wuchty 与 Almaas（2005, Proteomics）对酵母蛋白质相互作用网络做核分解，发现越靠内层的核中，必需蛋白和进化保守蛋白的比例越高，而且这一结果对相互作用数据的误差较稳健。
• 脑结构核心：Hagmann 等（2008, PLoS Biology）用 $k$-核与强度版本的 $s$-核分解弥散谱成像结构网络，识别出位于后内侧与顶叶皮层的结构核心（精读见 Hagmann 2008）。
• 理论：Dorogovtsev、Goltsev 与 Mendes（2006, PRL）研究了随机网络中 $k$-核的出现条件（$k$-核渗流），对 $k\ge3$ 它与普通巨分支出现的连续相变性质不同。