Dynamic Graphs: Katz Centrality (KC)

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.