Temporal Graph Algorithms
Temporal Graph Algorithms
![Open Access](/xmlui/themes/Fakultaeten//images/32px-Open_Access_logo_PLoS_white.svg.png)
dc.contributor.advisor | Mutzel, Petra | |
dc.contributor.author | Oettershagen, Lutz | |
dc.date.accessioned | 2022-07-21T14:22:42Z | |
dc.date.available | 2022-07-21T14:22:42Z | |
dc.date.issued | 21.07.2022 | |
dc.identifier.uri | https://hdl.handle.net/20.500.11811/10104 | |
dc.description.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.
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.iso | eng | |
dc.rights | In Copyright | |
dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | |
dc.subject | Temorale Graphen | |
dc.subject | Algorithmen | |
dc.subject | Temporal Graphs | |
dc.subject | Algorithms | |
dc.subject.ddc | 004 Informatik | |
dc.title | Temporal Graph Algorithms | |
dc.type | Dissertation oder Habilitation | |
dc.publisher.name | Universitäts- und Landesbibliothek Bonn | |
dc.publisher.location | Bonn | |
dc.rights.accessRights | openAccess | |
dc.identifier.urn | https://nbn-resolving.org/urn:nbn:de:hbz:5-67276 | |
ulbbn.pubtype | Erstveröffentlichung | |
ulbbnediss.affiliation.name | Rheinische Friedrich-Wilhelms-Universität Bonn | |
ulbbnediss.affiliation.location | Bonn | |
ulbbnediss.thesis.level | Dissertation | |
ulbbnediss.dissID | 6727 | |
ulbbnediss.date.accepted | 14.07.2022 | |
ulbbnediss.institute | Mathematisch-Naturwissenschaftliche Fakultät : Fachgruppe Informatik / Institut für Informatik | |
ulbbnediss.fakultaet | Mathematisch-Naturwissenschaftliche Fakultät | |
dc.contributor.coReferee | Italiano, Giuseppe F. | |
ulbbnediss.contributor.orcid | https://orcid.org/0000-0002-2526-8762 | |
ulbbnediss.contributor.gnd | 1268891614 |
Dateien zu dieser Ressource
Das Dokument erscheint in:
-
E-Dissertationen (4137)