K-core

定义

普遍认为k-core概念由Seidman首次提出，对于给定的网络，递归删除网络中度数小于k的节点可以得到网络的极大子图，其中每个节点的度数不小于k（不考虑子图外的连接情况），该子图为原网络的k-core。与k-core密切相关的概念还包括:

• k-shell：属于k-core，但不属于(k+1)-core的点集，通过k-core分解过程可以将网络根据k-shell进行分层。
• k-crust：从1到k的k-shell的并集，代表网络的外围结构
• k-corona：k-core中度数恰好为k的节点组成的点集
• coreness：一个节点如果属于k-shell, 该节点的coreness为k

在对k-core的研究中，人们注意到了k-core剪枝过程的临界性。剪枝过程的结果只有两种，要么网络消失，没有节点在剪枝过程中保留下来；要么无法进一步去除节点，网络最终拥有一个固定大小的 k-core。k-core剪枝过程是少数几个详细介绍精确临界行为并用解析法求解的例子之一。k-core剪枝过程的解析解为研究临界现象提供了新的见解，吸引了众多科学家。并且，由于k-core 分解能够简单高效地找到网络的核心结构，k-core及相关的概念包括（k-shell、coreness）被广泛应用于多个科学领域，包括 生物学、生态学、计算机科学、信息传播、地质学 等等。

k-core和coreness示意图

k-core分解的算法实现

剪枝过程（pruning process）是常用的进行k-core分解的算法，通过递归删除网络中度小于k的节点实现。论文提出了复杂度为O(m)（ m为网络中边的数量）的高效计算每个节点coreness的方法（k-core即为coreness不小于k的节点构成的子图）。算法的思想简单描述为：从度最小的节点开始，检查每个邻居节点的度，如果邻居节点的度更大，则将这条边移除并更新该节点的度，选择下一个度最小的节点重复以上过程。每个节点最终的度为节点的coreness。该算法需要检查网络中的每一条边，因此算法复杂度为O(m)。 具体算法描述如下:
INPUT: graph G = (V, L) represented by lists of neighbors
OUTPUT: table core with core number for each vertex

compute the degrees of vertices;

order the set of vertices V in increasing order of their degrees;

for each v ∈ V in the order do begin

core[v] := degree[v];

for each u ∈ N eighbors(v) do

if degree[u] > degree[v] then begin

degree[u] := degree[u] − 1;

reorder V accordingly

end

end;

python库networkx基于该算法实现了计算网络的k-core的函数和每个节点coreness的函数：

• netwokx.k_core(G,k)：获取网络G的k-core
• netwokx.core_number(G)：获取网络G每个节点的coreness

k-core分解的理论研究

不相关网络k-core分解的特征

对于k-core的理论研究主要关注k-core的临界性。经过剪枝过程网络可能完全消失没有节点保留，也有可能留下一个一定大小的k-core无法进一步的移除节点。k-core分解过程的临界点，k-core与网络结构的关联都是研究者关注的地方。对于k-core分解过程的特征的研究出发点通常是一个具有已知度分布和度密度的大型非关联随机网络，其统计特性由其度分布决定，具有相同度分布和相同度密度的随机网络可以被视为在结构上不可区分的。 1987年, Luczak首次从理论上研究 k-core 问题，关于随机网络G(n, p)中 k-core 的大小得出了以下三个定理：

（G(n, p) 是一个具有n个节点的网络，其中每对节点以概率p独立连接，v(k, n, p)表示k-core的节点数量，c表示网络平均度）

• 定理1：如果k > 3, v(k, n, p) = 0 或者 v(k, n, p) > 0.0002n 当 n → ∞ 以接近1的概率成立
• 定理2：对于任意ε> 0，存在常数d，使得当 c > d 且 [math]\displaystyle{ k \lt c - c^{0.5+ε} }[/math] 时，随着 n 趋近于无穷大，[math]\displaystyle{ v(k, n, p) \gt n − n·exp(-c^{ε}) }[/math]的概率趋近于 1
• 定理3：对于任意ε> 0，存在常数d，使得对所有 k 和 c > d，当 [math]\displaystyle{ n \rightarrow \infty }[/math]时，v(k, n, p) = 0或者[math]\displaystyle{ v(k, n, p) \gt n - nc ^{-0.5+ε} }[/math]以接近1的概率成立

