2026-07-25T19:05:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9024 2024-03-06T10:43:10Z ddc:004 open_access

Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry Bläsius, Thomas Freiberger, Cedric Friedrich, Tobias Katzmann, Maximilian Montenegro-Retana, Felix Thieffry, Marianne random graphs hyperbolic geometry scale-free networks bidirectional shortest path 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 {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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Bläsius and Cedric Freiberger and Tobias Friedrich and Maximilian Katzmann and Felix Montenegro-Retana and Marianne Thieffry 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.20 urn:nbn:de:0030-drops-90246 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.20 eng https://creativecommons.org/licenses/by/3.0/legalcode