Katz Centrality

Overview

Katz Centrality measures the influence of a node by considering not only its immediate connections but also its indirect connections at various distances while diminishing importance to more distant nodes.

Katz centrality scores range from 0 to 1, with higher scores indicating nodes that exert greater influence over the flow and connectivity of the network.

References:

• L. Katz, A New Status Index Derived from Sociometric Analysis (1953)

Concepts

Katz Centrality

The Katz centrality is an extension of the eigenvector centrality. In the k-th round of influence propagation in eigenvector centrality, the centrality vector is simply updated as c(k) = Ac(k-1), where A is the adjacency matrix. Katz centrality modifies this computation by introducing two additional parameters, leading to the following update formula (which should be rescaled afterward):

where,

• α (alpha) is an attenuation factor that controls how influence decays during each propagation round. In the k-th round, the influences from indirect neighbors that are k steps away are considered, with their contributions cumulatively attenuated by a factor of αk. To ensure the convergence of c(k), α must be smaller than 1/λmax, where λmax is the dominant eigenvalue of the adjacency matrix A.
• β (beta) is a baseline centrality constant that ensures each node has a nonzero centrality score, even when it receives no influence. The common choice for β is 1.
• 1 is an n × 1 column vector of ones, where n is the number of nodes in the graph.

Example Graph

GQL
INSERT (web1:web {_id: "web1"}), (web2:web {_id: "web2"}),
       (web3:web {_id: "web3"}), (web4:web {_id: "web4"}),
       (web5:web {_id: "web5"}), (web6:web {_id: "web6"}),
       (web7:web {_id: "web7"}),
       (web1)-[:link {value: 2}]->(web1), (web1)-[:link {value: 1}]->(web2),
       (web2)-[:link {value: 0.8}]->(web3), (web3)-[:link {value: 0.5}]->(web1),
       (web3)-[:link {value: 1.1}]->(web2), (web3)-[:link {value: 1.2}]->(web4),
       (web3)-[:link {value: 0.5}]->(web5), (web5)-[:link {value: 0.5}]->(web3),
       (web6)-[:link {value: 2}]->(web6)

Parameters

Run Mode

Returns:

Katz centrality for all nodes:

GQL
CALL algo.katz({
  alpha: 0.4,
  maxIterations: 50,
  tolerance: 0.00001,
  direction: "in",
  order: "desc"
}) YIELD nodeId, score, rank

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.katz.stream({
  alpha: 0.4,
  beta: 1,
  maxIterations: 100,
  tolerance: 0.00001,
  direction: "in",
  weight: ["value"],
  order: "desc"
}) YIELD nodeId, score
RETURN nodeId, score

Result:

Stats Mode

Returns:

GQL
CALL algo.katz.stats() YIELD nodeCount, minScore, maxScore, avgScore

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.katz.write({alpha: 0.1}, {
  db: {
    property: "katz_score"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs