Skip to main content

Edge Betweenness Centrality

UDTF: cugraph_edge_betweenness_centrality

Official cuGraph reference: C API

Measure how often each edge lies on shortest paths between 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.

SELECT *
FROM cugraph_edge_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.

The vertex-ID types this UDTF accepts, the numeric types a per-call codebook maps to native ids, and its string-key limits are listed in Vertex ID support; the concrete call-specific schema comes from gpu_validate_call.

Arguments and options​

Relation arguments​

ArgumentRequiredColumnsDescription
edgesyes
  • src, dst: Int32, Int64, Utf8, LargeUtf8, Utf8View
  • weight (optional): Float32, Float64
  • edge_id (optional): Int32, Int64
edge relation with canonical src and dst columns, plus optional weight and edge_id columns; this algorithm ignores weight

Every edge_id column must have the integer type of src and dst; string-keyed graphs accept no edge IDs.

Named value arguments​

OptionTypeDefaultConstraintsDescription
exact_vertex_thresholdinteger100000min 0; max 18446744073709552000vertex count threshold for exact betweenness
kinteger|nullnullmin 1; max 18446744073709552000optional sample count, at least 1
normalizedbooleantruewhether centrality scores are normalized
seedsarray|nullnulloptional 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​

ColumnTypeNullableDescription
srcInt64|Utf8noSource vertex of the scored edge.
dstInt64|Utf8noDestination vertex of the scored edge.
valueFloat64noEdge betweenness centrality score for the edge.

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.

Which citations connect otherwise distant parts of the AI literature?​

Some citations may lie on many shortest paths through a field's literature. This query ranks individual citation edges in the selected 2010s AI subgraph and joins paper titles for both ends of each edge.

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 ps.title AS citing, pd.title AS cited, ROUND(b.value, 5) AS edge_betweenness
FROM cugraph_edge_betweenness_centrality(edges => (SELECT src, dst FROM ai_edges)) b
JOIN papers ps ON ps.paper_id = b.src
JOIN papers pd ON pd.paper_id = b.dst
ORDER BY b.value DESC
LIMIT 5;
citingcitededge_betweenness
Rich Feature Hierarchies for Accurate Object Detection and Semantic SegmentationRegionlets for Generic Object Detection0.00022
Squeeze-and-Excitation NetworksRegularized Evolution for Image Classifier Architecture Search0.00021
Improving object detection with deep convolutional networks via Bayesian optimization and structured predictionDeep learning in neural networks0.00017
SqueezeNet: AlexNet-level accuracy with 50x fewer parameters and <0.5MB model sizeShallow Networks for High-Accuracy Road Object-Detection0.00016
A survey on deep learning in medical image analysisDeep Learning Convolutional Networks for Multiphoton Microscopy Vasculature Segmentation.0.00014

These edges rank highest within the selected subgraph.