Ranking in Dynamic Graphs Using Exponential Centrality

2018
OriginalPaper
Chapter

Published in:

Authors: Eisha Nathan; James Fairbanks; David Bader
Published in: Complex Networks & Their Applications VI
Publisher: Springer International Publishing

Read first chapter Log in

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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\(\times \) 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.

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Business + Economics & Engineering + Technology"

Online-Abonnement

Springer Professional "Business + Economics & Engineering + Technology" gives you access to:

more than 102.000 books
more than 537 journals

from the following subject areas:

Automotive
Construction + Real Estate
Business IT + Informatics
Electrical Engineering + Electronics
Energy + Sustainability
Finance + Banking
Management + Leadership
Marketing + Sales
Mechanical Engineering + Materials
Insurance + Risk

Secure your knowledge advantage now!

inform now

Springer Professional "Engineering + Technology"

Online-Abonnement

Springer Professional "Engineering + Technology" gives you access to:

more than 67.000 books
more than 390 journals

from the following specialised fileds:

Automotive
Business IT + Informatics
Construction + Real Estate
Electrical Engineering + Electronics
Energy + Sustainability
Mechanical Engineering + Materials

Secure your knowledge advantage now!

inform now

Springer Professional "Business + Economics"

Online-Abonnement

Springer Professional "Business + Economics" gives you access to:

more than 67.000 books
more than 340 journals

from the following specialised fileds:

Construction + Real Estate
Business IT + Informatics
Finance + Banking
Management + Leadership
Marketing + Sales
Insurance + Risk

Secure your knowledge advantage now!

inform now

previous chapter Toward a Better Understanding of Emotional Dynamics on Facebook

next chapter A Nonlinear Dynamical Approach to the Interpretation of Microblogging Network Complexity

Metadata
Literature

Title: Ranking in Dynamic Graphs Using Exponential Centrality
Authors: Eisha Nathan
James Fairbanks
David Bader
Publisher: Springer International Publishing
Book: Complex Networks & Their Applications VI
Print ISBN: 978-3-319-72149-1

Electronic ISBN: 978-3-319-72150-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-72150-7_31

This content is only visible if you are logged in and have the appropriate permissions.