概述
节点度(Degree)算法为每个节点计算与其相连的边的数量;当边上有权重时,则计算权重的总和。节点度是面向节点的浅层(≤ 1层)计算,是一种最简单、最高效的图算法,在科学计算、特征提取、超级节点识别等领域扮演着至关重要的角色。
基本概念
度的方向
节点的出边的数量称为节点的出度,节点的入边的数量称为节点的入度。如果忽略边的方向计算所有边的数量,就得到节点的度(或度中心性)。
上图中红色节点的出度为 3
,入度为 4
,度为 7
。需要注意的是,有向的自环边会被看作一条出边和一条入边。
边权重
边权重可以是边的某一个属性值。指定了边权重时,节点度就是边权重的和;不指定边权重时,节点度也可以理解为所有边的权重均为 1 时的节点度。
边加权后,上图中红色节点的出度为 1 + 0.2 + 2 = 3.2
,入度为 0.5 + 0.3 + 2 + 1 = 3.8
,度中心性为 3.2 + 3.8 = 7
。
特殊处理
孤点、不连通图
由于没有连接其他节点的边,孤点的节点度完全取决于其自环边。
自环边
自环边会被看作一条出边和一条入边。
有向边
有向边的方向是计算节点出度和入度的依据;计算度中心性时则会忽略边的方向。
结果和统计值
以下面包含 8 人的小型社交网络为例,点代表用户,边代表关注关系,边上的权重值来自属性 score:
算法结果:为每个点计算加权度,根据算法执行方式,返回 _id
、degree
两列或 _uuid
、degree
两列
_uuid | _id | degree |
---|---|---|
1 | Mike | 4.9 |
2 | Cathy | 6.5 |
3 | Anna | 11.1 |
4 | Joe | 6.1 |
5 | Sam | 4.3 |
6 | Bob | 5.2 |
7 | Bill | 2.3 |
8 | Tim | 0 |
算法统计值:度数和 total_degree
以及平均度数 average_degree
total_degree | average_degree |
---|---|
40.4 | 5.05 |
命令和参数配置
- 命令:
algo(degree)
params()
参数配置项如下:
名称 | 类型 | 默认值 |
规范 |
描述 |
---|---|---|---|---|
ids 或 uuids | []_id 或 []_uuid |
/ | / | 待计算节点的 ID / UUID;忽略则计算全部点 |
edge_schema_property | []@<schema>?.<property> |
/ | 数值类的边属性;需 LTE;是否携带 schema 均可 | 边权重所在的一个或多个属性名称,无该属性的边不参与计算;忽略则不加权 |
direction | string | / | in/out,大小写不敏感 | 边的方向;忽略则忽略方向 |
limit | int | -1 | >=-1 | 返回的结果条数,-1 表示返回所有结果 |
order | string | / | ASC/DESC,大小写不敏感 | 对返回结果进行排序;忽略则不排序 |
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename | _id ,degree |
示例:计算所有点的度,将算法结果回写至文件
algo(degree).params().write({
file:{
filename: "degree_all"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | degree |
点属性 | 未加权时,为 int64 ;加权时,为 int64 或 double |
示例:计算所有点的加权度,将计算结果回写至点属性
algo(degree).params({
edge_schema_property: @follow.score
}).write({
db:{
property: "degree"
}
})
3. 统计回写
统计项名称 | 数据类型 | 描述 |
---|---|---|
total_degree |
float | 度总和 |
average_degree |
float | 度平均值 |
示例:计算所有点的度,将算法统计值回写至任务信息
algo(degree).params().write()
直接返回
别名序号 |
类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其度 | _uuid , degree |
1 | KV | 度总和、度平均值 | total_degree , average_degree |
示例:计算所有点的加权度,分别返回算法结果和统计值,并将算法结果降序排列
algo(degree).params({
edge_schema_property: @follow.score,
order: "desc"
}) as results, stats
return results, stats
流式返回
别名序号 |
类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其度 | _uuid , degree |
示例:找到图中度最大的节点的一步邻居,返回这些邻居节点的详细信息
algo(degree).params({
order: "desc",
limit: 1
}).stream() as results
khop().src({_uuid == results._uuid}).depth(1) as neighbors
return neighbors{*}
实时统计
别名序号 |
类型 | 描述 | 列名 |
---|---|---|---|
0 | KV | 度总和、度平均值 | total_degree ,average_degree |
示例:计算所有点的出度,返回算法统计值
algo(degree).params({
direction: "out"
}).stats() as stats
return stats