Temporal Graph Algorithms

Abstract

Temporal graphs are often good models for real-life scenarios due to the inherently dynamic nature of most real-world activities and processes. A significant difference between conventional static and temporal graphs is the induced order of the edges in walks and paths. In a temporal walk, at each vertex, the time stamp of the next edge of the walk cannot be earlier than the arrival time at the vertex. We present temporal graph algorithms to analyze temporal graphs that make use of temporal walks or paths. There is a need for algorithms designed explicitly for temporal graphs because the interpretation as, or aggregation into, a static graph model is often not an appropriate solution for handling the temporal dynamics. The reason is that static interpretation and aggregation often lead to a loss of causal information. <br> Hence, we introduce algorithms and tools specifically designed for analyzing temporal networks such as, e.g., dynamic social network data, human contact graphs, or communication networks. We introduce an efficient top-$k$ algorithm for temporal closeness and lift an approximation for the temporal closeness to the temporal domain. The temporal closeness of a vertex is the sum of the reciprocals of the durations of the fastest paths to all other vertices. Furthermore, we present the <em>Temporal Walk Centrality</em> that ranks vertices according to their ability to pass information. We demonstrate that vertices with high temporal walk centrality are key players in disseminating information and present efficient and scalable algorithms for the computation of temporal walk centrality. Next, we introduce an index to speed up single-source-all-destination (SSAD) temporal distance queries. We call our index <em>Substream</em> index and show that deciding if there exists a <em>Substream</em> index of a given size is NP-complete. We provide an approximation and a greedy algorithm for computing the index and show their efficiency and effectiveness. Furthermore, we consider the classification of <em>dissemination processes</em> on temporal graphs, such as the spread of rumors, fake news, or diseases. We introduce a framework to lift standard graph kernels and graph-based neural networks to the temporal domain. We explore three different approaches and investigate the trade-offs between loss of temporal information and efficiency. Finally, we discuss the complexity of temporal path enumeration and counting in weighted temporal graphs. In a weighted temporal graph, each edge has an additional real cost value. We introduce two bicriteria temporal min-cost path problems. We are interested in the set of all efficient paths with low cost and short duration or early arrival time, respectively. We show that the efficient paths can be enumerated with polynomial delay.