# katz_centrality_online

## Abstract

Because of its simplicity, **Katz Centrality** has become one of the most
established centrality measurements. The definition of Katz centrality is that
it presents the amount of influence by summing all walks starting from the node
of interest and weighting walks by some attenuation factor smaller than 1.

Just as the other centrality measures got their dynamic algorithm
implementations, so did **Katz Centrality**. The implementation results in a
reduction of computations needed to update already calculated results. The
algorithm offers substantially large speedups compared to static algorithm runs.

The algorithm is based on the work of Alexander van der Grinten et. al. called
Scalable Katz Ranking Computation in Large Static and Dynamic
Graphs^{1}. The author proposes an
estimation method that computes Katz's centrality by iteratively improving upper
and lower bounds on the centrality scores. The computed scores may differ from
the real values, but the algorithm has the guarantee of preserving the rankings.

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

### Usage

Online Katz centrality should be used in a specific way. To set the parameters,
the user should call a `set()`

procedure. This function also sets the context of
a streaming algorithm. `get()`

function only returns the resulting values stored
in a cache. Therefore, if you try to get values before first calling `set()`

,
the run will fail with a proper message.

To make the incremental flow, you should set the proper trigger. For that, we'll
use the `update()`

function:

`CREATE TRIGGER katz_trigger`

(BEFORE | AFTER) COMMIT

EXECUTE CALL katz_centrality_online.update(createdVertices, createdEdges, deletedVertices, deletedEdges) YIELD *

SET node.rank = rank;

Finally, the `reset()`

function resets the context and enables the user to start
new runs.

Trait | Value |
---|---|

Module type | algorithm |

Implementation | C++ |

Graph direction | directed |

Edge weights | unweighted |

Parallelism | sequential |

## Procedures

If you want to execute this algorithm on graph projections, subgraphs or portions of the graph, be sure to check out the guide on How to run a MAGE module on subgraphs.

`set(alpha, epsilon)`

#### Input:

`alpha: double (default=0.2)`

➡ Exponential decay factor defining the walk length importance.`epsilon: double (default=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_online.set(0.2, 0.01)`

YIELD node, rank;

`get()`

* This should be used if the trigger has been set or a `set`

function has been
called before adding changes to the graph.

#### 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_online.get()`

YIELD node, rank;

`update(created_vertices, created_edges, deleted_vertices, deleted_edges)`

#### Input:

`created_vertices`

➡ Vertices that were created in the last transaction.`created_edges`

➡ Edges created in a period from the last transaction.`deleted_vertices`

➡ Vertices deleted from the last transaction.`deleted_edges`

➡ Edges deleted from the last transaction.

#### 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:

`CREATE TRIGGER katz_trigger`

(BEFORE | AFTER) COMMIT

EXECUTE CALL katz_centrality_online.update(createdVertices, createdEdges, deletedVertices, deletedEdges) YIELD *

SET node.rank = rank;

## Example

- Step 1: Input graph
- Step 2: Set parameters and trigger
- Step 3: Load commands
- Step 4: Running command
- Step 5: Results

`CALL katz_centrality_online.set(0.2) YIELD *;`

CREATE TRIGGER katz_trigger

BEFORE COMMIT

EXECUTE CALL katz_centrality_online.update(createdVertices, createdEdges, deletedVertices, deletedEdges) YIELD *

SET node.rank = rank;

`MERGE (a:Node {id: 1}) MERGE (b:Node {id: 0}) CREATE (a)-[:RELATION]->(b);`

MERGE (a:Node {id: 1}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 2}) MERGE (b:Node {id: 1}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 2}) MERGE (b:Node {id: 8}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 2}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 3}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 4}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 4}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 5}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 5}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 6}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 7}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 8}) MERGE (b:Node {id: 2}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 8}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 9}) MERGE (b:Node {id: 10}) CREATE (a)-[:RELATION]->(b);

MERGE (a:Node {id: 10}) MERGE (b:Node {id: 9}) CREATE (a)-[:RELATION]->(b);

`MATCH (node)`

RETURN node.id AS node_id, node.rank AS rank;

`+---------+---------+`

| node_id | rank |

+---------+---------+

| 1 | 0.408 |

| 0 | 0.28 |

| 10 | 1.864 |

| 2 | 1.08 |

| 8 | 0.408 |

| 3 | 0 |

| 4 | 0 |

| 5 | 0 |

| 6 | 0 |

| 7 | 0 |

| 9 | 0.544 |

+---------+---------+