The complex networks perspective has become an important methodological framework for both the modeling and analysis of complex systems. However, the vast majority of studies on complex networked systems is based on a static network perspective, in which links and nodes are ssumed to exist at any point in time. In contrast to this view, the availability of high-resolution time-stamped data on networked systems has recently validated the intuition that real complex systems are often highly dynamic, i.e. links are not active continuously but rather occur in specific temporal patterns. The following video shows two examples for temporal networks, which have the same time-aggregated topology, but different temporal patterns. The example further shows that these different temporal patterns can have dramatic effects on dynamical processes like, e.g., diffusion.
The fact that we currently lack a suitable methodological framework which integrates both the temporal and the topological dimension of complex systems severely limits the understanding of dynamic complex systems. Motivated by this limitation, empirical studies of temporal networks with time-varying topologies enter the focus of a growing research community. The few existing studies on temporal networks occurring in social, economic and technological systems have generally highlighted the presence of statistical inhomogeneities in terms of broad distributions of the waiting times between consecutive node or link activities or the duration of individual contacts. Through our own research, we recently added an important additional perspective, namely that interactions in many complex systems occur in specific temporal orders and that this ordering is essential to understand dynamical processes on temporal networks. For example in communication processes, in order for an information to be transferred from node A via node B to node C, it is crucial that the interaction between A and B happens before the interaction between B and C.
To study effects that are due to the order in which interactions occur, in our most recent research we have investigated models that preserve non-Markovian properties of contact sequences, i.e. the fact that in many real-world systems the next interaction of a node is not independent of with whom the node has interacted shortly before. We have shown that such non-Markovian properties give rise to effective interaction topologies that significantly differ from what would be expected from a static network representation. We have further demonstrated that, due to these order correlations, extrapolating findings from time-aggregated networks to time-varying networks can lead to significantly wrong statements about dynamical processes like diffusion or information propagation, as well as about the importance of individual nodes. To quantify this discrepancy, we developed an information-theoretic measure (betweenness preference) which allows to quantify the presence and strength of "preferred contact sequences" in longitudinal network data and how this influences dynamical processes. We further demonstrated the usability of this novel measure in a number of real-world data sets from social, technical and biological contexts.
Most recently, we have developed a powerful framework for the modeling and analysis of temporal networks based on so-called "higher-order aggregate networks", which can be seen as a generalisation of the static abstraction commonly used in network analysis. This approach allows to study dynamical processes in temporal networks using standard techniques like, for example, a dynamic analysis in terms of the eigenvalues of a modified Laplacian matrix, without losing information on the ordering of interactions which are hidden in the time dimension.
Our research on temporal networks has been featured in top-tier scientific journals like Physical Review Letters and Nature Communications. Our unique approach not only allows us to quantitatively study a previously unexplored temporal-topological dimension of complexity in time-stamped data. It also provides a methodological framework that offers broad perspectives for the development of new data mining and visualisation techniques which improve our ability to extract knowledge from dynamic networked systems.
Apart from this fundamental research, we are also actively involved in the actual (technical) implementation of our methods in terms of software packages. We have recently released the open source data mining package pathpy, which implements our methods. We further have a dedicated third-party funded project targeting at making our research usable in industrial applications.
Selected Publications
When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
[2017]
Scholtes, Ingo
Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, Nova Scotia, Canada
We introduce a framework for the modeling of sequential data capturing pathways of varying lengths observed in a network. Such data are important, e.g., when studying click streams in information networks, travel patterns in transportation systems, information cascades in social networks, biological pathways or time-stamped social interactions. While it is common to apply graph analytics and network analysis to such data, recent works have shown that temporal correlations can invalidate the results of such methods. This raises a fundamental question: when is a network abstraction of sequential data justified? Addressing this open question, we propose a framework which combines Markov chains of multiple, higher orders into a multi-layer graphical model that captures temporal correlations in pathways at multiple length scales simultaneously. We develop a model selection technique to infer the optimal number of layers of such a model and show that it outperforms previously used Markov order detection techniques. An application to eight real-world data sets on pathways and temporal networks shows that it allows to infer graphical models which capture both topological and temporal characteristics of such data. Our work highlights fallacies of network abstractions and provides a principled answer to the open question when they are justified. Generalizing network representations to multi-order graphical models, it opens perspectives for new data mining and knowledge discovery algorithms.
In this manuscript, we show how higher-order graphical models can be applied to study the controllability of networked systems with dynamic topologies. Studying empirical data on temporal networks, we specifically show that the order correlations in the activation sequence of links can both increase or reduce the time needed to achieve full controllability. We then demonstrate how spectral properties of higher-order graphical models can be used to analytically explain the effect of order correlations on controllability in temporal networks.
Recent research on temporal networks has highlighted the limitations of a static network perspective for our understanding of complex systems with dynamic topologies. In particular, recent works have shown that i) the specific order in which links occur in real-world temporal networks affects causality structures and thus the evolution of dynamical processes, and ii) higher-order aggregate representations of temporal networks can be used to analytically study the effect of these order correlations on dynamical processes. In this article we analyze the effect of order correlations on path-based centrality measures in real-world temporal networks. Analyzing temporal equivalents of betweenness, closeness and reach centrality in six empirical temporal networks, we first show that an analysis of the commonly used static, time-aggregated representation can give misleading results about the actual importance of nodes. We further study higher-order time-aggregated networks, a recently proposed generalization of the commonly applied static, time-aggregated representation of temporal networks. Here, we particularly define path-based centrality measures based on second-order aggregate networks, empirically validating that node centralities calculated in this way better capture the true temporal centralities of nodes than node centralities calculated based on the commonly used static (first-order) representation. Apart from providing a simple and practical method for the approximation of path-based centralities in temporal networks, our results highlight interesting perspectives for the use of higher-order aggregate networks in the analysis of time-stamped network data.
Recent research has highlighted limitations of studying complex systems with time-varying topologies from the perspective of static, time-aggregated networks. Non-Markovian characteristics resulting from the ordering of interactions in temporal networks were identified as one important mechanism that alters causality and affects dynamical processes. So far, an analytical explanation for this phenomenon and for the significant variations observed across different systems is missing. Here we introduce a methodology that allows to analytically predict causality-driven changes of diffusion speed in non-Markovian temporal networks. Validating our predictions in six data sets we show that compared with the time-aggregated network, non-Markovian characteristics can lead to both a slow-down or speed-up of diffusion, which can even outweigh the decelerating effect of community structures in the static topology. Thus, non-Markovian properties of temporal networks constitute an important additional dimension of complexity in time-varying complex systems.
When exploring the structure and function of such complex systems, the visualization of network topologies has become a standard technique.
Many - if not most - of the systems being considered are inherently dynamic and in recent years more and more data on their dynamics are becoming available in the form of so-called temporal networks.
We propose a simple mechanism that can be used to include temporal correlations present in longitudinal data on temporal networks in the layout of time-aggregated network structures.
We particularly focus on non-Markovian properties of contact sequences in temporal networks, i.e. the fact that future contacts not only depend on the current contact, but also on past contacts.
We demonstrate our approach by visualising a set of examples for temporal networks with non-Markovian properties.
The visualisations show that the resulting visualizations reveal important aspects like e.g. community structures of the dynamics which - although present in empirical data sets - a) are not represented in static, aggregate networks and b) cannot easily be seen even in dynamic visualizations of temporal networks.
Time-evolving interaction patterns studied in different contexts can be well represented bytemporal networks in which nodes are intermittently connected. In this Letter we introducethe notion of betweenness preference in the study of temporal networks. It captures how likelya certain node is to mediate interactions between particular pairs of its neighboring nodes.We argue that betweenness preference is an important correlation to consider in the analysisof temporal network data. In particular, it allows to assess to which extent paths existing intime-aggregated, static representations of temporal networks are actually feasible based onthe underlying sequence of interactions. We argue that betweenness preference correlationsare present in empirical data sets. We further show that neglecting betweenness preferencewill lead to significantly wrong statements about spreading dynamics in temporal networks.