Show simple item record

Temporal Graph Algorithms

dc.contributor.advisorMutzel, Petra
dc.contributor.authorOettershagen, Lutz
dc.date.accessioned2022-07-21T14:22:42Z
dc.date.available2022-07-21T14:22:42Z
dc.date.issued21.07.2022
dc.identifier.urihttps://hdl.handle.net/20.500.11811/10104
dc.description.abstractTemporal 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.
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 Temporal Walk Centrality 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 Substream index and show that deciding if there exists a Substream 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 dissemination processes 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.
en
dc.language.isoeng
dc.rightsIn Copyright
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectTemorale Graphen
dc.subjectAlgorithmen
dc.subjectTemporal Graphs
dc.subjectAlgorithms
dc.subject.ddc004 Informatik
dc.titleTemporal Graph Algorithms
dc.typeDissertation oder Habilitation
dc.publisher.nameUniversitäts- und Landesbibliothek Bonn
dc.publisher.locationBonn
dc.rights.accessRightsopenAccess
dc.identifier.urnhttps://nbn-resolving.org/urn:nbn:de:hbz:5-67276
ulbbn.pubtypeErstveröffentlichung
ulbbnediss.affiliation.nameRheinische Friedrich-Wilhelms-Universität Bonn
ulbbnediss.affiliation.locationBonn
ulbbnediss.thesis.levelDissertation
ulbbnediss.dissID6727
ulbbnediss.date.accepted14.07.2022
ulbbnediss.instituteMathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Informatik / Institut für Informatik
ulbbnediss.fakultaetMathematisch-Naturwissenschaftliche Fakultät
dc.contributor.coRefereeItaliano, Giuseppe F.
ulbbnediss.contributor.orcidhttps://orcid.org/0000-0002-2526-8762
ulbbnediss.contributor.gnd1268891614


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

The following license files are associated with this item:

InCopyright