2025 [ nach oben ]

Berger, Julian; Friedrich, Tobias; Lenzner, Pascal; Paraskevi, Voula; Ruff, Janosch Strategic Network Creation for Enabling Greedy RoutingConference on Artificial Intelligence (AAAI) 2025
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination. Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. In this paper we present the first game-theoretic network creation model that incorporates greedy routing, i.e., the strategic agents in our model are embedded in some metric space and strive for creating a network among themselves where all-pairs greedy routing is enabled. Besides this, the agents optimize their connection quality within the created network by aiming for greedy routing paths with low stretch. For our model, we analyze the existence of (approximate)-equilibria and the computational hardness in different underlying metric spaces. E.g., we characterize the set of equilibria in 1-2-metrics and tree metrics and show that Nash equilibria always exist. For Euclidean space, the setting which is most relevant in practice, we prove that equilibria are not guaranteed to exist but that the well-known \(\Theta\)-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.
@article{bflmr-aaai25, abstract = {Today we rely on networks that are created and maintained by smart devices. For such networks, there is no governing central authority but instead the network structure is shaped by the decisions of selfish intelligent agents. A key property of such communication networks is that they should be easy to navigate for routing data. For this, a common approach is greedy routing, where every device simply routes data to a neighbor that is closer to the respective destination. Networks of intelligent agents can be analyzed via a game-theoretic approach and in the last decades many variants of network creation games have been proposed and analyzed. In this paper we present the first game-theoretic network creation model that incorporates greedy routing, i.e., the strategic agents in our model are embedded in some metric space and strive for creating a network among themselves where all-pairs greedy routing is enabled. Besides this, the agents optimize their connection quality within the created network by aiming for greedy routing paths with low stretch. For our model, we analyze the existence of (approximate)-equilibria and the computational hardness in different underlying metric spaces. E.g., we characterize the set of equilibria in 1-2-metrics and tree metrics and show that Nash equilibria always exist. For Euclidean space, the setting which is most relevant in practice, we prove that equilibria are not guaranteed to exist but that the well-known \(\Theta\)-graph construction yields networks having a low stretch that are game-theoretically almost stable. For general metric spaces, we show that approximate equilibria exist where the approximation factor depends on the cost of maintaining any link.}, author = {Berger, Julian and Friedrich, Tobias and Lenzner, Pascal and Paraskevi, Voula and Ruff, Janosch}, journal = {Conference on Artificial Intelligence (AAAI)}, keywords = {aaai janoschruff julianberger paraskevimachaira pascallenzner tobiasfriedrich year2025}, title = {Strategic Network Creation for Enabling Greedy Routing}, year = 2025 }

