TY - JOUR A1 - Friedrich, Tobias A1 - Katzmann, Maximilian A1 - Krohmer, Anton T1 - Unbounded Discrepancy of Deterministic Random Walks on Grids JF - SIAM journal on discrete mathematics N2 - Random walks are frequently used in randomized algorithms. We study a derandomized variant of a random walk on graphs called the rotor-router model. In this model, instead of distributing tokens randomly, each vertex serves its neighbors in a fixed deterministic order. For most setups, both processes behave in a remarkably similar way: Starting with the same initial configuration, the number of tokens in the rotor-router model deviates only slightly from the expected number of tokens on the corresponding vertex in the random walk model. The maximal difference over all vertices and all times is called single vertex discrepancy. Cooper and Spencer [Combin. Probab. Comput., 15 (2006), pp. 815-822] showed that on Z(d), the single vertex discrepancy is only a constant c(d). Other authors also determined the precise value of c(d) for d = 1, 2. All of these results, however, assume that initially all tokens are only placed on one partition of the bipartite graph Z(d). We show that this assumption is crucial by proving that, otherwise, the single vertex discrepancy can become arbitrarily large. For all dimensions d >= 1 and arbitrary discrepancies l >= 0, we construct configurations that reach a discrepancy of at least l. KW - deterministic random walk KW - rotor-router model KW - single vertex discrepancy Y1 - 2018 U6 - https://doi.org/10.1137/17M1131088 SN - 0895-4801 SN - 1095-7146 VL - 32 IS - 4 SP - 2441 EP - 2452 PB - Society for Industrial and Applied Mathematics CY - Philadelphia ER - TY - THES A1 - Katzmann, Maximilian T1 - About the analysis of algorithms on networks with underlying hyperbolic geometry T1 - Über die Analyse von Algorithmen auf Netzwerken mit zugrundeliegender hyperbolischer Geometrie N2 - Many complex systems that we encounter in the world can be formalized using networks. Consequently, they have been in the focus of computer science for decades, where algorithms are developed to understand and utilize these systems. Surprisingly, our theoretical understanding of these algorithms and their behavior in practice often diverge significantly. In fact, they tend to perform much better on real-world networks than one would expect when considering the theoretical worst-case bounds. One way of capturing this discrepancy is the average-case analysis, where the idea is to acknowledge the differences between practical and worst-case instances by focusing on networks whose properties match those of real graphs. Recent observations indicate that good representations of real-world networks are obtained by assuming that a network has an underlying hyperbolic geometry. In this thesis, we demonstrate that the connection between networks and hyperbolic space can be utilized as a powerful tool for average-case analysis. To this end, we first introduce strongly hyperbolic unit disk graphs and identify the famous hyperbolic random graph model as a special case of them. We then consider four problems where recent empirical results highlight a gap between theory and practice and use hyperbolic graph models to explain these phenomena theoretically. First, we develop a routing scheme, used to forward information in a network, and analyze its efficiency on strongly hyperbolic unit disk graphs. For the special case of hyperbolic random graphs, our algorithm beats existing performance lower bounds. Afterwards, we use the hyperbolic random graph model to theoretically explain empirical observations about the performance of the bidirectional breadth-first search. Finally, we develop algorithms for computing optimal and nearly optimal vertex covers (problems known to be NP-hard) and show that, on hyperbolic random graphs, they run in polynomial and quasi-linear time, respectively. Our theoretical analyses reveal interesting properties of hyperbolic random graphs and our empirical studies present evidence that these properties, as well as our algorithmic improvements translate back into practice. N2 - Viele komplexe Systeme mit denen wir tagtäglich zu tun haben, können mit Hilfe von Netzwerken beschrieben werden, welche daher schon jahrzehntelang im Fokus der Informatik stehen. Dort werden Algorithmen entwickelt, um diese Systeme besser verstehen und nutzen zu können. Überraschenderweise unterscheidet sich unsere theoretische Vorstellung dieser Algorithmen jedoch oft immens von derem praktischen Verhalten. Tatsächlich neigen sie dazu auf echten Netzwerken viel effizienter zu sein, als man im schlimmsten Fall erwarten würde. Eine Möglichkeit diese Diskrepanz zu erfassen ist die Average-Case Analyse bei der man die Unterschiede zwischen echten Instanzen und dem schlimmsten Fall ausnutzt, indem ausschließlich Netzwerke betrachtet werden, deren Eigenschaften die von echten Graphen gut abbilden. Jüngste Beobachtungen zeigen, dass gute Abbildungen entstehen, wenn man annimmt, dass einem Netzwerk eine hyperbolische Geometrie zugrunde liegt. In dieser Arbeit wird demonstriert, dass hyperbolische Netzwerke als mächtiges Werkzeug der Average-Case Analyse dienen können. Dazu werden stark-hyperbolische Unit-Disk-Graphen eingeführt und die bekannten hyperbolischen Zufallsgraphen als ein Sonderfall dieser identifiziert. Anschließend werden auf diesen Modellen vier Probleme analysiert, um Resultate vorangegangener Experimente theoretisch zu erklären, die eine Diskrepanz zwischen Theorie und Praxis aufzeigten. Zuerst wird ein Routing Schema zum Transport von Nachrichten entwickelt und dessen Effizienz auf stark-hyperbolischen Unit-Disk-Graphen untersucht. Allgemeingültige Effizienzschranken können so auf hyperbolischen Zufallsgraphen unterboten werden. Anschließend wird das hyperbolische Zufallsgraphenmodell verwendet, um praktische Beobachtungen der bidirektionalen Breitensuche theoretisch zu erklären und es werden Algorithmen entwickelt, um optimale und nahezu optimale Knotenüberdeckungen zu berechnen (NP-schwer), deren Laufzeit auf diesen Graphen jeweils polynomiell und quasi-linear ist. In den Analysen werden neue Eigenschaften von hyperbolischen Zufallsgraphen aufgedeckt und empirisch gezeigt, dass sich diese sowie die algorithmischen Verbesserungen auch auf echten Netzwerken nachweisen lassen. KW - graph theory KW - hyperbolic geometry KW - average-case analysis KW - Average-Case Analyse KW - Graphentheorie KW - hyperbolische Geometrie Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-582965 ER - TY - JOUR A1 - Bläsius, Thomas A1 - Freiberger, Cedric A1 - Friedrich, Tobias A1 - Katzmann, Maximilian A1 - Montenegro-Retana, Felix A1 - Thieffry, Marianne T1 - Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry JF - ACM Transactions on Algorithms N2 - A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice this strategy performs particularly well on scale-free real-world networks. Such networks typically have a heterogeneous degree distribution (e.g., a power-law distribution) and high clustering (i.e., vertices with a common neighbor are likely to be connected themselves). These two properties can be obtained by assuming an underlying hyperbolic geometry.
To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is (O) over tilde (n(2-1/alpha) + n(1/(2 alpha)) + delta(max)) with high probability, where alpha is an element of (1/2, 1) controls the power-law exponent of the degree distribution, and dmax is the maximum degree. This bound is sublinear, improving the obvious worst-case linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it. KW - Random graphs KW - hyperbolic geometry KW - scale-free networks KW - bidirectional shortest path Y1 - 2022 U6 - https://doi.org/10.1145/3516483 SN - 1549-6325 SN - 1549-6333 VL - 18 IS - 2 SP - 1 EP - 32 PB - Association for Computing Machinery CY - New York ER -