Bläsius, Thomas ;
Freiberger, Cedric ;
Friedrich, Tobias ;
Katzmann, Maximilian ;
MontenegroRetana, Felix ;
Thieffry, Marianne
Efficient Shortest Paths in ScaleFree Networks with Underlying Hyperbolic Geometry
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 scalefree realworld networks. Such networks typically have a heterogeneous degree distribution (e.g., a powerlaw 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 powerlaw exponent of the degree distribution, and delta_{max} is the maximum degree. This bound is sublinear, improving the obvious worstcase linear bound. Although our analysis depends on the underlying geometry, the algorithm itself is oblivious to it.
BibTeX  Entry
@InProceedings{blsius_et_al:LIPIcs:2018:9024,
author = {Thomas Bl{\"a}sius and Cedric Freiberger and Tobias Friedrich and Maximilian Katzmann and Felix MontenegroRetana and Marianne Thieffry},
title = {{Efficient Shortest Paths in ScaleFree Networks with Underlying Hyperbolic Geometry}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {20:120:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9024},
URN = {urn:nbn:de:0030drops90246},
doi = {10.4230/LIPIcs.ICALP.2018.20},
annote = {Keywords: random graphs, hyperbolic geometry, scalefree networks, bidirectional shortest path}
}
04.07.2018
Keywords: 

random graphs, hyperbolic geometry, scalefree networks, bidirectional shortest path 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 