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:

Error in extension PUMA/BibSonomy CSL (#13)!
CSL style 'clean-citation-style' not found. Import the missing style, clear the cache, and reload this page

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