Fast Katz Centrality on Dynamic Graphs
Prajjwal Nijhara, Dishit Sharma, Dip Sankar Banerjee · 2025
In network analysis, Katz centrality is widely used to measure node influence by considering both direct and indirect connections weighted by path length. While numerous studies have examined Katz centrality for static graphs, relatively few address the challenges posed by dynamic graphs. Katz centrality can utilize perturbation theory by exploiting iterative solvers to obtain updated Katz scores in dynamic graphs. However, these methods are limited to handling only small changes, as they generally accept only minor structural updates limited to only edge insertions or removals. Additionally, due to an iterative approach, the solutions can be sequential and provide approximate answers, which may reduce accuracy when the graph undergoes frequent updates over time. This paper introduces a novel algorithm that significantly improves the efficiency of Katz centrality calculations in dynamic graphs. After each update, we identify affected nodes using a Breadth First Search (BFS) frontier and then apply dynamic programming, which allows for both edge/node insertions and deletions. Our parallel implementation on a shared memory platform achieves a 5.29 x speedup on an average over the static version. Our algorithm can update a batch of 1 million edges on an existing graph of 1 billion edges in 24.73 seconds.