×

zbMATH — the first resource for mathematics

Efficient shortest paths in scale-free networks with underlying hyperbolic geometry. (English) Zbl 07375947
Chatzigiannakis, Ioannis (ed.) et al., 45th international colloquium on automata, languages, and programming. ICALP 2018, Prague, Czech Republic, July 9–13, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 107, Article 20, 14 p. (2018).
Summary: 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 \(\widetilde{\mathcal{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.
For the entire collection see [Zbl 1392.68012].
MSC:
68Nxx Theory of software
68Qxx Theory of computing
Software:
KADABRA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Gregorio Alanis-Lobato, Pablo Mier, and Miguel A. Andrade-Navarro. Manifold learning and maximum likelihood estimation for hyperbolic network embedding. {\it Applied Network} {\it Science}, 1(10):1-14, 2016. doi:10.1007/s41109-016-0013-0.
[2] Thomas Bläsius, Tobias Friedrich, and Anton Krohmer.Hyperbolic random graphs: Separators and treewidth. In {\it 24th ESA}, volume 57 of {\it LIPIcs}, pages 15:1-15:16, 2016. doi:10.4230/LIPIcs.ESA.2016.15.
[3] Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Cliques in hyperbolic random graphs. {\it Algorithmica}, 80:1-21, 2017. doi:10.1007/s00453-017-0323-3.
[4] Michel Bode, Nikolaos Fountoulakis, and Tobias Müller.On the giant component of random hyperbolic graphs.In {\it 7th EuroComb}, pages 425-429, 2013.doi:10.1007/ 978-88-7642-475-5_68.
[5] Marián Boguñá, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping.{\it Nature Communications}, 1:1-8, 2010.doi:10.1038/ ncomms1063.
[6] Michele Borassi and Emanuele Natale. KADABRA is an adaptive algorithm for betweenness via random approximation. In {\it 24th ESA}, pages 20:1-20:18, 2016. doi: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. {\it 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 {\it 25th ESA}, volume 87 of {\it LIPIcs}, pages 20:1-20:15, 2017. doi: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 {\it PODC ’17}, pages 371-380, 2017. doi:10.1145/3087801.3087829.
[10] Devdatt P. Dubhashi and Alessandro Panconesi. {\it Concentration of Measure for the Analysis} {\it of Randomized Algorithms}. Cambridge University Press, 2012.
[11] Tobias Friedrich and Anton Krohmer. On the diameter of hyperbolic random graphs. In {\it 42nd ICALP}, pages 614-625, 2015. doi:10.1007/978-3-662-47666-6_49.
[12] Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: Degree sequence and clustering. In {\it 39th ICALP}, pages 573-585, 2012. doi: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. {\it Phys. Rev. E}, 82:036106, 2010. doi: 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. {\it Random Graph Models for Complex Systems}. PhD thesis, ETH Zürich, 2014.
[16] Ira Sheldon Pohl.{\it Bi-directional and Heuristic Search in Path Problems}.PhD thesis, Stanford University, 1969.
[17] :14
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.