2020 [ nach oben ]

Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian Solving Vertex Cover in Polynomial Time on Hyperbolic Random GraphsSymposium on the Theoretical Aspects of Computer Science (STACS) 2020: 25:1–25:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that this leads to even better approximations than the standard greedy approach on real instances.
@inproceedings{blasius2020solving, abstract = {The VertexCover problem is proven to be computationally hard in different ways: It is NP-complete to find an optimal solution and even NP-hard to find an approximation with reasonable factors. In contrast, recent experiments suggest that on many real-world networks the run time to solve VertexCover is way smaller than even the best known FPT-approaches can explain. Similarly, greedy algorithms deliver very good approximations to the optimal solution in practice. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that, on real instances, this leads to better approximations than the standard greedy approach within reasonable time. We link these observations to two properties that are observed in many real-world networks, namely a heterogeneous degree distribution and high clustering. To formalize these properties and explain the observed behavior, we analyze how a branch-and-reduce algorithm performs on hyperbolic random graphs, which have become increasingly popular for modeling real-world networks. In fact, we are able to show that the VertexCover problem on hyperbolic random graphs can be solved in polynomial time, with high probability. The proof relies on interesting structural properties of hyperbolic random graphs. Since these predictions of the model are interesting in their own right, we conducted experiments on real-world networks showing that these properties are also observed in practice. When utilizing the same structural properties in an adaptive greedy algorithm, further experiments suggest that this leads to even better approximations than the standard greedy approach on real instances.}, author = {Bläsius, Thomas and Fischbeck, Philipp and Friedrich, Tobias and Katzmann, Maximilian}, booktitle = {Symposium on the Theoretical Aspects of Computer Science (STACS)}, keywords = {hyperbolic_analysis maximiliankatzmann philippfischbeck stacs thomasblaesius tobiasfriedrich year2020}, pages = {25:1-25:14}, title = {Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs}, year = 2020 }

2018 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton Cliques in Hyperbolic Random GraphsAlgorithmica 2018: 2324–2344
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Krioukov et al. and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E[K_k]\) and the size of the largest clique \(\omega(G)\). We observe that there is a phase transition at power-law exponent \(\beta = 3\). More precisely, for \(\beta\)\(\in\)\((2,3)\) we prove \(E[K_k] = \) \(n^{k(3-\beta)/2} \Theta(k)^{-k}\) and \(\omega(G) = \) \(\Theta\)\((n^{(3-\beta)/2})\), while for \(\beta \geq 3\) we prove \(E[K_k]=n \Theta(k)^{-k}\) and \(\omega(G)=\Theta(\log(n)/ \log\log n)\). Furthermore, we show that for \(\beta \geq 3\), cliques in hyperbolic random graphs can be computed in time \(O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime \(O(m n^{2.5})\) for all values of \(\beta\).
@article{journals/algorithmica/Blasius0K18, abstract = {Most complex real world networks display scale-free features. This characteristic motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Krioukov et al. and has shown theoretically and empirically to fulfill all typical properties of real world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E[K_k]\) and the size of the largest clique \(\omega(G)\). We observe that there is a phase transition at power-law exponent \(\beta = 3\). More precisely, for \(\beta\)\(\in\)\((2,3)\) we prove \(E[K_k] = \) \(n^{k(3-\beta)/2} \Theta(k)^{-k}\) and \(\omega(G) = \) \(\Theta\)\((n^{(3-\beta)/2})\), while for \(\beta \geq 3\) we prove \(E[K_k]=n \Theta(k)^{-k}\) and \(\omega(G)=\Theta(\log(n)/ \log\log n)\). Furthermore, we show that for \(\beta \geq 3\), cliques in hyperbolic random graphs can be computed in time \(O(n)\). If the underlying geometry is known, cliques can be found with worst-case runtime \(O(m n^{2.5})\) for all values of \(\beta\).}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton}, journal = {Algorithmica}, keywords = {algorithmica antonkrohmer hyperbolic_analysis thomasblaesius tobiasfriedrich year2018}, pages = {2324-2344}, title = {Cliques in Hyperbolic Random Graphs}, volume = 80, year = 2018 }

