281
个编辑
更改
跳到导航
跳到搜索
第2行：
第2行： − − − − − − − − 第32行：
第24行： − − − + − 1987年, Luczak [15]首次从理论上研究 k-core 问题，关于随机网络G(n, p)中 k-core 的大小得出了以下三个定理： 第64行：
第53行： − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→相关网络k-core分解过程
普遍认为k-core概念由Seidman[^1] [12]首次提出，对于给定的网络，递归删除网络中度数小于k的节点可以得到网络的极大子图，其中每个节点的度数不小于k（不考虑子图外的连接情况），该子图为原网络的k-core。与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-shell：属于k-core，但不属于(k+1)-core的点集，通过k-core分解过程可以将网络根据k-shell进行分层。
:* k-crust：从1到k的k-shell的并集，代表网络的外围结构
:* k-crust：从1到k的k-shell的并集，代表网络的外围结构
:* k-corona：k-core中度数恰好为k的节点组成的点集
:* k-corona：k-core中度数恰好为k的节点组成的点集
:* coreness：一个节点如果属于k-shell, 该节点的coreness为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的研究中，人们注意到了k-core剪枝过程的临界性。剪枝过程的结果只有两种，要么网络消失，没有节点在剪枝过程中保留下来；要么无法进一步去除节点，网络最终拥有一个固定大小的 k-core。k-core修剪过程是少数几个详细介绍精确临界行为并用解析法求解的例子之一。k-core修剪过程的解析解为研究临界现象提供了新的见解，吸引了众多科学家。并且，由于k-core 分解能够简单高效地找到网络的核心结构，k-core及相关的概念包括（k-shell、coreness）被广泛应用于多个科学领域，包括 生物学、生态学、计算机科学、信息传播、地质学 等等。
[[文件:K-core和coreness示意图.png|缩略图|k-core和coreness示意图]]
[[文件:K-core和coreness示意图.png|缩略图|k-core和coreness示意图]]
== k-core分解的算法实现 ==
== k-core分解的算法实现 ==
剪枝过程（pruning process）是常用的寻找该极大子图的k-core分解算法，通过递归删除网络中度小于k的节点实现。论文[^4]提出了复杂度为O(m)（ m为网络中边的数量）的高效计算每个节点coreness的方法（k-core即为coreness不小于k的节点构成的子图）。算法的思想简单描述为：从度最小的节点开始，检查每个邻居节点的度，如果邻居节点的度更大，则将这条边移除并更新该节点的度，选择下一个度最小的节点重复以上过程。每个节点的coreness为节点最终的度。该算法需要检查网络中的每一条边，因此算法复杂度为O(m)。
剪枝过程（pruning process）是常用的寻找该极大子图的k-core分解算法，通过递归删除网络中度小于k的节点实现。论文[^4]提出了复杂度为O(m)（ m为网络中边的数量）的高效计算每个节点coreness的方法（k-core即为coreness不小于k的节点构成的子图）。算法的思想简单描述为：从度最小的节点开始，检查每个邻居节点的度，如果邻居节点的度更大，则将这条边移除并更新该节点的度，选择下一个度最小的节点重复以上过程。每个节点的coreness为节点最终的度。该算法需要检查网络中的每一条边，因此算法复杂度为O(m)。
具体算法描述如下: </br>
具体算法描述如下: </br>
INPUT: graph G = (V, L) represented by lists of neighbors </br>
INPUT: graph G = (V, L) represented by lists of neighbors </br>
:::end</br>
:::end</br>
::::end;</br>
::::end;</br>
python库networkx基于该算法实现了计算网络的k-core的函数和每个节点coreness的函数：
python库networkx基于该算法实现了计算网络的k-core的函数和每个节点coreness的函数：
:* netwokx.k_core(G,k)获取网络G的k-core
:* netwokx.k_core(G,k)获取网络G的k-core
:* netwokx.core_number(G) 获取网络G每个节点的coreness
:* netwokx.core_number(G) 获取网络G每个节点的coreness
== k-core分解的理论研究 ==
== k-core分解的理论研究 ==
=== 无关网络k-core分解的特征 ===
=== 无关网络k-core分解的特征 ===
对于k-core的理论研究主要关注k-core的临界性。经过剪枝过程网络可能完全消失没有节点保留，也有可能留下一个一定大小的k-core无法进一步的移除节点。k-core分解过程的临界点，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表示网络平均度）
（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的概率成立
:* 定理1：如果k > 3, v(k, n, p) = 0 或者 v(k, n, p) > 0.0002n 当 n → ∞ 以接近1的概率成立
=== 无关网络k-core分解过程 ===
=== 无关网络k-core分解过程 ===
S. N. Dorogovtsev [22]推导出了描述任意度分布的受损的随机不相关网络中 k-core 结构的精确方程。这一结果可以计算各种受损或未受损的随机网络中 k-core 的大小及其其他结构特征，并揭示复杂网络中 k-core 渗流的本质。
S. N. Dorogovtsev [22]推导出了描述任意度分布的受损的随机不相关网络中 k-core 结构的精确方程。这一结果可以计算各种受损或未受损的随机网络中 k-core 的大小及其其他结构特征，并揭示复杂网络中 k-core 渗流的本质。</br>
对于一个无关网络（根据度分布由配置模型生成），考虑到无限稀疏的配置模型的树状结构特点，可以发现其k核与无限（k−1）叉子树（每个子节点至少有k-1个子代）完全重合。
P(q)为度分布,Q=1-p表示网络中随机移除的节点的比例。</br>
设R为网络中某条边的一端不是无限（k-1）叉子树根节点的概率，那么一个节点属于k-core的概率</br>
<math>M(k)=p\sum_{q \ge k}P(q)\sum _{n=k}^{q}C_n^q R^(q-n) (1-R)^n </math></br>
如果某条边的某一端至多有k−2 个子分支是无限(k−1) 叉子树的根节点，那么该端本身就不能成为无限(k−1) 叉子树的根节点。这一关系导出了关于R的方程：</br>
<math>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></br>
对于这个方程的解释如下：
:* 第一项，1-p=Q表示网络中边的一端被移除的概率，对于未受损的网络方程中的p=1
:* 第二项中 <math>C_n^i R^{i-n}(1-R)^n] </math>是边的一段具有i个子节点并且其中有n个是k-1叉树根节点的概率
:* 第二项中 <math>\frac {(i+1)P(i+1)}{z_1} </math> 随机选择的一条边连接到具有i个分支的顶点的概率
:* 第二项中 <math>z_1 = \sum_q qP(q) </math> 一个顶点的平均邻居数量
对于k-core的度分布表示如下：
<math>
P_k(q) = \frac {p}{M(k)} \sum_{q' \ge q}P(q')C_q^{q'}R^{q'-q}(1-R)^q
</math></br>
k-core的平均度可以表示为<math>z_1(k) = \sum_{q \ge k}P_k(q)q</math> </br>
属于k-core但不属于k+1-core的节点，即k-shell的大小可以表示为 <math>S(k) = M(k)-M(k+1) </math>
=== 相关网络k-core分解过程 ===
=== 相关网络k-core分解过程 ===
Shi et al. [24]使用基于非回溯拓展分支（NBEB-NonBacktracking Expansion Branch）的方法给出了k-core大小的精确解析解，首次揭示了k核剪枝过程中临界现象的精确行为特征。。他们的研究表明Baxter等人[20]提出的四个方程简化为单变量迭代形式，且k核剪枝过程能够完美映射至该迭代。论文中推导出了这一迭代的通用表达式。只要给定初始状态，便可计算出单变量迭代的每个中间状态，从而精确对应k核剪枝过程的每个阶段。特别地，对于随机生成的不相关网络，该理论能准确解析出剪枝过程中任意中间阶段所剩k核的规模与结构特征。数值模拟结果进一步验证了理论分析的正确性。
用e表示边，v表示点，<math>\alpha和\beta</math>表示节点下标，j、l、m表示节点的度，<math>e_{2 \rightarrow 1}</math>表示从节点<math>v_2 到 v_1</math>的有向边，用<math>S_1</math>表示从v1到其每个邻居节点的有向边集合，<math>S_{2 \rightarrow 1}</math>表示所有在<math>S_1</math>除了<math>e_{1 \rightarrow 2}</math>的边。定义NBEB <math> B_{2 \rightarrow 1}</math>为从根边<math>e_{2 \rightarrow 1}</math>延伸到子节点的树状结构。从子节点继续不断地延伸是一个递归过程，非回溯拓展分支（NBEB）通常具有无限性。
对于给定的正整数k，定义<math>Y_n</math>为满足以下条件的非回溯扩展分支(NBEB)集合：存在一个包含根节点的NBEB子分支，且在该子分支的前n代中，每个顶点的子顶点数量均不少于k-1。并且定义<math>Y_0</math>为所有NBEB的集合。显然<math>Y_0 \in Y_1 \in … Y_n \in Y_{n+1} \in … \in Y_{\infty} </math>。例如，图中NBEB <math>B_{2 \rightarrow 1}</math>在k=3时属于<math>Y_1</math>，在k=2时属于<math>Y_{\infty}</math>
[[文件:NBEB示意图.jpg|缩略图]]
在这基础上可以得到以下两个基本定理：
(1)NBEB <math>B_{\alpha \rightarrow \beta}</math>属于<math>Y_n</math>当且仅当<math>B(S_{\alpha})</math>包含至少k-1个NBEB属于<math>Y_{n-1}</math>
(2)节点<math>v_{\alpha}</math>在n步剪枝过程后保留当且仅当<math>B(S_{\alpha})</math>包括至少k个NBEB属于<math>Y_{n-1}</math>
假设<math>y_n</math>表示一个随机选择的NBEB属于<math>Y_n</math>的概率，显示<math>y_0 = 1</math>。我们可以得出关于<math>y_n</math>的递推关系如下：</br>
<math>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></br>
<math>= \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></br>
<math>= \sum^{\infty}_{m=k-1} \frac {y_{n-1}^m}{m!}·G_1^{(m)} (1-y_{n-1})</math></br>
<math>= 1 - \sum_{m=0}^{k-2} \frac {y_{n-1}^m}{m!}·G_1^{(m)}(1-y_{n-1}) </math></br>
<math>= f(y_{n-1})</math></br>
这里<math>q_j</math>表示余度分布，<math>G_1(z) = \sum_{j=0}^{\infty}q_jz^j</math>表示余度分布的生成函数<math>G^{(j)}(z)</math>表示G(z)的j阶导数</br>
经过n步剪枝过后剩下的子图大小可以的递推关系如下</br>
<math>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></br>
<math>= \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></br>
<math>= 1 - \sum_{m=0}^{k-1} \frac {y_{n-1}^m}{m!}·G_0^{(m)}(1-y_{n-1}) </math></br>
<math>= g(y_{n-1})</math></br>
这里<math>p_j</math>表示度分布，<math>G_0(z) = \sum_{j=0}^{\infty}p_jz^j</math>表示度分布的生成函数</br>
基于以上推导，{<math>y_n</math>}是一个递减序列，并且<math>y_n \ge 0</math>，因此<math>y = lim_{n \rightarrow \infty}y_n</math>,得到以下方程：</br>
<math>y=f(y)=1 - \sum_{m=0}^{k-2} \frac {y^m}{m!}·G_1^{(m)}(1-y)</math></br>
下图表示基于以上关系得到的ER网络上最大k-core的变化情况：当k=2时是连续变化，<math>k \ge 3</math>时是非连续变化</br>
[[文件:ER网络的kcore相变.png|缩略图|ER网络的k-core相变]]
Wu et al. [25]发现非回溯扩展分支（NBEB）方法能够处理度相关网络，并且通过在多种网络上的数值模拟验证了其结果的正确性。在此基础上，Wu et al. [33]进一步拓展了NBEB方法，不仅解决了多层网络中的k核剪枝过程问题，还提出了"多色非回溯扩展分支"（MNEB）算法。该方法可分析从最简单的非关联多层网络，到同时存在层内与层间关联的最复杂情况。</br>
用<math>e_{jl}</math>表示一条边的两个端点分别具有剩余度 j 和 l 的概率，<math>\sum^{\infty}_{l=0} = q_j</math>，在无关网络中，<math>e_{jl} = q_j * q_l</math>，可以得到如下递推关系：</br>
<math>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></br>
<math>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></br>