概述
中介中心性（Betweenness Centrality）衡量节点处于其它任意两点间最短路径之中的概率。该概念由Linton C. Freeman于1977年提出，能有效地计算出在图的多个部分间起桥梁或媒介作用的点。
中介中心性的取值范围是0到1，节点的分值越大，对于网络流通性或连通性的影响力越大。
相关资料如下：
- L.C. Freeman, A Set of Measures of Centrality Based on Betweenness (1977)
- L.C. Freeman, Centrality in Social Networks Conceptual Clarification (1978)
基本概念
最短路径
在连通图中，两点间的最短路径（Shortest Path）是指经过的边数最少（非权重图）或所有边的权重和最小（权重图）的路径。
在上面的非权重图中，红、绿两点间存在三条最短路径，其中有两条经过黄色节点，因此，黄色节点对于红绿节点对的中介概率为2 / 3 = 0.6667。
中介中心性
在本算法中，节点的中介中心性分值计算公式为：
其中，x为待计算的目标节点，i、j为图中互异的任意两个节点（不包含x），σ为ij点对最短路径的数量，σ(x)为ij点对经过x的最短路径的数量，σ(x)/σ就是x对于ij点对的中介概率（i、j不连通时该概率为0），k为图中节点的数量，(k-1)(k-2)/2为ij节对的数量。
计算上图中红色节点的中介中心性。图中共有5个节点，除了红色节点有(5-1)(5-2)/2 = 6组点对，红色节点对于各节点对的中介概率分别为0、1/2、2/2、0、2/3和0，因此其中介中心性分值为(0 + 1/2 + 2/2 + 0 + 2/3 + 0) / 6 = 0.3611。
中介中心性算法会消耗很多计算资源。在一个有V个节点的图中，建议当V>10000时通过采样进行近似计算，推荐的采样个数是节点数以10为底的对数（
log(V)）。
每次执行算法时，只进行一次采样，每个节点的中心性分值是所有样本节点间的最短路径计算的。
特殊说明
- 孤点的中介中心性分值为0。
- 中介中心性算法忽略边的方向，按照无向边进行计算。在包含
k个节点的无向图中，参与计算的点对数量是(k-1)(k-2)/2。
示例图集
创建示例图集：
// 在空图集中逐行运行以下语句
create().node_schema("user").edge_schema("know")
insert().into(@user).nodes([{_id:"Sue"}, {_id:"Dave"}, {_id:"Ann"}, {_id:"Mark"}, {_id:"May"}, {_id:"Jay"}, {_id:"Billy"}])
insert().into(@know).edges([{_from:"Dave", _to:"Sue"}, {_from:"Dave", _to:"Ann"}, {_from:"Mark", _to:"Dave"}, {_from:"May", _to:"Mark"}, {_from:"May", _to:"Jay"}, {_from:"Jay", _to:"Ann"}])
在HDC图集上运行算法
创建HDC图集
将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_betweenness：
CALL hdc.graph.create("hdc-server-1", "hdc_betweenness", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
})
hdc.graph.create("hdc_betweenness", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true,
update: "static",
query: "query",
default: false
}).to("hdc-server-1")
参数
算法名：betweenness_centrality
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
sample_size |
Integer | -1, -2, [1, |V|] |
-2 |
是 | 指定采样策略；设置为-1时，采样log(|V|)个点；设置为[1, |V|]区间内的一个数字，采样指定数量的点（|V|是图中总点数）；设置为-2时，不进行采样。该选项仅当所有点参与计算时生效 |
return_id_uuid |
String | uuid, id, both |
uuid |
是 | 在结果中使用_uuid、_id或同时使用两者来表示点 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据betweenness_centrality分值对结果排序 |
文件回写
CALL algo.betweenness_centrality.write("hdc_betweenness", {
params: {
return_id_uuid: "id"
},
return_params: {
file: {
filename: "betweenness_centrality"
}
}
})
algo(betweenness_centrality).params({
project: "hdc_betweenness",
return_id_uuid: "id"
}).write({
file: {
filename: "betweenness_centrality"
}
})
结果：
_id,betweenness_centrality
Mark,0.133333
Jay,0.0666667
Ann,0.133333
Sue,0
Dave,0.333333
Billy,0
May,0.0666667
数据库回写
将结果中的betweenness_centrality值写入指定点属性。该属性类型为float。
CALL algo.betweenness_centrality.write("hdc_betweenness", {
params: {},
return_params: {
db: {
property: 'bc'
}
}
})
algo(betweenness_centrality).params({
project: "hdc_betweenness"
}).write({
db:{
property: 'bc'
}
})
完整返回
CALL algo.betweenness_centrality("hdc_betweenness", {
params: {
return_id_uuid: "id",
order: "desc",
limit: 3
},
return_params: {}
}) YIELD bc
RETURN bc
exec{
algo(betweenness_centrality).params({
return_id_uuid: "id",
order: "desc",
limit: 3
}) as bc
return bc
} on hdc_betweenness
结果：
| _id | betweenness_centrality |
|---|---|
| Dave | 0.333333 |
| Ann | 0.133333 |
| Mark | 0.133333 |
流式返回
CALL algo.betweenness_centrality("hdc_betweenness", {
params: {
return_id_uuid: "id"
},
return_params: {
stream: {}
}
}) YIELD r
FILTER r.betweenness_centrality = 0
RETURN count(r)
exec{
algo(betweenness_centrality).params({
return_id_uuid: "id"
}).stream() as r
where r.betweenness_centrality == 0
return count(r)
} on hdc_betweenness
结果：2
在分布式投影上运行算法
创建分布式投影
将图集全部投影到shard服务器上并命名为dist_betweenness：
create().projection("dist_betweenness", {
nodes: {"*": ["*"]},
edges: {"*": ["*"]},
direction: "undirected",
load_id: true
})
参数
算法名：betweenness_centrality
参数名 |
类型 |
规范 |
默认值 |
可选 |
描述 |
|---|---|---|---|---|---|
sample_rate |
Float | (0, 1] | / | 是 | 指定用于计算的节点采样比例 |
limit |
Integer | ≥-1 | -1 |
是 | 限制返回的结果数；-1返回所有结果 |
order |
String | asc, desc |
/ | 是 | 根据betweenness_centrality分值对结果排序 |
文件回写
CALL algo.betweenness_centrality.write("dist_betweenness", {
params: {},
return_params: {
file: {
filename: "betweenness_centrality"
}
}
})
algo(betweenness_centrality).params({
project: "dist_betweenness"
}).write({
file: {
filename: "betweenness_centrality"
}
})
结果：
_id,betweenness_centrality
Mark,0.133333
Jay,0.0666667
Ann,0.133333
Sue,0
Dave,0.333333
Billy,0
May,0.0666667
数据库回写
将结果中的betweenness_centrality值写入指定点属性。该属性类型为double。
CALL algo.betweenness_centrality.write("dist_betweenness", {
params: {},
return_params: {
db: {
property: 'bc'
}
}
})
algo(betweenness_centrality).params({
project: "dist_betweenness"
}).write({
db:{
property: 'bc'
}
})