概述
K 核子图(k-Core)算法可以计算出由一张图的所有核心度不小于 k 的节点构成的子图。K 核子图算法常用来识别和提取图中的紧密连通群组,以便做进一步分析,因具有较低的时间复杂度(线性)及较好的直观可解释性,广泛应用于金融风控、社交网络和生物学等研究领域。
基本概念
K 核子图
一张图的 K 核子图是指从图中反复去掉度(不考虑自环边)小于 k 的节点之后得到的子图。该计算过程是一个反复迭代剪枝的过程,在某一轮剪枝之前度大于等于 k 的节点,可能会在该轮剪枝后变为度小于 k。
注意:在 K 核子图的计算中考虑节点度时,自环边无任何贡献。
上面左起第一图中,所有节点的度的最小值为 1,故该图为其自身的 1 核子图;为了得到该图的 2 核子图,先去掉图中度为 1 的节点 1
、6
、7
,得到中间的子图。由于节点 6
、7
已经被去掉,此时节点 4
的度边为 1,需要继续去掉节点 4
,即得到右面的子图;此时所剩节点 2
、3
、5
的度均为 2,故原图的 2 核子图包含节点 2
、3
、5
。
核心度
如果一个节点属于其所在图的 K 核子图,但不属于 K+1 核子图,则称该节点的核心度(或核数 Coreness)为 k。
在之前的例子中,1-Core 包含节点 [1,2,3,4,5,6,7],2-Core 包含节点 [2,3,5],3-Core 为空集,故核心度为 1 的节点有 [1,4,6,7],核心度为 2 的节点有 [2,3,5]。
特殊处理
孤点、不连通图
孤点不与任何其他节点相连,孤点的度在 K 核子图的计算中被判定为 0。
图的连通性不影响 K 核子图的计算,原先连通的图在 K 核子图的求解过程中可能会变为不连通。
自环边
自环边不参与 K 核子图的计算。
有向边
对于有向边,本算法会忽略边的方向,按照无向边进行计算。
结果和统计值
以下面的图为例,运行 K 核子图算法:
算法结果:当 k=3 时,返回构成 3 核子图的点列表
[4]
[5]
[6]
[7]
算法统计值:无
命令和参数配置
- 命令:
algo(k_core)
params()
参数配置项如下:
名称 | 类型 | 默认值 | 规范 | 描述 |
---|---|---|---|---|
k | int | / | >0,必填 | 核心度 K |
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename | _id |
示例:计算 3 核子图,将算法结果回写至名为 3-core 的文件
algo(k_core).params({
k:3
}).write({
file:{
filename: "3-core"
}
})
2. 属性回写
算法不支持属性回写。
3. 统计回写
算法不支持统计回写。
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 构成 k-Core 的节点 | _uuid |
示例:计算 2 核子图,将算法结果定义为别名 k2 返回
algo(k_core).params({
k:2
}) as k2
return k2
流式返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 构成 k-Core 的节点 | _uuid |
示例:计算 2 核子图,将算法结果定义为别名 k2,返回构成 2 核子图的点数量
algo(k_core).params({
k:2
}).stream() as k2
return count(k2)
实时统计
算法无统计值。