中介中心性¶
本文介绍中介中心性算法，并演示如何用 GQL 实现该算法。
算法介绍¶
中介中心性衡量点位于其他点最短路径上的频繁程度。
该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。
更多信息，请参见中介中心性。
数据模型¶
为了在 GQL 中实现中介中心性算法，使用以下数据模型创建图类型：
- 实体由类型为
Node的点表示，点属性包括id和rating。 - 实体间关系由类型为
Link的边表示，边属性包括weight。
该图类型的完整定义，请参见准备图数据。
过程实现¶
为了计算中介中心性结果，创建一个过程。
关于该过程的更多信息，请参见过程实现。下文将介绍该过程的关键组成部分及其工作原理。
该过程接受以下输入参数：
- 该过程不需要输入参数。
此外，在过程内部定义了以下变量：
| 变量名 | 变量类型 | 描述 |
|---|---|---|
frontier |
原始值变量 | 当前 BFS 层的活跃点集合。 |
source_ids |
全局 SumAgg 聚合值变量 | 用于多源 BFS 的所有点 ID 列表。 |
has_next |
原始值变量 | 当前源点的 BFS 层是否仍有待扩展点。 |
inf |
原始值变量 | 未初始化距离的无穷大哨兵值。 |
source_id |
原始值变量 | 外层 BFS 循环中当前处理的源点 ID。 |
src_idx |
原始值变量 | 外层循环在 source_ids 列表中的当前索引。 |
level |
原始值变量 | 从当前源点出发的 BFS 跳数深度。 |
max_level |
原始值变量 | 当前源点 BFS 达到的最大深度。 |
rev_level |
原始值变量 | 回溯阶段的逆向层级计数。 |
bc |
点绑定 SumAgg 聚合值变量 | 每个点的中介中心性累积得分。 |
dist |
点绑定 SumAgg 聚合值变量 | 从当前源点到每个点的最短跳数距离。 |
sigma |
点绑定 SumAgg 聚合值变量 | 从当前源出发到每个点的最短路径数量。 |
delta |
点绑定 SumAgg 聚合值变量 | 回溯阶段累积的每点依赖分数。 |
result_table |
表变量 | 存储 (vertex_id, score) 结果对的输出表。 |
以下步骤概述了该过程的逻辑：
- 将所有点 ID 收集到
source_ids，初始化每点的dist、sigma和delta。 - 对每个源点执行 BFS，计算最短路径跳数（
dist）和路径数量（sigma）。 - 从最深 BFS 层向源回溯，累积每点的依赖分数（
delta）到中介中心性得分（bc）。 - 返回每个点的中介中心性得分（
vertex_id、score），按分数降序排列。
操作步骤¶
在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。
1. 准备图数据¶
-
创建一个与数据模型匹配的图类型。
''' CREATE GRAPH TYPE IF NOT EXISTS betweenness_centrality_graph_type AS { NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}), EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node) } ''' -
下载以下 CSV 文件，保留文件名，保存到部署目录下的
examples/algorithms/betweenness_centrality/：查看 CSV 内容
betweenness_centrality_node.csvid,rating 1,0 2,2 3,1 4,0 5,0 6,2 7,1 8,2 9,0 10,1 11,0 12,2 13,1 14,1 15,0 16,2 17,0 18,1 19,2 20,0 21,2 22,1 23,0 24,1betweenness_centrality_edge.csvsrc_id,dst_id,weight 1,2,4 1,3,2 1,4,7 1,5,9 2,3,1 2,4,6 2,5,5 2,6,2 3,4,3 3,5,4 3,6,8 4,6,2 4,7,6 4,8,5 5,6,4 5,8,7 5,9,6 6,8,1 6,9,5 6,10,6 7,9,2 7,10,9 8,9,3 8,11,6 8,12,4 9,10,4 9,12,7 9,13,2 10,12,1 10,13,8 10,14,4 11,12,2 11,14,5 11,15,7 12,14,3 12,15,6 12,16,5 13,15,2 13,16,7 14,15,4 14,17,8 14,18,2 15,16,1 15,18,5 15,19,3 16,18,3 16,19,6 17,18,2 17,20,7 17,21,5 18,19,4 18,21,9 18,22,6 19,21,1 19,22,5 20,21,3 20,23,6 20,24,8 21,22,2 21,23,4 21,24,7 22,24,4 23,24,1 -
基于图类型创建临时图，并将数据文件加载到临时图中。
CREATE TEMPORARY GRAPH IF NOT EXISTS #betweenness_centrality_graph TYPED betweenness_centrality_graph_type''' USE #betweenness_centrality_graph IMPORT INTO GRAPH { NODE (v@Node {id: id, rating: rating}) FROM DATAFILE { PATH: "file:///examples/algorithms/betweenness_centrality/betweenness_centrality_node.csv", FORMAT: "CSV", DELIMITER: ',' }, EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE { PATH: "file:///examples/algorithms/betweenness_centrality/betweenness_centrality_edge.csv", FORMAT: "CSV", DELIMITER: ',' } } '''导入成功后，在控制台执行以下查询核对点数：
''' USE #betweenness_centrality_graph MATCH (n) RETURN count(n) AS node_count '''node_count应为24。点数不符时，先按文件问题排查检查文件和导入结果。
2. 创建过程¶
创建实现中介中心性算法的过程。关于该过程的更多信息，请参见过程实现。
'''
CREATE OR REPLACE PROCEDURE betweenness_centrality()
RETURNS (vertex_id INT64, score DOUBLE)
COMMENT "Compute classic unweighted betweenness centrality for all vertices on an undirected graph via the Brandes algorithm, using vertex property id as the identifier and treating shortest paths by hop count."
AS {
VALUE frontier ACTIVE_SET
VALUE source_ids ListAgg<INT64>
VALUE has_next OrAgg = false
VALUE inf INT64 = 1000000000
VALUE source_id INT64 = 0
VALUE src_idx INT64 = 0
VALUE level INT64 = 0
VALUE max_level INT64 = 0
VALUE rev_level INT64 = 0
NODE VALUE bc SumAgg<DOUBLE> = 0.0
NODE VALUE dist MinAgg<INT64> = 1000000000
NODE VALUE sigma SumAgg<DOUBLE> = 0.0
NODE VALUE delta SumAgg<DOUBLE> = 0.0
TABLE result_table TYPED TABLE {vertex_id INT64, score DOUBLE}
MATCH (n)
PER NODE (n) {
SET n.@bc = 0.0
SET @source_ids += n.id
}
WHILE src_idx < @source_ids.size() THEN {
SET source_id = @source_ids[src_idx]
SET src_idx = src_idx + 1
SET level = 0
SET max_level = 0
MATCH (n)
PER NODE (n) {
SET n.@dist = inf
SET n.@sigma = 0.0
SET n.@delta = 0.0
}
MATCH (s)
WHERE s.id = source_id
PER NODE (s) {
SET s.@dist = 0
SET s.@sigma = 1.0
SET s.@delta = 0.0
}
FINALLY {
SET frontier = s
}
SET @has_next = true
WHILE @has_next = true THEN {
SET @has_next = false
SET level = level + 1
MATCH (u)-[e]-(v)
WHERE u IN frontier AND v.@dist = inf
PER PATH {
SET @has_next += true
}
FINALLY {
SET frontier = v
}
IF @has_next = true THEN {
SET max_level = level
MATCH (v)
WHERE v IN frontier
PER NODE (v) {
SET v.@dist = level
}
MATCH (v)-[e]-(u)
WHERE v IN frontier AND u.@dist = level - 1
PER PATH {
SET v.@sigma += u.@sigma
}
}
}
SET rev_level = max_level
WHILE rev_level > 0 THEN {
MATCH (v)-[e]-(w)
WHERE v.@dist = rev_level - 1 AND w.@dist = rev_level
PER PATH {
VALUE contrib DOUBLE = 0.0
IF w.@sigma > 0.0 THEN {
SET contrib = (v.@sigma / w.@sigma) * (1.0 + w.@delta)
SET v.@delta += contrib
}
}
MATCH (w)
WHERE w.@dist = rev_level AND w.id <> source_id
PER NODE (w) {
SET w.@bc += w.@delta
}
SET rev_level = rev_level - 1
}
}
MATCH (n)
PER NODE (n) {
EXPORT n.id, n.@bc / 2.0 INTO result_table
}
FOR r IN result_table
RETURN r.vertex_id AS vertex_id, r.score AS score
ORDER BY score DESC, vertex_id ASC
}
'''
3. 调用过程¶
计算各点的中介中心性分数。
USE #betweenness_centrality_graph CALL betweenness_centrality() RETURN vertex_id, score
返回：
展开查看返回
+-----------+--------------------+
| vertex_id | score |
+-----------+--------------------+
| 14 | 67.8918657967101 |
| 10 | 51.75309772968774 |
| 18 | 40.30392916544371 |
| 12 | 37.370764716983835 |
| 6 | 33.38757193543222 |
| 8 | 32.13354984875291 |
| 17 | 30.42103303694065 |
| 21 | 29.912102529148715 |
| 15 | 26.875354636179623 |
| 9 | 24.913164244339967 |
| 5 | 16.162075382607817 |
| 16 | 15.65169579580913 |
| 19 | 14.87225072961119 |
| 11 | 12.14105197018898 |
| 4 | 12.043896472711737 |
| 13 | 11.120121682305985 |
| 22 | 6.730357142857143 |
| 20 | 6.524206994660801 |
| 7 | 3.3496843489235455 |
| 2 | 1.1211129203521168 |
| 3 | 1.1211129203521168 |
| 24 | 1.0 |
| 1 | 0.2 |
| 23 | 0.0 |
+-----------+--------------------+
保存结果到文件或图中
如需将返回的结果保存为 CSV 文件或写入图，请参见 EXPORT。导出字段应与返回列及目标属性对应。