Harmonic Centrality

Compute harmonic centrality, the sum of reciprocal shortest-path distances

Category: centrality

Syntax

SELECT * FROM graph_harmonic(table_name)

Description

Harmonic centrality, introduced by Marchiori and Latora (2000) and refined by Rochat (2009), measures how close a node is to the rest of the graph by summing the reciprocals of shortest-path distances. The score for node v is sum over u not equal to v of 1 / d(v, u). Unlike classical closeness centrality, which divides n - 1 by the sum of distances, harmonic centrality handles disconnected graphs natively: unreachable nodes contribute 0 because 1 over infinity is 0, so the metric is always well defined without Wasserman-Faust normalisation. Higher values mean the node is close to many other nodes on average. On directed graphs the SQL surface emits the outgoing-harmonic variant: from v, BFS walks outgoing edges and the contribution 1 / d(v, u) accumulates at u, matching the Neo4j NATURAL projection. The CPU implementation in delta-forge-graph runs a parallel BFS from every source vertex. Sources are chunked so that one BFS per rayon thread executes at a time, and the per-target contribution 1 / depth is folded into a per-node atomic accumulator. Atomic addition on f64 uses a compare-and-swap loop over the u64 bit pattern. The cancel token is checked between sources, so long-running computations on huge graphs interrupt promptly. Edge weights are ignored because the algorithm is defined on unweighted distance; if you need weighted shortest-path centrality use graph_closeness instead. The SQL table function surface returns the raw harmonic sum (normalized = false). The Cypher CALL algo.harmonic({normalized: true}) path applies the n - 1 divisor independently in columnar_executor::algorithms. Results are returned sorted by score descending. The GPU implementation in delta-forge-graph-gpu is a wgpu port of NVIDIA cuGraph's BFS primitive (bfs_impl.cuh) extended with a harmonic accumulator pass. Each source vertex drives a level-synchronous top-down BFS with an explicit compact frontier, edge-parallel expansion through a Hillis-Steele prefix scan over per-frontier-vertex degrees, and filtered-write next-frontier compaction. After each BFS the accumulate shader adds 1 / depth into the per-vertex score buffer using a CAS-loop emulated atomic f32 add. Boundary inputs are handled explicitly: a graph with zero nodes returns an empty result, a single isolated vertex returns one row with score 0.0, and disconnected vertices produce contributions of 0 because BFS leaves them at the unreachable sentinel. Precision is f32 on GPU rather than f64 on CPU, so for graphs with diameter beyond about 64 the GPU score may diverge from the CPU score at the 1e-7 relative ULP level. The GPU fast path engages only when the graph has at least 5,000 nodes (thresholds::HARMONIC). Below that threshold the dispatcher returns Ok(None) and the engine runs the CPU implementation. If the graph exceeds GPU memory the buffer upload also returns None and the CPU path takes over silently.

Parameters

Name	Type	Description
`table_name`		Specify the name of the registered Delta table that supplies edges. The loader auto-detects column names src/source/src_id for the source endpoint and dst/target/dst_id for the destination endpoint. Edge weights are ignored: harmonic centrality is defined in terms of unweighted shortest-path distance, and the BFS-driven implementation treats every edge as cost 1.

Examples

CREATE TABLE roads AS
SELECT * FROM VALUES
  (1, 2),
  (2, 3),
  (3, 4),
  (4, 5),
  (1, 5),
  (2, 4),
  (5, 6),
  (6, 7)
AS t(src, dst);

SELECT * FROM graph_harmonic('roads');

SELECT node_id, score
FROM graph_harmonic('roads')
ORDER BY score DESC
LIMIT 5;

SELECT h.node_id, m.intersection_name, m.borough, h.score
FROM graph_harmonic('roads') h
JOIN intersections m ON h.node_id = m.id
ORDER BY h.score DESC;

WITH h AS (
  SELECT node_id, score FROM graph_harmonic('roads')
), node_count AS (
  SELECT COUNT(*) AS n FROM h
)
SELECT
  h.node_id,
  h.score AS raw_harmonic,
  h.score / (node_count.n - 1) AS normalised_harmonic
FROM h CROSS JOIN node_count
ORDER BY raw_harmonic DESC;

SELECT
  h.node_id,
  h.score AS harmonic,
  c.score AS closeness
FROM graph_harmonic('roads') h
JOIN graph_closeness('roads') c
  ON h.node_id = c.node_id
ORDER BY h.score DESC;

Pitfalls

Scores are raw sums, not normalised. The SQL table function surface intentionally calls harmonic_centrality(graph, false, cancel_token), so the result depends on the graph size. To get the normalised variant divide by n - 1 in a downstream CTE, or use the Cypher CALL algo.harmonic({normalized: true}) form which normalises in the algorithm wrapper.
Edge weights are ignored. Harmonic centrality is defined on unweighted distance and the BFS-driven CPU and GPU implementations treat every edge as cost 1. If you need weighted shortest-path centrality use graph_closeness with a weighted edge table.
Time complexity is O(V * (V + E)) because the algorithm runs one BFS per source. On graphs with millions of nodes this is prohibitively expensive even with rayon parallelism on the CPU path. Consider sampling sources via graph_betweenness with sampling_size, or restrict the analysis to a subset of nodes via a pre-filtered edge table.
On directed graphs the result is the outgoing-harmonic variant by Neo4j NATURAL convention: BFS walks outgoing edges from each source. If you need incoming-harmonic (in-coreness) reverse the src and dst columns before calling the function.
GPU execution accumulates harmonic contributions in f32 rather than f64. For diameters above about 64, or for graphs with extremely long path lengths, the GPU score may differ from the CPU score at the 1e-7 relative ULP level. Treat the two engines as numerically equivalent only to single-precision tolerance.
The GPU fast path activates only when the graph has at least 5,000 nodes. Smaller graphs always run on CPU even if a GPU is registered, so latency comparisons across graph sizes are not directly meaningful.
Isolated nodes always score 0.0 because no BFS from any other source reaches them. They still appear in the result set, so consumers that filter for non-trivial centrality should add a WHERE score > 0.0 clause.