Eigenvector Centrality

Compute eigenvector centrality via power iteration on the adjacency matrix

Category: centrality

Syntax

SELECT * FROM graph_eigenvector(table_name [, max_iterations] [, tolerance])

Description

Eigenvector centrality assigns each vertex a score proportional to the sum of the scores of its neighbours. Formally, the score vector is the principal eigenvector of the (possibly weighted) adjacency matrix: a node is important if it is pointed to by other important nodes. Unlike PageRank, there is no teleport term and no damping, so the metric measures pure structural influence. The score vector is L2-normalised at every iteration, so the values lie in [0, 1] and the result is invariant under positive scaling of edge weights. The CPU implementation in delta-forge-graph initialises every node to 1 / sqrt(n) and applies parallel power iteration. On directed graphs it follows the Neo4j NATURAL convention: each vertex accumulates contributions from its in-neighbours, weighted by the forward edge weight of the reverse traversal, which yields the principal eigenvector of A^T (the left eigenvector, equivalent to inbound influence). On undirected graphs the adjacency is symmetric and the pull simplifies to a sum over neighbours weighted by the forward edge weight. After each iteration the L2 norm is computed in parallel and the vector is divided by it. Convergence is tested with L-infinity on the per-node delta between successive normalised iterates. Disconnected graphs converge to a vector whose mass concentrates on the largest strongly connected component, and isolated nodes converge to 0. Results are returned sorted by score descending. The GPU implementation in delta-forge-graph-gpu is a wgpu port of NVIDIA cuGraph's eigenvector_centrality_impl.cuh. Each iteration runs a pull-shaped pass that adds the per-edge contribution sum_{u in in(v)} old[u] * w(u, v) plus the cuGraph plus-old term, then a two-stage L2 partial-sum reduction, a divide-by-hypotenuse normalisation, and an L-infinity max-diff convergence check via bitcast plus atomicMax. The GPU fast path engages only when the graph has at least 1,000 nodes (thresholds::PAGERANK). 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. The graph cache (256 MB default budget, LRU eviction, 10-minute idle timeout) retains the CSR topology across repeated invocations, so successive eigenvector calls on the same table skip the CSR construction phase.

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. If a weight column is present it feeds the adjacency-matrix entries directly, so the algorithm computes the principal eigenvector of the weighted adjacency.
`max_iterations`		Cap the number of power-iteration rounds. The driver may exit earlier once L-infinity convergence is reached on the L2-normalised vector. Defaults to 100, which is higher than PageRank because eigenvector centrality has no teleport term and converges more slowly on graphs with small spectral gap.
`tolerance`		Set the L-infinity convergence threshold on per-node delta between successive normalised iterates. Defaults to 1e-7, matching Neo4j GDS gds.eigenvector.

Examples

CREATE TABLE influence AS
SELECT * FROM VALUES
  (1, 2, 1.0),
  (2, 1, 1.0),
  (2, 3, 1.0),
  (3, 2, 1.0),
  (3, 4, 1.0),
  (4, 3, 1.0),
  (4, 5, 1.0),
  (5, 4, 1.0)
AS t(src, dst, weight);

SELECT * FROM graph_eigenvector('influence');

SELECT * FROM graph_eigenvector('influence', 500, 1e-9);

SELECT node_id, score
FROM graph_eigenvector('influence')
ORDER BY score DESC
LIMIT 5;

SELECT e.node_id, p.full_name, p.team, e.score
FROM graph_eigenvector('influence') e
JOIN people p ON e.node_id = p.id
ORDER BY e.score DESC;

SELECT
  e.node_id,
  e.score AS eigenvector,
  h.authority,
  h.hub
FROM graph_eigenvector('influence') e
JOIN graph_hits('influence') h
  ON e.node_id = h.node_id
ORDER BY e.score DESC;

Pitfalls

On graphs with a small spectral gap (eigenvalue ratio close to 1.0) power iteration converges slowly and the default cap of 100 iterations may be reached before tolerance is met. The function returns the partially converged vector without surfacing a warning, so the score order can be unstable across re-runs. Raise max_iterations or tighten tolerance for such graphs.
Disconnected graphs collapse most of the score mass onto the largest strongly connected component. Nodes in smaller components, including isolated nodes, converge to scores very close to 0.0. Compute connected components first if you need per-component centrality.
Edge weights are interpreted as raw adjacency-matrix entries. Negative weights are not supported because power iteration tracks the largest-magnitude eigenvalue and signed inputs can produce a non-positive eigenvector. Ensure weights are non-negative before calling the function.
On directed graphs the result is the left eigenvector (inbound influence) by Neo4j convention. If you need the right eigenvector (outbound influence) reverse the source and destination columns before calling the function.
When the graph is all-zero (every weight is 0.0 or every node is isolated) the L2 norm reduces to 0 and the algorithm exits early at the initial uniform vector. The emitted scores are all equal to 1 / sqrt(n), which is mathematically valid but conveys no ranking information.
The GPU fast path activates only when the graph has at least 1,000 nodes. Smaller graphs always run on CPU even if a GPU is registered.