K-core

定义

普遍认为k-core概念由Seidman[^1] [12]首次提出，对于给定的网络，递归删除网络中度数小于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的节点实现。论文[^4]提出了复杂度为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 [15]首次从理论上研究 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 \ne 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⟩是高于、等于还是低于该阈值，系统表现出三种不同的行为：

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

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

第三，当低于阈值时，系统会经历一个持续时间较长的瞬态过程（即“plateau”阶段）,该过程最终会以网络整体崩溃结束，即整个网络结构的消失。

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

无关网络k-core分解过程

S. N. Dorogovtsev [22]推导出了描述任意度分布的受损的随机不相关网络中 k-core 结构的精确方程。这一结果可以计算各种受损或未受损的随机网络中 k-core 的大小及其其他结构特征，并揭示复杂网络中 k-core 渗流的本质。