Eur. Phys. J. B (2016) 89: 61
https://doi.org/10.1140/epjb/e2016-60663-0

Regular Article

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

ETH Zürich, Chair of Systems Design, Weinbergstrasse 56/58, 8092 Zürich, Switzerland

^a e-mail: ischoltes@ethz.ch

Received: 10 August 2015
Received in final form: 18 January 2016
Published online: 2 March 2016

Abstract

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.