Scalable Katz Ranking Computation in Large Static and Dynamic Graphs

Alexander Grinten Van Der, Elisabetta Bergamini, Oded Green, David A. Bader, Henning Meyerhenke

Research output: Contribution to journalArticlepeer-review

Abstract

Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those measures is a major challenge in algorithmic network analysis. Aside from closeness and betweenness, Katz centrality is one of the established centrality measures. In this article, we consider the problem of computing rankings for Katz centrality. In particular, we propose upper and lower bounds on the Katz score of a given node. Previous approaches relied on numerical approximation or heuristics to compute Katz centrality rankings; however, we construct an algorithm that iteratively improves those upper and lower bounds until a correct Katz ranking is obtained. We extend our algorithm to dynamic graphs while maintaining its correctness guarantees. Experiments demonstrate that our static graph algorithm outperforms both numerical approaches and heuristics with speedups between and , depending on the desired quality guarantees. Our dynamic graph algorithm improves upon the static algorithm for update batches of less than 10,000 edges. We provide efficient parallel CPU and GPU implementations of our algorithms that enable near real-time Katz centrality computation for graphs with hundreds of millions of edges in fractions of seconds.

Original languageEnglish (US)
Article number1.7
JournalJournal of Experimental Algorithmics
Volume27
Issue number1
DOIs
StatePublished - Jul 7 2022

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science

Keywords

  • Katz centrality
  • Network analysis
  • dynamic graphs
  • parallel algorithms
  • top-k ranking

Fingerprint

Dive into the research topics of 'Scalable Katz Ranking Computation in Large Static and Dynamic Graphs'. Together they form a unique fingerprint.

Cite this