概述
度中心性(Degree Centrality)算法用于衡量网络中节点的重要性,它计算与每个节点相连的入边和/或出边的数量,或边上的权重和。节点度是面向节点一层邻域的计算,是一种最简单、高效的图算法,在科学计算、特征提取、超级节点识别等领域扮演着至关重要的角色。
基本概念
入度和出度
节点的入边数量称为节点的入度(In-degree),出边数量则称为出度(Out-degree),如果忽略边的方向计算所有边的数量,就得到节点的度。
![](https://img.ultipa.cn/draw/draw_c79beb875cd64cdfa0e3cb4647110abb.jpg?v='1642759847524')
上图中红色节点的入度为4,出度为3,度为7。需要注意的是,有向自环边被视为一条出边和一条入边。
加权度
在很多应用中,图中的边会与一个数字相关联,称为权重(Weight)。在加权图中,一个节点的加权度(Weighted Degree)是指其所有邻边的权重和。不指定边权重时,节点度也可以理解为所有边的权重均为1时的度。
![](https://img.ultipa.cn/draw/draw_bd6ced106a164be3865f9a21d578ede7.jpg?v='1642759974332')
在这个加权图中,红色节点的加权入度为0.5 + 0.3 + 2 + 1 = 3.8
,加权出度为1 + 0.2 + 2 = 3.2
,加权度为3.2 + 3.8 = 7
。
特殊说明
- 孤点的节点度完全取决于其自环边,没有自环边的孤点的度为0。
- 每条自环边为节点贡献的度数2,有向自环边被视为一条入边和一条出边。
语法
- 命令:
algo(degree)
- 参数:
名称 | 类型 | 规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
ids / uuids | []_id / []_uuid |
/ | / | 是 | 待计算节点的ID/UUID,忽略则计算全部点 |
edge_schema_property | []@<schema>?.<property> |
数值类型,需LTE | / | 是 | 计算加权度时,用作边权重的属性,权重值为所有指定属性值的和 |
direction | string | in , out |
/ | 是 | in 计算入度,out 计算出度 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
order | string | asc , desc |
/ | 是 | 按度大小对结果进行排序 |
示例
示例是一个社交网络,边属性@follow.score的值可用作权重:
![](https://img.ultipa.cn/draw/draw_8b86fa9e21e145d181c9d11dbcb59081.jpg?v='1680579330133')
文件回写
配置项 | 回写内容 |
---|---|
filename | _id ,degree |
algo(degree).params().write({
file:{
filename: 'degree_all'
}
})
统计值:total_degree = 20, average_degree = 2.25
结果:文件degree_all
Tim,0
Bill,1
Bob,2
Sam,2
Joe,3
Anna,5
Cathy,4
Mike,3
属性回写
配置项 | 回写内容 | 回写至 | 数据类型 |
---|---|---|---|
property | degree |
点属性 | double |
algo(degree).params({
edge_schema_property: '@follow.score'
}).write({
db:{
property: 'degree'
}
})
统计值:total_degree = 40.4, average_degree = 5.05
结果:每个节点的度回写至名为degree的点属性下
直接返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其度 | _uuid , degree |
1 | KV | 度总和、度平均值 | total_degree , average_degree |
algo(degree).params({
edge_schema_property: '@follow.score',
order: 'desc'
}) as degree, stats
return degree, stats
结果:degree和stats
_uuid | degree |
---|---|
3 | 11.1 |
2 | 6.5 |
4 | 6.1 |
6 | 5.2 |
1 | 4.9 |
5 | 4.3 |
7 | 2.3 |
8 | 0 |
total_degree | average_degree |
---|---|
40.4 | 5.05 |
流式返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
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{*}
结果:neighbors
_id | _uuid |
---|---|
Bill | 7 |
Sam | 5 |
Joe | 4 |
Cathy | 2 |
Mike | 1 |
统计返回
别名序号 | 类型 | 描述 |
列名 |
---|---|---|---|
0 | KV | 度总和、度平均值 | total_degree ,average_degree |
algo(degree).params({
direction: 'out'
}).stats() as stats
return stats
结果:stats
total_degree | average_degree |
---|---|
10 | 1.25 |