Betweenness centrality for temporal multiplexes

Abstract

Betweenness centrality quantifies the importance of a vertex for the information flow in a network. The standard betweenness centrality applies to static single-layer networks, but many real world networks are both dynamic and made of several layers. We propose a definition of betweenness centrality for temporal multiplexes. This definition accounts for the topological and temporal structure and for the duration of paths in the determination of the shortest paths. We propose an algorithm to compute the new metric using a mapping to a static graph. We apply the metric to a dataset of [Formula: see text]k European flights and compare the results with those obtained with static or single-layer metrics. The differences in the airports rankings highlight the importance of considering the temporal multiplex structure and an appropriate distance metric.

Figure 1

Example of conversion of a temporal multiplex G (above) into the corresponding static single-layer network $\mathcal{G}$ (below). G has $M=2$ layers and $N=3$ nodes, links a, b and c have the temporal structure ($T=5$) indicated on the side ($t_i$ is the time-step during which the link appears and $t_f$ the one during which it disappears). In $\mathcal{G}$ each of the three nodes has 10 copies, one per layer and per time-step of the temporal discretization.

Figure 2

Comparison between the results obtained with the proposed betweenness centrality and with static betweenness centrality computed on the aggregated network obtained with method (i), for different values of the parameters $\alpha$ and $\epsilon$. (a) Correlation between the rankings; (b) Jaccard index between the sets of airports with zero-betweenness according to both metrics.

Figure 3

Comparison between the ranking according to the static betweenness on the aggregated network (method (i)) and the betweenness proposed here, computed with $\epsilon =1$ and $\alpha =12/13$ (panel a) and $\alpha =1$ (panel b). Each dot represents an airport, red dots are airports having $b_{\mathit{stat}}>0$ but $b=0$. The blue line is 1:1.

Figure 4

(a) Comparison between the rankings with $\epsilon =0$ and $\epsilon =1$ (for $\alpha =12/13$); (b) Comparison between the rankings with $\epsilon =1$ and $\epsilon =\infty$ (for $\alpha =12/13$) Each dot represents an airport. The red line is the 1:1 line.