Skip to main content

katz_centrality

docs-source

Abstract

Katz Centrality is the measurement of centrality that incorporates the inbound path length starting from the wanted node. More central nodes will have closer connections rather than having many long-distance nodes connected to them.

The implemented algorithm is based on the work of Alexander van der Grinten et. al. called Scalable Katz Ranking Computation in Large Static and Dynamic Graphs1. The author proposes an estimation method that preserves rankings for both static and dynamic Katz centrality scenarios.

Theoretically speaking there exists an attenuation factor (alpha^i) smaller than 1 which is applied to walks of length i. If w_i(v) is the number of walks of length i starting from node v, Katz centrality is defined as:

Centrality(v) = sum { w_i(v) * alpha ^ i}

The constructed algorithm computes Katz centrality by iteratively improving the upper and lower bounds on centrality scores. This guarantees that centrality rankings will be correct, but it does not guarantee that the corresponding resulting centralities will be correct.

1 Scalable Katz Ranking Computation in Large Static and Dynamic Graphs, Alexander van der Grinten et. al.

TraitValue
Module typealgorithm
ImplementationC++
Graph directiondirected
Edge weightsunweighted
Parallelismsequential

Procedures

get(alpha, epsilon)

Input:

  • alpha: double(0.2) ➡ Exponential decay factor defining the walk length importance.
  • epsilon: double(1e-2) ➡ Convergence tolerance. Minimal difference in two adjacent pairs of nodes in the final ranking.

Output:

  • node ➡ Node in the graph, for which Katz Centrality is calculated.
  • rank ➡ Normalized ranking of a node. Expresses the centrality value after bound convergence

Usage:

CALL katz_centrality.get()
YIELD node, rank;

Example