[KDD 2020] Algorithmic Aspects of Temporal Betweenness
Aug 13, 20202 views
The,betweenness centrality,of a graph vertex measures how often,this vertex is visited on shortest paths between other vertices of,the graph. In the analysis of many real-world graphs or networks,,betweenness centrality of a vertex is used as an indicator for its relative importance in the network. In recent years, a growing number,of real-world networks is modeled as,temporal graphs,instead of,conventional (static) graphs. In a temporal graph, we have a fixed,set of vertices and there is a finite discrete set of time steps and,every edge might be present only at some time steps. While shortest,paths are straightforward to define in static graphs, temporal paths,can be considered “optimal” with respect to many different criteria,,including length, arrival time, and overall travel time (shortest, foremost, and fastest paths). This leads to different concepts of,temporal,betweenness centrality,, posing new challenges on the algorithmic,side. We provide a systematic study of temporal betweenness variants based on various concepts of optimal temporal paths both on,a theoretical and empirical level.