Ranking in dynamic graphs using exponential centrality

Eisha Nathan, James Fairbanks, David Bader

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

2 Scopus citations


Many large datasets from several fields of research such as biology or society can be represented as graphs. Additionally in many real applications, data is constantly being produced, leading to the notion of dynamic graphs. A heavily studied problem is identification of the most important vertices in a graph. This can be done using centrality measures, where a centrality metric computes a numerical value for each vertex in the graph. In this work we focus on centrality scores obtained from the computation of the matrix exponential. Specifically, we present a new dynamic algorithm for updating exponential centrality-based values of vertices in evolving graphs. We show that our method is faster than pure static recomputation, obtaining about 16 × speedup in real-world networks while maintaining a high quality of recall of the top ranked vertices in graphs. Moreover, we do not see a deterioration of the quality of our algorithm over time as more data is inserted into the graph.

Original languageEnglish (US)
Title of host publicationComplex Networks and Their Applications VI - Proceedings of Complex Networks 2017 (The 6th International Conference on Complex Networks and Their Applications)
EditorsHocine Cherifi, Chantal Cherifi, Mirco Musolesi, Márton Karsai
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319721491
StatePublished - 2018
Externally publishedYes
Event6th International Conference on Complex Networks and Their Applications, Complex Networks 2017 - Lyon, France
Duration: Nov 29 2017Dec 1 2017

Publication series

NameStudies in Computational Intelligence
ISSN (Print)1860-949X


Conference6th International Conference on Complex Networks and Their Applications, Complex Networks 2017

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence


Dive into the research topics of 'Ranking in dynamic graphs using exponential centrality'. Together they form a unique fingerprint.

Cite this