第一个定理指出，对于 𝑘≥3，k-core 中的节点数要么为 0，要么大于0.0002n。这表明了一个不连续变化的存在。从其余两个定理中可以看出，在某些条件下，当平均度 c 足够大时，k-core 的大小要么为 0，要么非常大（几乎占据整个网络），这同样暗示了变化的不连续性。

G. J. Baxter [20]推导出了描述k-core剪枝过程的精确方程，并对其进行了数值求解。通过分析从第n步到第n+1步的剪枝过程，他们得出了四个递推方程：

[math]\displaystyle{ (1)P(q,t+1) = P(q,t)-r_t q P(q,t) + r_t(q+1)P(q+1,t) }[/math]

[math]\displaystyle{ (2)P(k-1,t+1) = r_t k P(k,t) }[/math]

[math]\displaystyle{ (3)P(0,t+1) = P(0,t) + P(k-1,t) }[/math]

[math]\displaystyle{ (4){\lt q\gt }_t = (k-1)P(k-1,t) + \sum_{q \ge k} qP(q,t) }[/math]

其中，[math]\displaystyle{ {\lt q\gt }_t }[/math]表示经过t步剪枝过程留下的网络的平均度，[math]\displaystyle{ r_t = \frac 1 {\lt q\gt _t} \sum_{q\lt k}qP(q,t) }[/math]表示经过t步剪枝过程留下的网络度小于k的节点的概率，[math]\displaystyle{ P(q,t) }[/math]表示经过t步剪枝过程留下的网络中度为q节点的概率

经过ER网络上的计算和模拟，他们发现存在一个临界阈值[math]\displaystyle{ \lt q\gt _c }[/math]根据初始网络的平均度⟨q⟩是高于、等于还是低于该阈值，系统表现出三种不同的行为：

首先，当[math]\displaystyle{ \lt q\gt }[/math]高于阈值时，网络会以指数形式弛豫到稳定的 k-core 状态。随着 ⟨q⟩ 趋近于临界值 [math]\displaystyle{ {⟨q⟩}_c }[/math]，弛豫时间发散，表现出一种被称为“临界慢化（critical slowing down）”的现象。

其次，在临界点[math]\displaystyle{ \lt q\gt =\lt q\gt _c }[/math]时，系统处于临界状态，其动力学表现为幂律弛豫过程，具体表现为依赖[math]\displaystyle{ 1 / t^2 }[/math]的衰减行为。

第三，当[math]\displaystyle{ \lt q\gt }[/math]低于阈值时，系统会经历一个持续时间较长的瞬态过程（“plateau”stage）,该过程最终会以网络整体崩溃结束，即整个网络结构的消失。

k-core分解过程中k-core大小随时间变化

不相关网络k-core分解过程

S. N. Dorogovtsev [22]推导出了描述任意度分布的受损的随机不相关网络中 k-core 结构的精确方程。这一结果可以计算各种受损或未受损的随机网络中 k-core 的大小及其其他结构特征，并揭示复杂网络中 k-core 渗流的本质。
对于一个不相关网络（根据度分布由配置模型生成），考虑到无限稀疏的配置模型的树状结构特点，可以发现其k核与无限（k−1）叉子树（每个子节点至少有k-1个子代）完全重合。 P(q)为度分布,Q=1-p表示网络中随机移除的节点的比例。设R为网络中某条边的一端不是无限（k-1）叉子树根节点的概率，那么一个节点属于k-core的概率
[math]\displaystyle{ M(k)=p\sum_{q \ge k}P(q)\sum _{n=k}^{q}C_n^q R^{q-n} (1-R)^n }[/math]
如果某条边的某一端至多有k−2 个子分支是无限(k−1) 叉子树的根节点，那么该端本身就不能成为无限(k−1) 叉子树的根节点。由此导出关于R的方程：
[math]\displaystyle{ R=1-p+p\sum^{k-2}_{n=0}[\sum_{i=n}^{\infty} \frac {(i+1)P(i+1)}{z_1} C_n^i R^{i-n}(1-R)^n] }[/math]
对于这个方程的解释如下：

