Document Open Access Logo

Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry

Authors Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.20.pdf
  • Filesize: 0.77 MB
  • 14 pages

Document Identifiers

Author Details

Thomas Bläsius
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Cedric Freiberger
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Maximilian Katzmann
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Felix Montenegro-Retana
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
Marianne Thieffry
  • Hasso Plattner Institute, University of Potsdam, Potsdam, Germany

Cite As Get BibTex

Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, and Marianne Thieffry. Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.20

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 {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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
  • Theory of computation → Random network models
  • Theory of computation → Computational geometry
Keywords
  • random graphs
  • hyperbolic geometry
  • scale-free networks
  • bidirectional shortest path

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Gregorio Alanis-Lobato, Pablo Mier, and Miguel A. Andrade-Navarro. Manifold learning and maximum likelihood estimation for hyperbolic network embedding. Applied Network Science, 1(10):1-14, 2016. URL: http://dx.doi.org/10.1007/s41109-016-0013-0.
  2. Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic random graphs: Separators and treewidth. In 24th ESA, volume 57 of LIPIcs, pages 15:1-15:16, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.15.
  3. Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Cliques in hyperbolic random graphs. Algorithmica, 80:1-21, 2017. URL: http://dx.doi.org/10.1007/s00453-017-0323-3.
  4. Michel Bode, Nikolaos Fountoulakis, and Tobias Müller. On the giant component of random hyperbolic graphs. In 7th EuroComb, pages 425-429, 2013. URL: http://dx.doi.org/10.1007/978-88-7642-475-5_68.
  5. Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nature Communications, 1:1-8, 2010. URL: http://dx.doi.org/10.1038/ncomms1063.
  6. Michele Borassi and Emanuele Natale. KADABRA is an adaptive algorithm for betweenness via random approximation. In 24th ESA, pages 20:1-20:18, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.20.
  7. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Average distance in a general class of scale-free networks with underlying geometry. CoRR, abs/1602.05712, 2016. URL: http://arxiv.org/abs/1602.05712.
  8. Karl Bringmann, Ralph Keusch, and Johannes Lengler. Sampling geometric inhomogeneous random graphs in linear time. In 25th ESA, volume 87 of LIPIcs, pages 20:1-20:15, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.20.
  9. Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, and Anisur Rahaman Molla. Greedy routing and the algorithmic small-world phenomenon. In PODC '17, pages 371-380, 2017. URL: http://dx.doi.org/10.1145/3087801.3087829.
  10. Devdatt P. Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2012. Google Scholar
  11. Tobias Friedrich and Anton Krohmer. On the diameter of hyperbolic random graphs. In 42nd ICALP, pages 614-625, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_49.
  12. Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: Degree sequence and clustering. In 39th ICALP, pages 573-585, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31585-5_51.
  13. Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, 2010. URL: http://dx.doi.org/10.1103/PhysRevE.82.036106.
  14. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, 2014.
  15. Ueli Peter. Random Graph Models for Complex Systems. PhD thesis, ETH Zürich, 2014. Google Scholar
  16. Ira Sheldon Pohl. Bi-directional and Heuristic Search in Path Problems. PhD thesis, Stanford University, 1969. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact