Add the Betweenness Centrality graph algorithm
- Dominant language
- Java
- Stars
- 808
- Forks
- 188
- Avg merge
- 3d 22h
- Merged PRs (30d)
- 2
Description
### What & why
GeaFlow has PageRank and ClosenessCentrality, but not **Betweenness Centrality** —
a measure of how often a vertex sits on shortest paths between other vertices,
i.e. how much of a "bridge" it is. It's a core metric for social-network and
key-node analysis. It's also genuinely hard: the classic Brandes algorithm has
two phases (shortest-path counting + dependency accumulation), which makes it a
satisfying high-difficulty challenge.
GeaFlow 有 PageRank、ClosenessCentrality,但缺**介数中心性**(Betweenness)——衡量一个
顶点作为"最短路径桥梁"的重要性,是社交网络/关键节点分析的核心指标。它实现难度大
(经典 Brandes 算法需要两阶段:最短路径计数 + 依赖累积),非常适合作为高难度挑战题。
### The task
Implement Betweenness Centrality on GeaFlow's vertex-centric / message-passing
model (an unweighted-graph version is a fine first cut).
基于 GeaFlow 的顶点中心/消息传递模型实现介数中心性(可先做无权图版本)。
### Where to look / 怎么做
1. Reference the more complex existing algorithms:
`udf/graph/PageRank.java` (multi-iteration + convergence) and
`SingleSourceShortestPath.java` (shortest paths).
2. Implement `AlgorithmUserFunction` using multi-round iteration + `sendMessage`
for shortest-path counting and dependency back-propagation (the Brandes approach).
3. Register in `BuildInSqlFunctionTable.java`.
4. Use a small graph (5–7 nodes), compute the standard answer by hand, and turn
it into `.sql`/`.txt` tests.
### Done when
- [ ] Implemented and registered; `CALL betweenness() YIELD (id, score)` works
- [ ] Results match hand-calculation / NetworkX on a small graph (attach the comparison in the PR)
- [ ] Complexity and suitable scale documented (note it's for small/medium graphs if so)
- [ ] Tests pass
Contributor guide
Research direction
Start by reading udf/graph/PageRank.java and SingleSourceShortestPath.java to understand GeaFlow's AlgorithmUserFunction, iteration, and sendMessage model. Add the Brandes-based unweighted algorithm, register it in BuildInSqlFunctionTable.java, and create .sql/.txt tests for a 5–7-node graph whose scores match hand calculations or NetworkX; document complexity and supported scale.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- distributed-systems
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100