• 第一项，1-p=Q表示网络中边的一端被移除的概率，对于未受损的网络方程中的p=1
• 第二项中 [math]\displaystyle{ C_n^i R^{i-n}(1-R)^n] }[/math]是边的一段具有i个子节点并且其中有n个是k-1叉树根节点的概率
• 第二项中 [math]\displaystyle{ \frac {(i+1)P(i+1)}{z_1} }[/math] 随机选择的一条边连接到具有i个分支的顶点的概率
• 第二项中 [math]\displaystyle{ z_1 = \sum_q qP(q) }[/math] 一个顶点的平均邻居数量

对于k-core的度分布表示如下： [math]\displaystyle{ P_k(q) = \frac {p}{M(k)} \sum_{q' \ge q}P(q')C_q^{q'}R^{q'-q}(1-R)^q }[/math]
k-core的平均度可以表示为[math]\displaystyle{ z_1(k) = \sum_{q \ge k}P_k(q)q }[/math]
属于k-core但不属于k+1-core的节点，即k-shell的大小可以表示为 [math]\displaystyle{ S(k) = M(k)-M(k+1) }[/math]

相关网络k-core分解过程

Shi et al. [24]使用基于非回溯拓展分支（NBEB-NonBacktracking Expansion Branch）的方法给出了k-core大小的精确解析解，首次揭示了k核剪枝过程中临界现象的精确行为特征。。他们的研究表明Baxter等人[20]提出的四个方程简化为单变量迭代形式，且k核剪枝过程能够完美映射至该迭代。论文中推导出了这一迭代的通用表达式。只要给定初始状态，便可计算出单变量迭代的每个中间状态，从而精确对应k核剪枝过程的每个阶段。特别地，对于随机生成的不相关网络，该理论能准确解析出剪枝过程中任意中间阶段所剩k-core的规模与结构特征。数值模拟结果进一步验证了理论分析的正确性。

用e表示边，v表示点，[math]\displaystyle{ \alpha和\beta }[/math]表示节点下标，j、l、m表示节点的度，[math]\displaystyle{ e_{2 \rightarrow 1} }[/math]表示从节点[math]\displaystyle{ v_2 到 v_1 }[/math]的有向边，用[math]\displaystyle{ S_1 }[/math]表示从v1到其每个邻居节点的有向边集合，[math]\displaystyle{ S_{2 \rightarrow 1} }[/math]表示所有在[math]\displaystyle{ S_1 }[/math]除了[math]\displaystyle{ e_{1 \rightarrow 2} }[/math]的边。定义NBEB [math]\displaystyle{ B_{2 \rightarrow 1} }[/math]为从根边[math]\displaystyle{ e_{2 \rightarrow 1} }[/math]延伸到子节点的树状结构。非回溯拓展分支（NBEB）通常具有无限性，由于从子节点继续不断地延伸的递归过程。

对于给定的正整数k，定义[math]\displaystyle{ Y_n }[/math]为满足以下条件的非回溯扩展分支(NBEB)集合：存在一个包含根节点的NBEB子分支，且在该子分支的前n代中，每个顶点的子顶点数量均不少于k-1。并且定义[math]\displaystyle{ Y_0 }[/math]为所有NBEB的集合。显然[math]\displaystyle{ Y_0 \supset Y_1 \supset … Y_n \supset Y_{n+1} \supset … \supset Y_{\infty} }[/math]。例如，图中NBEB [math]\displaystyle{ B_{2 \rightarrow 1} }[/math]在k=3时属于[math]\displaystyle{ Y_1 }[/math]，在k=2时属于[math]\displaystyle{ Y_{\infty} }[/math]

NBEB示意图

在这基础上可以得到以下两个基本定理： (1)NBEB [math]\displaystyle{ B_{\alpha \rightarrow \beta} }[/math]属于[math]\displaystyle{ Y_n }[/math]当且仅当[math]\displaystyle{ B(S_{\alpha}) }[/math]包含至少k-1个NBEB属于[math]\displaystyle{ Y_{n-1} }[/math] (2)节点[math]\displaystyle{ v_{\alpha} }[/math]在n步剪枝过程后保留当且仅当[math]\displaystyle{ B(S_{\alpha}) }[/math]包括至少k个NBEB属于[math]\displaystyle{ Y_{n-1} }[/math]

