### Dynamic Graphs: Katz Centrality (KC)

Chapter 9: Katz Centrality in Dynamic Graphs

# Chapter 9: Katz Centrality (KC) in Dynamic Graphs

## Introduction

Katz Centrality is a metric used to measure the influence of a node in a network. It takes into account not just the immediate neighbors but also nodes that are more distantly connected. In a dynamic graph, maintaining up-to-date Katz Centrality scores can be challenging due to the frequent changes in node and edge configurations. This chapter explores these challenges and potential solutions.

## Standard Katz Centrality Algorithm

The Katz Centrality of a node $$i$$ is computed as follows:

$\text{Katz}(i) = \alpha \sum_{j=1}^{N} A_{ij} \text{Katz}(j) + \beta$

Where $$A_{ij}$$ is the adjacency matrix, $$\alpha$$ is a attenuation factor, $$N$$ is the total number of nodes, and $$\beta$$ is a constant.

## Dynamic Graphs and Katz Centrality

The main challenges for maintaining Katz Centrality in dynamic graphs are:

• When a node or edge is added, the Katz Centrality of all nodes might change.
• When a node or edge is removed, the Katz Centrality scores may also change.

## Katz Centrality in Dynamic Graphs

Strategies for updating Katz Centrality in dynamic graphs include:

1. Recomputing from Scratch: This method is straightforward but computationally expensive.
2. Incremental Updates: Incremental updates are more efficient and involve only partial recomputation.

### Incremental Katz Centrality Algorithm


IncrementalKatzCentrality(Graph G_t, KC_Scores, alpha, beta):
1. Detect changes (added/removed vertices and edges)
2. Partially recompute Katz Centrality scores affected by the changes
3. Update KC_Scores accordingly


## Conclusion

Katz Centrality is an important metric for measuring the influence of nodes in a network. In the face of dynamically changing graphs, incremental algorithms offer an efficient way to keep Katz Centrality scores up-to-date.