Reachability and Spreading Processes on Temporal Networks

The static graph-based models of complex networks have enjoyed great success in describing various phenomena. Major parts of this success rely on effective methods in characterising and analysing the connectivity of the networks, which has made it possible to study phenomena such as disease and information spreading within social systems or the robustness of infrastructure networks. These methods are also used in this Thesis to show how digital contact tracing can curtail the spreading of diseases in populations with non-trivial structures such as homophily on tracing app usage and heterogeneity in the number of contacts. Despite its success, the static model falls short of providing an accurate description of a wide category of phenomena. For example, the rapidity of spreading of information or diseases in a social network depends also on the order and timing of every interaction and the evolution of the social connections over time. This necessitated the introduction of temporal networks, which use the actual interaction times as opposed to an aggregated measure of connectedness. This means that many of the algorithms, the software and the statistical physics backbone developed for understanding connectivity in graphs can not serve their essential function for temporal networks. The works presented here aim to bridge this gap by providing a solid theoretical framework—accompanied by a set of algorithms and software tools—for analysing connectivity, reachability and the outcome of spreading processes in temporal network models of complex systems. The presented algorithms enable computationally efficient estimation of reachability in large systems. This allows research on reachability at a much larger scale by turning problems that required millennia of computation time into ones that can be performed in minutes. This breakthrough made a deeper understanding of connectivity in temporal networks possible by connecting the spreading process to the well-established directed percolation universality class. This connection is shown analytically, through a mean-field approximation of connectivity, and empirically, by simulating spreading processes on synthetic and real-world temporal networks. This was made possible by representing temporal networks as event graphs, higher-order static graphs that contain a superposition of all temporal paths. The methodology and the software package presented in this Thesis make it possible for the researchers to study the connectivity of both temporal network models and data in a new theoretically grounded way. The software, algorithms and theoretical frameworks presented in this work enable a more grounded analysis of reachability and spreading processes in complex systems. This paves the path to a better understanding of a wide range of problems from the spreading of diseases and information to the accessibility of public transport.