Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Bidirectional Search in a Realistic Graph Model

Master Project - Summer 2017

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

This project has resulted in the following publications:

  • Efficient Shortest Paths ... - Download
    Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, Marianne Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic GeometryInternational Colloquium on Automata, Languages, and Programming (ICALP) 2018: 20:1–20:14
     

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

E-Mail: cedric.freiberger(at)student.hpi.de

Felix Montenegro-Retana

Project Participant


Chair for Algorithm Engineering
Hasso Plattner Institute

E-Mail: Felix.Montenegro-Retana(at)student.hpi.de

Marianne Thieffry

Project Participant

Chair for Algorithm Engineering
Hasso Plattner Institute

E-Mail: marianne.thieffry(at)student.hpi.de