Betweenness Centrality
SQL function: cugraph_betweenness_centrality
Official cuGraph reference: C API
Measure how often each vertex lies on shortest paths between other vertex pairs, exactly or from an explicit sample of source vertices.
Quickstart
The call below supplies edges from registered relation target_edges with canonical src and dst columns and may include weight. Substitute your own registered relations.
SELECT * FROM cugraph_betweenness_centrality(edges => (SELECT src, dst FROM target_edges));
Inputs
Every relation is a named parenthesized SELECT subquery. The required edges role uses canonical src and dst columns; every role, its canonical columns, and their accepted Arrow types are listed under Relation arguments. Metadata validation resolves registered tables named in its JSON request.
Endpoint columns accept numeric Int32, Int64 vertex IDs or logical string Utf8, LargeUtf8, Utf8View vertex IDs; string vertex-identity outputs are canonicalized to Utf8 (native mapping Int64) while scores, distances, counts, coordinates, and opaque labels stay numeric. The shared vertex-ID contract is summarized in Vertex ID support; the concrete call-specific schema comes from gpu_validate_call.
Logical string side-input limitations:
- edge ID columns and edge-ID predicate side inputs are not supported for logical string graphs
Arguments and options
Relation arguments
| Argument | Required | Columns | Description |
|---|---|---|---|
edges | yes |
| edge relation with canonical src and dst columns, plus optional weight and edge_id columns |
Every edge_id column must have the integer type of src and dst; string-keyed graphs accept no edge IDs.
Named value arguments
| Option | Type | Default | Constraints | Description |
|---|---|---|---|---|
exact_vertex_threshold | integer | 100000 | min 0; max 18446744073709552000 | vertex count threshold for exact betweenness |
include_endpoints | boolean | false | whether betweenness includes endpoints | |
k | integer|null | null | min 1; max 18446744073709552000 | optional sample count, at least 1 |
normalized | boolean | true | whether centrality scores are normalized | |
seeds | array|null | null | optional non-empty homogeneous seed vertex array |
Graph construction options
Graph construction follows the shared defaults (directed=true, renumbering, python_cugraph policy) documented in Graph Construction Options.
Output
| Column | Type | Nullable | Description |
|---|---|---|---|
vertex | Int64|Utf8 | no | Algorithm result column. |
value | Float64 | no | Algorithm result column. |
These are generic descriptor schemas; run gpu_validate_call to get the concrete, table-specific output schema.
Examples
This example runs on the citation network demo dataset.
Exact betweenness on a SQL-defined subgraph
Exact betweenness is refused above exact_vertex_threshold (100k vertices by
default), so the full 4.1M-vertex citation graph needs {"k": N} or explicit
seeds. A WHERE clause is the cleaner instrument: the 2010s AI literature
(same views as the Louvain example)
is a ~38k-vertex graph, small enough that every source is used and the scores
are exact and deterministic; no sampling options required.
CREATE OR REPLACE VIEW ai_nodes AS
SELECT paper_id FROM papers
WHERE year >= 2010 AND primary_fos IN (
'Deep learning', 'Artificial neural network', 'Convolutional neural network',
'Recurrent neural network', 'Natural language processing',
'Reinforcement learning', 'Image segmentation', 'Feature extraction',
'Object detection', 'Speech recognition');
CREATE OR REPLACE VIEW ai_edges AS
SELECT e.src, e.dst
FROM citation_edges e
JOIN ai_nodes a ON a.paper_id = e.src
JOIN ai_nodes b ON b.paper_id = e.dst;
SELECT p.title, p.year, p.primary_fos, CAST(b.value AS BIGINT) AS paths_through
FROM cugraph_betweenness_centrality(
edges => (SELECT src, dst FROM ai_edges), normalized => false) b
JOIN papers p ON p.paper_id = b.vertex
ORDER BY b.value DESC
LIMIT 6;
| title | year | primary_fos | paths_through |
|---|---|---|---|
| Deep learning in neural networks | 2015 | Deep learning | 1,107,737 |
| Rich Feature Hierarchies for Accurate Object Detection and Semantic Segmentation | 2014 | Object detection | 1,053,439 |
| ImageNet Large Scale Visual Recognition Challenge | 2015 | Object detection | 551,884 |
| Squeeze-and-Excitation Networks | 2017 | Convolutional neural network | 535,545 |
| SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model size | 2017 | Deep learning | 503,771 |
| Regionlets for Generic Object Detection | 2013 | Object detection | 475,746 |
With normalized: false the score is a raw count: over one million shortest
citation chains inside this subgraph pass through the Deep learning in neural
networks survey and through R-CNN. These are the brokers between AI
subfields (surveys and boundary-crossing architectures), a different signal
than citation volume: none of them is the most-cited paper in the view. In
this run the exact call over the 164k-edge subgraph returned in well under a
second on the capture host.
On the full graph, pass a deterministic sample size instead: execution uses
the first k distinct graph vertices in stable order and refuses k larger
than the actual vertex count:
SELECT * FROM cugraph_betweenness_centrality(
edges => (SELECT src, dst FROM citation_edges), k => 64, normalized => false);
Limits
No algorithm-specific limitations.
To dry-run validate relation metadata, column types, and options without execution, see gpu_validate_call.