apache / apache/geaflow

Add the Betweenness Centrality graph algorithm

Open
#801 0 comments 0 reactions 0 assignees View on GitHub
enhancement good first issue
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.