Symposium on Networks, Time and Causality
Graph-based data analytic methods play an important role in bioinformatics, ecology, social science, information systems, and economics. Methods like graph mining, (social) network analysis, link prediction or clustering help us to detect patterns in large corpora of data that capture relationships or interactions between genes, brain regions, species, humans, documents, or financial institutions. But access to time series data allows us to capture more than just relations. Biological pathway and sequence data, time-stamped data on social interactions, user click streams in information systems, or time-resolved data on financial transactions tell us who interacts with whom, but also when and in which order interactions occur. Such data pose a fundamental challenge for network analytic methods.
9:00 - 9:15 Opening (Frank Schweitzer)
Many time-evolving systems in nature, society and technology leave traces of the interactions within them. These interactions form temporal networks that reflect the states of the systems. In this presentation, we start from briefly reviewing a "discrete-state view" of human behaviour data (e.g., an active versus quiescent state of an individual). Then, we pursue a coarse-grained description of temporal networks by proposing a method to assign discrete states and inferring the sequence of such states from the given temporal network data. Such states may, for example, correspond to a mental state (as inferred from neuroimaging data) or the operational state of an organization (as inferred by interpersonal communication). Our method combines a graph distance measure and hierarchical clustering. Using several empirical data sets of social temporal networks, we show that our method is capable of inferring the system's states such as distinct activities in a school and a weekday state as opposed to a weekend state. The methods are expected to be equally useful in other settings such as temporally varying protein interactions, ecological interspecific interactions, functional connectivity in the brain and adaptive social networks. This is joint work with Petter Holme.
Graph or network abstractions are an important foundation for the computational modeling of complex systems. They help us to model (and control) power grids, transportation and communication infrastructures, to study dynamical processes in computational physics and systems biology, to analyse social and economic networks, and to extract knowledge from large corpora of relational data. While this potential of the network perspective is undisputed, advances in data sensing and collection increasingly provide us with high-dimensional, temporal, and noisy data on real systems. The complex characteristics of such data sources pose fundamental challenges for data-driven modelling. They question the validity of network models of complex systems and pose a threat for interdisciplinary applications of data science and machine learning.
To address these challenges, I introduce graphical modelling techniques that account for the complex characteristics of real-world data on complex systems. I demonstrate this in time series data on systems with dynamic topologies. Current approaches to model the topology of such systems discard information on the timing and ordering of interactions, which however determines who can influence whom. To solve this issue, I introduce a novel statistical modelling framework that (i) generalises standard network abstractions towards multi-order graphical models, and (ii) uses principled model selection techniques to achieve an optimal balance between explanatory power and model complexity. This framework advances the theoretical foundation of data science and network analysis and sheds light on the important question when network abstractions of complex data are actually justified. It opens broad perspective for the modelling of dynamical processes in natural and engineered systems and is the basis for a new generation of data mining and machine learning techniques that account both for temporal and topological characteristics in real-world data.
10:45 -11:15 Coffee Break
Temporal networks are commonly used to represent systems where connections between elements are active only for restricted periods of time, such as telecommunication, biochemical reactions or social networks. Such time-varying interactions may be induced by local correlations between causally related events, which in turn lead to the emergence of mesoscale temporal motifs or time-respecting paths on the system level. While temporal motifs can be considered as local building blocks of the temporal structure, time respecting paths determine the possible spread of any type of information (epidemics, passengers, news) over the temporal network, and are especially important when the spreading agent has a limited lifetime at nodes. In this talk we will introduce two methods to identify temporal motifs and paths via the higher order representation of temporal graphs. First, we will provide a mapping from event sequences to coloured directed graphs that enables an efficient algorithm for identifying temporal motifs. Second, we will introduce weighted event graphs as a powerful and fast framework for studying connectivity determined by time-respecting paths where the allowed waiting times between contacts have an upper limit. We will show that the weighted event graph representation can be identified as a directed percolation problem, characterised by multiple order parameters, as we will demonstrate using large simulated and real world datasets.