# Bidirectional Search in a Realistic Graph Model

## Master Project - Summer 2017

Supervisors: Prof. Dr. Tobias Friedrich, Dr. Thomas Bläsius

Advisor: Maximilian Katzmann

**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 [1].

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 [1]. 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 [2]. 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.

[1] | 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. |

[2] | Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá: Hyperbolic Geometry of Complex Networks, Phys. Rev. E 82 doi.org/10.1103/PhysRevE.82.036106 |

# Results

The results of the project have 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:

**Project Supervisor**

Hasso Plattner Institute

Office: A-1.10

Tel.: +49 331 5509-410

E-Mail: friedrich(at)hpi.de

**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

Links: Homepage, Publications

**Advisor**

Chair for Algorithm Engineering

Hasso Plattner Institute

Office: A-1.13

Tel.:

E-Mail: Maximilian.Katzmann(at)hpi.de

Links: Homepage, Publications

## 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