TY  - JOUR
A1  - Bläsius, Thomas
A1  - Freiberger, Cedric
A1  - Friedrich, Tobias
A1  - Katzmann, Maximilian
A1  - Montenegro-Retana, Felix
A1  - Thieffry, Marianne
T1  - Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
JF  - ACM Transactions on Algorithms
N2  - A standard approach to accelerating shortest path algorithms on networks is the bidirectional search, which explores the graph from the start and the destination, simultaneously. In practice 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. <br /> To explain the observed behavior of the bidirectional search, we analyze its running time on hyperbolic random graphs and prove that it is (O) over tilde (n(2-1/alpha) + n(1/(2 alpha)) + delta(max)) with high probability, where alpha is an element of (1/2, 1) controls the power-law exponent of the degree distribution, and dmax 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.
KW  - Random graphs
KW  - hyperbolic geometry
KW  - scale-free networks
KW  - bidirectional shortest path
Y1  - 2022
U6  - https://doi.org/10.1145/3516483
SN  - 1549-6325
SN  - 1549-6333
VL  - 18
IS  - 2
SP  - 1
EP  - 32
PB  - Association for Computing Machinery
CY  - New York
ER  -