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