TY - GEN
T1 - Ranking in dynamic graphs using exponential centrality
AU - Nathan, Eisha
AU - Fairbanks, James
AU - Bader, David
N1 - Publisher Copyright:
© Springer International Publishing AG 2018.
PY - 2018
Y1 - 2018
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85036665171&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85036665171&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-72150-7_31
DO - 10.1007/978-3-319-72150-7_31
M3 - Conference contribution
AN - SCOPUS:85036665171
SN - 9783319721491
T3 - Studies in Computational Intelligence
SP - 378
EP - 389
BT - Complex Networks and Their Applications VI - Proceedings of Complex Networks 2017 (The 6th International Conference on Complex Networks and Their Applications)
A2 - Cherifi, Hocine
A2 - Cherifi, Chantal
A2 - Musolesi, Mirco
A2 - Karsai, Márton
PB - Springer Verlag
T2 - 6th International Conference on Complex Networks and Their Applications, Complex Networks 2017
Y2 - 29 November 2017 through 1 December 2017
ER -