Higher-order aggregate networks in the analysis of temporal networks: path structures and centralities

Despite recent advances in the study of temporal networks, the analysis of time-stamped network data is still a fundamental challenge. In particular, recent studies have shown that correlations in the ordering of links crucially alter causal topologies of temporal networks, thus invalidating analyses based on static, time-aggregated representations of time-stamped data. These findings not only highlight an important dimension of complexity in temporal networks, but also call for new network-analytic methods suitable to analyze complex systems with time-varying topologies. Addressing this open challenge, here we introduce a novel framework for the study of path-based centralities in temporal networks. Studying betweenness, closeness and reach centrality, we first show than an application of these measures to time-aggregated, static representations of temporal networks yields misleading results about the actual importance of nodes. To overcome this problem, we define path-based centralities in higher-order aggregate networks, a recently proposed generalization of the commonly used static representation of time-stamped data. Using data on six empirical temporal networks, we show that the resulting higher-order measures better capture the true, temporal centralities of nodes. Our results demonstrate that higher-order aggregate networks constitute a powerful abstraction, with broad perspectives for the design of new, computationally efficient data mining techniques for time-stamped relational data. Copyright EDP Sciences, SIF, Springer-Verlag Berlin Heidelberg 2016