Baguley, Samuel; Maus, Yannic Maus; Ruff, Janosch; Skretas, George Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for ColouringInternational Symposium on Theoretical Aspects of Computer Science (STACS) 2025: 13:1–13:20
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from \((2/\sqrt{3})\) to \(4/3\) depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.
@conference{bmrs-stacs25, abstract = {Hyperbolic random graphs inherit many properties that are present in real-world networks. The hyperbolic geometry imposes a scale-free network with a strong clustering coefficient. Other properties like a giant component, the small world phenomena and others follow. This motivates the design of simple algorithms for hyperbolic random graphs. In this paper we consider threshold hyperbolic random graphs (HRGs). Greedy heuristics are commonly used in practice as they deliver a good approximations to the optimal solution even though their theoretical analysis would suggest otherwise. A typical example for HRGs are degeneracy-based greedy algorithms [Bläsius, Fischbeck; Transactions of Algorithms '24]. In an attempt to bridge this theory-practice gap we characterise the parameter of degeneracy yielding a simple approximation algorithm for colouring HRGs. The approximation ratio of our algorithm ranges from \((2/\sqrt{3})\) to \(4/3\) depending on the power-law exponent of the model. We complement our findings for the degeneracy with new insights on the clique number of hyperbolic random graphs. We show that degeneracy and clique number are substantially different and derive an improved upper bound on the clique number. Additionally, we show that the core of HRGs does not constitute the largest clique. Lastly we demonstrate that the degeneracy of the closely related standard model of geometric inhomogeneous random graphs behaves inherently different compared to the one of hyperbolic random graphs.}, author = {Baguley, Samuel and Maus, Yannic Maus and Ruff, Janosch and Skretas, George}, booktitle = {International Symposium on Theoretical Aspects of Computer Science (STACS)}, keywords = {georgeskretas janoschruff samuelbaguley stacs year2025}, pages = {13:1-13:20}, title = {Hyperbolic Random Graphs: Clique Number and Degeneracy with Implications for Colouring}, year = 2025 }

2024 [ nach oben ]

Harder, Jonathan Gadea; Kötzing, Timo; Li, Xiaoyue; Radhakrishnan, Aishwarya; Ruff, Janosch Run Time Bounds for Integer-Valued OneMax FunctionsGenetic and Evolutionary Computation Conference (GECCO ’24) 2024
[ BibTeX ] [ DOI ] [ Download ]
 
@conference{2024bounds, author = {Harder, Jonathan Gadea and Kötzing, Timo and Li, Xiaoyue and Radhakrishnan, Aishwarya and Ruff, Janosch}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO '24)}, keywords = {sys:relevantfor:ae aishwaryaradhakrishnan gecco janoschruff jonathangadeaharder timokoetzing xiaoyueli year2024}, title = {Run Time Bounds for Integer-Valued OneMax Functions}, year = 2024 }

2023 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Ruff, Janosch; Zeif, Ziena On the Giant Component of Geometric Inhomogeneous Random GraphsEuropean Symposium on Algorithms (ESA) 2023: 20:1–20:13
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In this paper we study the threshold model of geometric inhomogeneous random graphs (GIRGs); a generative random graph model that is closely related to hyperbolic random graphs (HRGs). These models have been observed to capture complex real-world networks well with respect to the structural and algorithmic properties. Following comprehensive studies regarding their connectivity, i.e., which parts of the graphs are connected, we have a good understanding under which circumstances a giant component (containing a constant fraction of the graph) emerges. While previous results are rather technical and challenging to work with, the goal of this paper is to provide more accessible proofs. At the same time we significantly improve the previously known probabilistic guarantees, showing that GIRGs contain a giant component with probability \( 1 - exp(-\Omega (n^{(3-\tau )/2})) \) for graph size \(n\) and a degree distribution with power-law exponent \(\tau \in (2, 3)\). Based on that we additionally derive insights about the connectivity of certain induced subgraphs of GIRGs.
@inproceedings{blasius2023giant, abstract = {In this paper we study the threshold model of geometric inhomogeneous random graphs (GIRGs); a generative random graph model that is closely related to hyperbolic random graphs (HRGs). These models have been observed to capture complex real-world networks well with respect to the structural and algorithmic properties. Following comprehensive studies regarding their connectivity, i.e., which parts of the graphs are connected, we have a good understanding under which circumstances a giant component (containing a constant fraction of the graph) emerges. While previous results are rather technical and challenging to work with, the goal of this paper is to provide more accessible proofs. At the same time we significantly improve the previously known probabilistic guarantees, showing that GIRGs contain a giant component with probability \( 1 - exp(-\Omega (n^{(3-\tau )/2})) \) for graph size \(n\) and a degree distribution with power-law exponent \(\tau \in (2, 3)\). Based on that we additionally derive insights about the connectivity of certain induced subgraphs of GIRGs.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Ruff, Janosch and Zeif, Ziena}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {esa janoschruff maximiliankatzmann thomasblaesius tobiasfriedrich year2023 zienazeif}, pages = {20:1–20:13}, title = {On the Giant Component of Geometric Inhomogeneous Random Graphs}, year = 2023 }