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.

Signature

cugraph_betweenness_centrality(table_name [, src_col, dst_col [, weight_col [, options_json]]])

Quickstart

The call below expects a registered edge table or view target_edges with endpoint columns src and dst. Substitute your own registered relations.

SELECT * FROM cugraph_betweenness_centrality('target_edges');

Inputs

table_name must be a registered edge table or view (the edges role); parenthesized subqueries are not accepted, and metadata validation resolves the same registered name.

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

Positional scalar arguments

src_col and dst_col name the edge endpoint columns; both are optional and default to src and dst.

Argument	Type	Required	Default	Notes
weight_col	Utf8|null	no		accepted as an edge-column binding; native algorithm execution does not consume weights; semantic effect: none for this algorithm

JSON options

Option	Type	Default	Constraints	Description
exact_vertex_threshold	UInt64	100000		Maximum actual graph vertex count allowed for exact betweenness without explicit seeds or k.
include_endpoints	Boolean	false		When true, the two endpoints of each shortest path count as lying on that path; the traditional formulation (false) excludes them.
k	UInt64|null	null	min 1; mutually exclusive with seeds	Deterministic approximate seed count. Execution uses the first k distinct graph vertices in stable order and refuses k larger than the actual vertex count.
normalized	Boolean	true		When true, scores are scaled by the maximum possible value for the vertex count and directedness so results lie in [0, 1]; when false, raw shortest-path counts are returned.
seeds	List<Int64>|List<Utf8>|null	null	mutually exclusive with k	Explicit homogeneous integer or string seed vertices for approximate betweenness. Null requests exact all-vertex betweenness unless k is set.

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; validate the 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('ai_edges', 'src', 'dst', NULL,
                                    '{"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,735
Rich Feature Hierarchies for Accurate Object Detection and Semantic Segmentation	2014	Object detection	1,053,444
ImageNet Large Scale Visual Recognition Challenge	2015	Object detection	551,882
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,772
Regionlets for Generic Object Detection	2013	Object detection	475,727

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('citation_edges', 'src', 'dst', NULL,
                                             '{"k": 64, "normalized": false}');

Limits

No algorithm-specific limitations.

Validate the call

Dry-run validation checks registered relation metadata, column presence, static dtypes, and options only; it does not scan edge data, construct a graph, or prove source-vertex existence:

SELECT * FROM gpu_validate_call(
  'cugraph_betweenness_centrality',
  '{"schema_version":1,"relations":{"edges":{"table":"target_edges"}},"options":{"src_col":"src","dst_col":"dst"}}'
);

See GPU Function Catalog API for the full gpu_validate_call contract.