Friedrich, Tobias; Krohmer, Anton On the diameter of hyperbolic random graphsSIAM Journal on Discrete Mathematics 2018: 1314–1334
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing is close to optimal (Boguñá, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation has pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power law degree distribution with controllable exponent \(\beta\) and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573–585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is \(O(\)\((\log n)\)\(^{32/((3 - \beta)(5 - \beta))+1})\)(Kiwi and Mitsche. ANALCO, pp. 26–39, 2015). We present two much simpler proofs for an improved upper bound of \(O((\log n)\)\(^{2/(3 - \beta)})\) and a lower bound of \(\Omega(\log n)\). If \(\beta > 3\), we show that the latter bound is tight by proving an upper bound of \(O(\log n)\) for the diameter.
@article{friedrich2018diameter, abstract = {Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing is close to optimal (Boguñá, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation has pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power law degree distribution with controllable exponent \(\beta\) and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573–585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is \(O(\)\((\log n)\)\(^{32/((3 - \beta)(5 - \beta))+1})\)(Kiwi and Mitsche. ANALCO, pp. 26–39, 2015). We present two much simpler proofs for an improved upper bound of \(O((\log n)\)\(^{2/(3 - \beta)})\) and a lower bound of \(\Omega(\log n)\). If \(\beta > 3\), we show that the latter bound is tight by proving an upper bound of \(O(\log n)\) for the diameter.}, author = {Friedrich, Tobias and Krohmer, Anton}, journal = {SIAM Journal on Discrete Mathematics}, keywords = {antonkrohmer hyperbolic_analysis sidma tobiasfriedrich year2018}, number = 2, pages = {1314-1334}, publisher = {SIAM}, title = {On the diameter of hyperbolic random graphs}, volume = 32, year = 2018 }

Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, Marianne Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic GeometryInternational Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1–20:14
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that 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 \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) 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.
@inproceedings{blasius2018efficient, abstract = {A common way to accelerate shortest path algorithms on graphs is the use of a bidirectional search, which simultaneously explores the graph from the start and the destination. It has been observed recently that 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 \(\tilde{O}(n\)\(^{2 - 1/ \alpha}+\)\(n^{1/(2\alpha)}\)\(+ \delta_{\max})\) with high probability, where \(\alpha\)\(\in\)\((0.5, 1)\) controls the power-law exponent of the degree distribution, and \(\delta_{\max}\) 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.}, author = {Bläsius, Thomas and Freiberger, Cedric and Friedrich, Tobias and Katzmann, Maximilian and Montenegro-Retana, Felix and Thieffry, Marianne}, booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)}, keywords = {cedricfreiberger felixmontenegroretana hyperbolic_analysis icalp mariannethieffry maximiliankatzmann thomasblaesius tobiasfriedrich year2018}, pages = {20:1-20:14}, title = {Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry}, volume = 107, year = 2018 }

