Temporal betweenness centrality in dynamic graphs

Ioanna Tsalouchidou, Ricardo Baeza-Yates, Francesco Bonchi, Kewen Liao, Timos Sellis

Research output: Contribution to journalArticle

Abstract

Measures of centrality of vertices in a network are usually defined solely on the basis of the network structure. In highly dynamic networks, where vertices appear and disappear and their connectivity constantly changes, we need to redefine our measures of centrality to properly capture the temporal dimension of the network structure evolution, as well as the dynamic processes over the network. Betweenness centrality (BC), one of the most studied measures, defines the importance of a vertex as a mediator between available communication paths. BC value of a node is expressed as the fraction of the shortest paths passing through this node. In other words, given the context that information flow follows the shortest paths, a node with higher BC potentially has greater influence on the information flow in the network. In temporal dynamic graphs, a communication path should be seen as a path both in space (i.e., the network structure) and in time (i.e., the network evolution). Toward this goal, in this paper we propose the bi-objective notion of shortest–fastest path (SFP) in temporal graphs, which considers both space and time as a linear combination governed by a parameter. Based on this notion, we then define a novel temporal betweenness centrality (TBC) metric, which is highly sensitive to the observation interval and the importance of space and time distances of the vertices, that can provide better understanding of the communication mediators in temporal networks. We devise efficient algorithms for exactly computing all-pairs SFPs and the corresponding BC values both in a single graph window and sliding graph windows. We also present a distributed implementation of our approach on Apache Spark which shows great solution effectiveness and efficiency. We provide a thorough experimentation on a large variety of datasets. An application to the analysis of information propagation proves that our notion of TBC outperforms static BC in the task of identifying the best vertices for propagating information.

Original languageEnglish
Pages (from-to)257-272
Number of pages16
JournalInternational Journal of Data Science and Analytics
Volume9
Issue number3
DOIs
Publication statusPublished - Apr 2020

Fingerprint Dive into the research topics of 'Temporal betweenness centrality in dynamic graphs'. Together they form a unique fingerprint.

Cite this