Incrementally updating Katz centrality in dynamic graphs

Eisha Nathan, David A. Bader

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


A variety of large datasets, such as social networks or biological data, can be represented as graphs. A common query in graph analysis is to identify the most important vertices in a graph. Centrality metrics are used to obtain numerical scores for each vertex in the graph. The scores are then translated to rankings identifying relative importance of vertices. In this work, we focus on Katz centrality, a linear algebra-based metric. In many real applications, since data are constantly being produced and changed, it is necessary to have a dynamic algorithm to update centrality scores with minimal computation when the graph changes. We present an algorithm for updating Katz centrality scores in a dynamic graph that incrementally updates the centrality scores as the underlying graph changes. Our proposed method exploits properties of iterative solvers to obtain updated Katz scores in dynamic graphs. Our dynamic algorithm improves performance and achieves speedups of over two orders of magnitude compared to a standard static algorithm while maintaining high quality of results.

Original languageEnglish (US)
Article number26
JournalSocial Network Analysis and Mining
Issue number1
StatePublished - Dec 1 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Communication
  • Media Technology
  • Human-Computer Interaction
  • Computer Science Applications


  • Dynamic graphs
  • Iterative solvers
  • Katz centrality


Dive into the research topics of 'Incrementally updating Katz centrality in dynamic graphs'. Together they form a unique fingerprint.

Cite this