假设[math]\displaystyle{ y_n }[/math]表示一个随机选择的NBEB属于[math]\displaystyle{ Y_n }[/math]的概率，显示[math]\displaystyle{ y_0 = 1 }[/math]。我们可以得出关于[math]\displaystyle{ y_n }[/math]的递推关系如下：
[math]\displaystyle{ y_n = \sum^{\infty}_{j=k-1}q_j \sum^j_{m=k-1}(^j_m)y^m_{n-1}(1-y_{n-1})^{j-m} }[/math]
[math]\displaystyle{ = \sum^{\infty}_{m=k-1} \frac {y_{n-1}^m}{m!} \sum^{\infty}_{j=m} \frac {j!}{(j-m)!}q_j{(1-y_{n-1})}^{j-m} }[/math]
[math]\displaystyle{ = \sum^{\infty}_{m=k-1} \frac {y_{n-1}^m}{m!}·G_1^{(m)} (1-y_{n-1}) }[/math]
[math]\displaystyle{ = 1 - \sum_{m=0}^{k-2} \frac {y_{n-1}^m}{m!}·G_1^{(m)}(1-y_{n-1}) }[/math]
[math]\displaystyle{ = f(y_{n-1}) }[/math]
这里[math]\displaystyle{ q_j }[/math]表示余度分布，[math]\displaystyle{ G_1(z) = \sum_{j=0}^{\infty}q_jz^j }[/math]表示余度分布的生成函数[math]\displaystyle{ G^{(j)}(z) }[/math]表示G(z)的j阶导数
经过n步剪枝过后剩下的子图大小可以的递推关系如下
[math]\displaystyle{ r_n = \sum^{\infty}_{j=k}p_j \sum^j_{m=k}(^j_m)y^m_{n-1}(1-y_{n-1})^{j-m} }[/math]
[math]\displaystyle{ = \sum^{\infty}_{m=k} \frac {y_{n-1}^m}{m!} \sum^{\infty}_{j=m} \frac {j!}{(j-m)!}p_j{(1-y_{n-1})}^{j-m} }[/math]
[math]\displaystyle{ = 1 - \sum_{m=0}^{k-1} \frac {y_{n-1}^m}{m!}·G_0^{(m)}(1-y_{n-1}) }[/math]
[math]\displaystyle{ = g(y_{n-1}) }[/math]
这里[math]\displaystyle{ p_j }[/math]表示度分布，[math]\displaystyle{ G_0(z) = \sum_{j=0}^{\infty}p_jz^j }[/math]表示度分布的生成函数
基于以上推导，{[math]\displaystyle{ y_n }[/math]}是一个递减序列，并且[math]\displaystyle{ y_n \ge 0 }[/math]，因此[math]\displaystyle{ y = lim_{n \rightarrow \infty}y_n }[/math],得到以下方程：
[math]\displaystyle{ y=f(y)=1 - \sum_{m=0}^{k-2} \frac {y^m}{m!}·G_1^{(m)}(1-y) }[/math]
下图表示基于以上关系得到的ER网络上最大k-core的变化情况：当k=2时是连续变化，[math]\displaystyle{ k \ge 3 }[/math]时是非连续变化

ER网络的k-core变化

Wu et al. [25]指出非回溯扩展分支（NBEB）方法能够处理度相关网络，并且通过在多种网络上的数值模拟验证了其结果的正确性。在此基础上，Wu et al. [33]进一步拓展了NBEB方法，不仅解决了多层网络中的k核剪枝过程问题，还提出了"多色非回溯扩展分支"（MNEB）算法。该方法可分析从最简单的非关联多层网络，到同时存在层内与层间关联的最复杂情况。
用[math]\displaystyle{ e_{jl} }[/math]表示一条边的两个端点分别具有剩余度 j 和 l 的概率，[math]\displaystyle{ \sum^{\infty}_{l=0} = q_j }[/math]，在不相关网络中，[math]\displaystyle{ e_{jl} = q_j * q_l }[/math]，不相关网络中的递推关系可以修改为如下：
[math]\displaystyle{ q_l * y_{n,l} = \sum^{\infty}_{j=k-1}e_{lj}\sum^l_{m=k-1}(^j_m)y^m_{n-1,j}*{(1-y_{n-1,j})^{j-m}} }[/math]
[math]\displaystyle{ r_n = \sum^{\infty}_{j=k}p_j \sum^j_{m=k}(^j_m)y^m_{n-1}(1-y_{n-1})^{j-m} }[/math]