2016 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton Hyperbolic Random Graphs: Separators and TreewidthEuropean Symposium on Algorithms (ESA) 2016: 15:1–15:16
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
When designing and analyzing algorithms, one can obtain better and more realistic results for practical instances by assuming a certain probability distribution on the input. The worst-case run-time is then replaced by the expected run-time or by bounds that hold with high probability (whp), i.e., with probability \(1 - O(1/n)\), on the random input. Hyperbolic random graphs can be used to model complex real-world networks as they share many important properties such as a small diameter, a large clustering coefficient, and a power-law degree-distribution. Divide and conquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that a hyperbolic random graph can be expected to have a balanced separator hierarchy with separators of size \(O(\sqrt{n^{(3-\beta)}})\), \(O(\log n)\), and \(O(1)\) if \(2 < \beta < 3\), \(\beta = 3\) and \(3 < \beta\), respectively (\(\beta\) is the power-law exponent). We infer that these graphs have whp a treewidth of \(O(\sqrt{n^{(3 - \beta)}})\), \(O(\log^{2}n)\), and \(O(\log n)\), respectively. For \(2 < \beta < 3\), this matches a known lower bound. For the more realistic (but harder to analyze) binomial model, we still prove a sublinear bound on the treewidth. To demonstrate the usefulness of our results, we apply them to obtain fast matching algorithms and an approximation scheme for Independent Set.
@inproceedings{DBLP:conf/esa/BlasiusFK16, abstract = {When designing and analyzing algorithms, one can obtain better and more realistic results for practical instances by assuming a certain probability distribution on the input. The worst-case run-time is then replaced by the expected run-time or by bounds that hold with high probability (whp), i.e., with probability \(1 - O(1/n)\), on the random input. Hyperbolic random graphs can be used to model complex real-world networks as they share many important properties such as a small diameter, a large clustering coefficient, and a power-law degree-distribution. Divide and conquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that a hyperbolic random graph can be expected to have a balanced separator hierarchy with separators of size \(O(\sqrt{n^{(3-\beta)}})\), \(O(\log n)\), and \(O(1)\) if \(2 < \beta < 3\), \(\beta = 3\) and \(3 < \beta\), respectively (\(\beta\) is the power-law exponent). We infer that these graphs have whp a treewidth of \(O(\sqrt{n^{(3 - \beta)}})\), \(O(\log^{2}n)\), and \(O(\log n)\), respectively. For \(2 < \beta < 3\), this matches a known lower bound. For the more realistic (but harder to analyze) binomial model, we still prove a sublinear bound on the treewidth. To demonstrate the usefulness of our results, we apply them to obtain fast matching algorithms and an approximation scheme for Independent Set.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {ESA antonkrohmer hyperbolic_analysis thomasblaesius tobiasfriedrich year2016}, pages = {15:1-15:16}, title = {Hyperbolic Random Graphs: Separators and Treewidth}, year = 2016 }

2015 [ nach oben ]

Friedrich, Tobias; Krohmer, Anton On the Diameter of Hyperbolic Random GraphsInternational Colloquium on Automata, Languages and Programming (ICALP) 2015: 614–625
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing performs close to optimal (Boguna, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent \(\beta\) and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is \(O((\log n)\)\(^{32/((3-\beta)(5-\beta))})\) (Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of \(O((\log n)\)\(^{2/(3-\beta)})\) and a lower bound of \(\Omega(\log n)\). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of \(O(\log n)\).
@inproceedings{DBLP:conf/icalp/FriedrichK15, abstract = {Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing performs close to optimal (Boguna, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent \(\beta\) and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 2012). For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known explicit bound is \(O((\log n)\)\(^{32/((3-\beta)(5-\beta))})\) (Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of \(O((\log n)\)\(^{2/(3-\beta)})\) and a lower bound of \(\Omega(\log n)\). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of \(O(\log n)\).}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Colloquium on Automata, Languages and Programming (ICALP)}, keywords = {antonkrohmer hyperbolic_analysis icalp imported tobiasfriedrich year2015}, pages = {614-625}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, title = {On the Diameter of Hyperbolic Random Graphs}, volume = 9135, year = 2015 }

Friedrich, Tobias; Krohmer, Anton Cliques in Hyperbolic Random GraphsInternational Conference on Computer Communications (INFOCOM) 2015: 1544–1552
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Papadopoulos, Krioukov, Boguna, Vahdat (INFOCOM, pp. 2973-2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E[K_k]\) and the size of the largest clique \(\omega(G)\). We observe that there is a phase transition at power-law exponent \(\gamma = 3\). More precisely, for \(\gamma\) \(\in\) \((2,3)\) we prove \(E[K_k] = \)\(n^{k(3-\gamma)/2}\)\(\Theta(k)^{-k}\) and \(\omega(G) = \)\(\Theta(\)\(n^{(3-\gamma)/2})\) while for \(\gamma \ge 3\) we prove \(E[K_k] = n \Theta(k)^{-k}\) and \(\omega(G) = \Theta(\log(n)/\log \log n)\). We empirically compare the \(\omega(G)\) value of several scale-free random graph models with real-world networks. Our experiments show that the \(\omega(G)\)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.
@inproceedings{DBLP:conf/infocom/FriedrichK15, abstract = {Most complex real-world networks display scale-free features. This motivated the study of numerous random graph models with a power-law degree distribution. There is, however, no established and simple model which also has a high clustering of vertices as typically observed in real data. Hyperbolic random graphs bridge this gap. This natural model has recently been introduced by Papadopoulos, Krioukov, Boguna, Vahdat (INFOCOM, pp. 2973-2981, 2010) and has shown theoretically and empirically to fulfill all typical properties of real-world networks, including power-law degree distribution and high clustering. We study cliques in hyperbolic random graphs \(G\) and present new results on the expected number of \(k\)-cliques \(E[K_k]\) and the size of the largest clique \(\omega(G)\). We observe that there is a phase transition at power-law exponent \(\gamma = 3\). More precisely, for \(\gamma\) \(\in\) \((2,3)\) we prove \(E[K_k] = \)\(n^{k(3-\gamma)/2}\)\(\Theta(k)^{-k}\) and \(\omega(G) = \)\(\Theta(\)\(n^{(3-\gamma)/2})\) while for \(\gamma \ge 3\) we prove \(E[K_k] = n \Theta(k)^{-k}\) and \(\omega(G) = \Theta(\log(n)/\log \log n)\). We empirically compare the \(\omega(G)\) value of several scale-free random graph models with real-world networks. Our experiments show that the \(\omega(G)\)-predictions by hyperbolic random graphs are much closer to the data than other scale-free random graph models.}, author = {Friedrich, Tobias and Krohmer, Anton}, booktitle = {International Conference on Computer Communications (INFOCOM)}, keywords = {antonkrohmer hyperbolic_analysis imported infocom tobiasfriedrich year2015}, pages = {1544-1552}, title = {Cliques in Hyperbolic Random Graphs}, year = 2015 }

2020 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Hyperbolic Embeddings for Near-Optimal Greedy RoutingJournal of Experimental Algorithmics (JEA) 2020: 1–18
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular, our embeddings guarantee that greedy routing always succeeds in reaching the target, and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real-world networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results (i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths). In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention. In addition to measuring the stretch, we empirically evaluate our algorithms regarding the size of the coordinates of the resulting embeddings and observe how it impacts the success rate when coordinates are not represented with very high precision. Since numerical difficulties are a major issue when performing computations in the hyperbolic plane, we consider variations of our algorithm that improve the success rate when using coordinates with lower precision.
@article{blasius2020hyperbolic, abstract = {Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular, our embeddings guarantee that greedy routing always succeeds in reaching the target, and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real-world networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results (i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths). In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention. In addition to measuring the stretch, we empirically evaluate our algorithms regarding the size of the coordinates of the resulting embeddings and observe how it impacts the success rate when coordinates are not represented with very high precision. Since numerical difficulties are a major issue when performing computations in the hyperbolic plane, we consider variations of our algorithm that improve the success rate when using coordinates with lower precision.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, journal = {Journal of Experimental Algorithmics (JEA)}, keywords = {antonkrohmer hyperbolic_embedding jea maximiliankatzmann thomasblaesius tobiasfriedrich year2020}, month = {March}, number = {1.3}, pages = {1-18}, title = {Hyperbolic Embeddings for Near-Optimal Greedy Routing}, volume = 25, year = 2020 }

2018 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, Sören Efficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneIEEE/ACM Transactions on Networking 2018: 920–933
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require at least a quadratic runtime. Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics, like Log-likelihood and greedy routing, our algorithm discovers embeddings that are very close to the ground truth.
@article{journals/ton/BlasiusFKL18, abstract = {Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require at least a quadratic runtime. Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics, like Log-likelihood and greedy routing, our algorithm discovers embeddings that are very close to the ground truth.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, Sören}, journal = {IEEE/ACM Transactions on Networking}, keywords = {antonkrohmer hyperbolic_embedding thomasblaesius tobiasfriedrich transnetw year2018}, number = {1-57570FN}, pages = {920-933}, publisher = {IEEE & ACM}, title = {Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}, volume = 26, year = 2018 }

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton Hyperbolic Embeddings for Near-Optimal Greedy RoutingAlgorithm Engineering and Experiments (ALENEX) 2018: 199–208
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.
@inproceedings{btkk2018hyperbolic, abstract = {Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths. We evaluate our algorithm on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph, we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only \(6\%\) longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton}, booktitle = {Algorithm Engineering and Experiments (ALENEX)}, keywords = {alenex antonkrohmer hyperbolic_embedding maximiliankatzmann thomasblaesius tobiasfriedrich year2018}, pages = {199-208}, title = {Hyperbolic Embeddings for Near-Optimal Greedy Routing}, year = 2018 }

2016 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Krohmer, Anton; Laue, Sören Efficient Embedding of Scale-Free Graphs in the Hyperbolic PlaneEuropean Symposium on Algorithms (ESA) 2016: 16:1–16:18
EATCS Best Paper Award
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of \(\Omega(n^{2})\). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.
@inproceedings{DBLP:conf/esa/BlasiusFKL16, abstract = {Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of \(\Omega(n^{2})\). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.}, author = {Bläsius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, Sören}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {ESA antonkrohmer bestpaper hyperbolic_embedding thomasblaesius tobiasfriedrich year2016}, note = {EATCS Best Paper Award}, pages = {16:1-16:18}, title = {Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}, year = 2016 }

2019 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Meyer, Ulrich; Penschuck, Manuel; Weyand, Christopher Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random GraphsEuropean Symposium on Algorithms (ESA) 2019: 21:2–21:14
EATCS Best Paper Award
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.
@inproceedings{blaesius2019efficiently, abstract = {Hyperbolic random graphs (HRG) and geometric inhomogeneous random graphs (GIRG) are two similar generative network models that were designed to resemble complex real world networks. In particular, they have a power-law degree distribution with controllable exponent \(\beta\), and high clustering that can be controlled via the temperature \(T\). We present the first implementation of an efficient GIRG generator running in expected linear time. Besides varying temperatures, it also supports underlying geometries of higher dimensions. It is capable of generating graphs with ten million edges in under a second on commodity hardware. The algorithm can be adapted to HRGs. Our resulting implementation is the fastest sequential HRG generator, despite the fact that we support non-zero temperatures. Though non-zero temperatures are crucial for many applications, most existing generators are restricted to \(T = 0\). We also support parallelization, although this is not the focus of this paper. Moreover, we note that our generators draw from the correct probability distribution, i.e., they involve no approximation. Besides the generators themselves, we also provide an efficient algorithm to determine the non-trivial dependency between the average degree of the resulting graph and the input parameters of the GIRG model. This makes it possible to specify \(\bar{d}\) as input and obtain a graph with expected average degree \(\bar{d}\). Moreover, we investigate the differences between HRGs and GIRGs, shedding new light on the nature of the relation between the two models. Although HRGs represent, in a certain sense, a special case of the GIRG model, we find that a straight-forward inclusion does not hold in practice. However, the difference is negligible for most use cases.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Meyer, Ulrich and Penschuck, Manuel and Weyand, Christopher}, booktitle = {European Symposium on Algorithms (ESA)}, keywords = {christopherweyand esa hyperbolic_generation manuelpenschuck maximiliankatzmann thomasblaesius tobiasfriedrich ulrichmeyer year2019}, note = {EATCS Best Paper Award}, pages = {21:2-21:14}, title = {Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs}, year = 2019 }

2024 [ nach oben ]

Bläsius, Thomas; Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S. Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic ApproximationCoRR 2024
ArXiv preprint
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive. We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erdős-Rényi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations.
@article{blasius2024robust, abstract = {Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive. We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erdős-Rényi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations.}, author = {Bläsius, Thomas and Cohen, Sarel and Fischbeck, Philipp and Friedrich, Tobias and Krejca, Martin S.}, journal = {CoRR}, keywords = {sarelcohen philippfischbeck thomasblaesius martinskrejca tobiasfriedrich year2024 arxiv}, note = {ArXiv preprint}, title = {Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation}, volume = {arXiv:2402.05534}, year = 2024 }

2022 [ nach oben ]

Böther, Maximilian; Kißig, Otto; Taraz, Martin; Cohen, Sarel; Seidel, Karen; Friedrich, Tobias What’s Wrong with Deep Learning in Tree Search for Combinatorial OptimizationInternational Conference on Learning Representations (ICLR) 2022
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.
@inproceedings{bother2022whats, abstract = {Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.}, author = {Böther, Maximilian and Kißig, Otto and Taraz, Martin and Cohen, Sarel and Seidel, Karen and Friedrich, Tobias}, booktitle = {International Conference on Learning Representations (ICLR)}, keywords = {maximilianboether sarelcohen ottokissig tobiasfriedrich martintaraz year2022 iclr karenseidel}, title = {What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization}, year = 2022 }

2019 [ nach oben ]

Friedrich, Tobias From Graph Theory to Network Science: The Natural Emergence of HyperbolicitySymposium Theoretical Aspects of Computer Science (STACS) 2019: 5:1–5:9
[ Abstract ] [ BibTeX ] [ DOI ] [ Download ]
 
Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scale-free networks. The connection between hyperbolic geometry and complex networks gives insights in both directions: (1) Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties for example with online social networks like Facebook or Twitter. They are thus well suited for algorithmic analyses in a more realistic setting. (2) Starting with a real-world network, hyperbolic geometry is well-suited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions.
@inproceedings{friedrich2019graph, abstract = {Network science is driven by the question which properties large real-world networks have and how we can exploit them algorithmically. In the past few years, hyperbolic graphs have emerged as a very promising model for scale-free networks. The connection between hyperbolic geometry and complex networks gives insights in both directions: (1) Hyperbolic geometry forms the basis of a natural and explanatory model for real-world networks. Hyperbolic random graphs are obtained by choosing random points in the hyperbolic plane and connecting pairs of points that are geometrically close. The resulting networks share many structural properties for example with online social networks like Facebook or Twitter. They are thus well suited for algorithmic analyses in a more realistic setting. (2) Starting with a real-world network, hyperbolic geometry is well-suited for metric embeddings. The vertices of a network can be mapped to points in this geometry, such that geometric distances are similar to graph distances. Such embeddings have a variety of algorithmic applications ranging from approximations based on efficient geometric algorithms to greedy routing solely using hyperbolic coordinates for navigation decisions.}, author = {Friedrich, Tobias}, booktitle = {Symposium Theoretical Aspects of Computer Science (STACS)}, keywords = {year2019 stacs tobiasfriedrich}, pages = {5:1–5:9}, title = {From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity}, year = 2019 }

2018 [ nach oben ]

Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian; Krohmer, Anton; Striebel, Jonathan Towards a Systematic Evaluation of Generative Network ModelsWorkshop on Algorithms and Models for the Web Graph (WAW) 2018: 99–114
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.
@inproceedings{blasius2018towards, abstract = {Generative graph models play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. The explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graph models (Erdős-Rényi, Barabási-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.}, author = {Bläsius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Krohmer, Anton and Striebel, Jonathan}, booktitle = {Workshop on Algorithms and Models for the Web Graph (WAW)}, keywords = {jonathanstriebel thomasblaesius year2018 tobiasfriedrich antonkrohmer maximiliankatzmann waw}, pages = {99-114}, title = {Towards a Systematic Evaluation of Generative Network Models}, year = 2018 }