Parallel Katz Centrality On Evolving Graphs

Katz centrality measures a node’s influence within a network, considering the total number of walks between pairs of nodes rather than solely the shortest paths. This paper presents an algorithm for dynamically updating Katz centrality scores as the underlying graph evolves. Our method employs a frontier-based breadth-first search (BFS) to efficiently derive updated Katz scores in dynamic graphs. Notably, our algorithm accommodates node insertions and deletions, addressing a significant limitation of current state-of-the-art methods.