Approximating personalized katz centrality in dynamic graphs

Eisha Nathan, David A. Bader

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations


Dynamic graphs can capture changing relationships in many real datasets that evolve over time. One of the most basic questions about networks is the identification of the “most important” vertices in a network. Measures of vertex importance called centrality measures are used to rank vertices in a graph. In this work, we focus on Katz Centrality. Typically, scores are calculated through linear algebra but in this paper we present an new alternative, agglomerative method of calculating Katz scores and extend it for dynamic graphs. We show that our static algorithm is several orders of magnitude faster than the typical linear algebra approach while maintaining good quality of the scores. Furthermore, our dynamic graph algorithm is faster than pure static recomputation every time the graph changes and maintains high recall of the highly ranked vertices on both synthetic and real graphs.

Original languageEnglish (US)
Title of host publicationParallel Processing and Applied Mathematics - 12th International Conference, PPAM 2017, Revised Selected Papers
EditorsJack Dongarra, Roman Wyrzykowski, Konrad Karczewski, Ewa Deelman
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319780238
StatePublished - 2018
Externally publishedYes
Event12th International Conference on Parallel Processing and Applied Mathematics, PPAM 2017 - Czestochowa, Poland
Duration: Sep 10 2017Sep 13 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10777 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference12th International Conference on Parallel Processing and Applied Mathematics, PPAM 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


  • Approximate centrality
  • Dynamic graphs
  • Katz centrality
  • Personalized centrality


Dive into the research topics of 'Approximating personalized katz centrality in dynamic graphs'. Together they form a unique fingerprint.

Cite this