 # Bidirectional Search in a Realistic Graph Model

## Motivation

In the analysis of algorithms, a major discrepancy between theory and practice comes from the fact that the analysis usually assumes worst-case instances while real-world instances behave very differently. One example is the bidirectional search, which computes the shortest path between two vertices $$s$$ and $$t$$ in a graph by starting a breadth-first search (BFS) from $$s$$ and from $$t$$ while stopping when the two search spaces meet. In the worst-case, this does not improve the running time compared to a single BFS starting at $$s$$. However, it has been observed that the bidirectional search leads to a significant speed-up on large real-world networks such as social networks or communication networks .

One approach to bridge this gap between theory and practice is to make an average-case analysis by bounding the expected run time under the assumption that the input is randomly drawn from a certain distribution. The practical relevance and explanatory power of such an average-case analysis of course heavily depends on the assumed probability distribution of the input. In case of the bidirectional search, it is actually known that it has a significantly sublinear run time on numerous random graph models . However, the analysis heavily relies on the fact that the edges in the random models under consideration are statistically independent. Unfortunately, this is a very unrealistic assumption: in a social network, two friends of a single person are much more likely to be friends of each other than two random people. Thus, the question why bidirectional search performs so well on large real-world networks remains unanswered.

## Purpose of the Project

We want to theoretically explain why the bidirectional search performs so well on large real-world networks. To this end, we want to bound its expected run time on a more realistic model for such networks, namely on hyperbolic random graphs.

## Hyperbolic Random Graphs

When thinking of complex real-world networks, there are two fundamental properties that come to mind. First, they are typically heterogeneous, i.e., they usually have some high-degree and many low-degree vertices (think of few very popular and many "normal" people in a social network). In fact, many real-world networks are scale-free, which means that the number of vertices of degree at most $$x$$ is roughly proportional to $$x^{−\beta}$$. One also says that such graphs have a power-law degree distribution with power-law exponent $$\beta$$. Second, vertices with a common neighbor should be more likely to be connected than vertices without common neighbors. Formally, this property can be expressed via the so-called clustering coefficient, which, roughly speaking, is the probability that two vertices with a common neighbor are connected.

Hyperbolic random graphs fit the bill as they combine a power-law degree distribution with a high clustering coefficient . They are generated by placing vertices randomly in the hyperbolic plane and connecting two vertices if and only if their hyperbolic distance is small. Note that two vertices that have a common neighbor are geometrically close to this neighbor and thus also close to each other, which increases their probability to be connected and leads to a large clustering coefficient. Moreover, choosing the hyperbolic geometry (instead of the Euclidean) leads to the desired degree distribution.

  Michele Borassi, Emanuele Natale: KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation, ESA 2016 dx.doi.org/10.4230/LIPIcs.ESA.2016.20.  Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá: Hyperbolic Geometry of Complex Networks, Phys. Rev. E 82 doi.org/10.1103/PhysRevE.82.036106

# Results

This project has resulted in the following publications:

# Project Team

The Master Project is organized by the Algorithm Engineering Group. The following group members and students are participating:

## Prof. Dr. Tobias Friedrich

Project Supervisor

Hasso Plattner Institute

Office: A-1.10
Tel.: +49 331 5509-410
E-Mail: friedrich(at)hpi.de

## Dr. Thomas Bläsius

Project Supervisor

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: A-1.4
Tel.: +49 331 5509-412
E-Mail: Thomas.Blaesius(at)hpi.de

## Maximilian Katzmann

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: A-1.13
Tel.:
E-Mail: Maximilian.Katzmann(at)hpi.de

## Cedric Freiberger

Project Participant

Chair for Algorithm Engineering
Hasso Plattner Institute

## Felix Montenegro-Retana

Project Participant

Chair for Algorithm Engineering
Hasso Plattner Institute

## Marianne Thieffry

Project Participant

Chair for Algorithm Engineering
Hasso Plattner Institute