Katz Centrality

SQL function: cugraph_katz_centrality

Official cuGraph reference: C API

Score vertices from the number of walks that reach them, attenuating longer walks and adding a baseline contribution.

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_katz_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	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

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
alpha	number	0.01	max 1; > 0	Katz alpha in (0, 1]
beta	number	1	> 0	positive Katz beta
epsilon	number	0.000001	> 0	positive convergence tolerance
max_iterations	integer	1000	min 1; max 4294967295	maximum iteration count, at least 1

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	Vertex receiving the Katz centrality score.
value	Float64	no	Katz centrality score for the vertex.

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.

alpha decides how deep credit flows

Katz centrality counts all incoming walks, discounting a walk of length n by alpha^n. At the default alpha (0.01) long chains contribute almost nothing and the ranking is nearly in-degree. Raising alpha to 0.05 shifts credit to papers whose citers are themselves heavily cited, transitively; window functions over the two results make the shift visible as rank movement:

WITH katz AS (
  SELECT vertex, ROW_NUMBER() OVER (ORDER BY value DESC) AS katz_rank
  FROM cugraph_katz_centrality(
    edges => (SELECT src, dst FROM citation_edges), alpha => 0.05)),
deg AS (
  SELECT vertex, in_degree, ROW_NUMBER() OVER (ORDER BY in_degree DESC) AS degree_rank
  FROM cugraph_in_degrees_all(edges => (SELECT src, dst FROM citation_edges)))
SELECT p.title, p.year, k.katz_rank, d.degree_rank, d.in_degree
FROM katz k
JOIN deg d ON d.vertex = k.vertex
JOIN papers p ON p.paper_id = k.vertex
WHERE k.katz_rank <= 8
ORDER BY k.katz_rank;

title	year	katz_rank	degree_rank	in_degree
Distinctive Image Features from Scale-Invariant Keypoints	2004	1	1	22,892
The Nature of Statistical Learning Theory	1995	2	6	14,508
Histograms of oriented gradients for human detection	2005	3	9	13,768
Object recognition from local scale-invariant features	1999	4	58	6,300
New Directions in Cryptography	1976	5	69	6,007
The Design and Analysis of Computer Algorithms	1974	6	103	5,168
A Computational Approach to Edge Detection	1986	7	24	9,069
A method for obtaining digital signatures and public-key cryptosystems	1978	8	50	6,580

The risers are the foundations: New Directions in Cryptography climbs from in-degree rank #69 to Katz rank #5 and the RSA paper from #50 to #8, because the papers citing them anchor entire downstream literatures. Katz is the natural choice on citation-style graphs; near-acyclic structure starves eigenvector centrality, while the beta base score keeps every vertex non-zero here. Convergence requires alpha below the reciprocal of the graph's largest eigenvalue: pushing it too high fails with a convergence error rather than returning partial scores.

Limits

No algorithm-specific limitations.

To dry-run validate relation metadata, column types, and options without execution, see gpu_validate_call.