Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Master Project Summer Term 2018 - Visualizing Networks in Hyperbolic Space

Motivation

When analyzing the running time of graph algorithms, it is often observed that there is a huge gap between theory and practice.  The reason for this is that the instances that are found in the real world rarely resemble the worst-case instances used for the theoretical analysis.  One approach to understand this gap is to analyze a graph model that closely resembles the networks that occur in the real world and exploiting properties of the model that set it apart from the theoretical worst-case.

A very promising model assumes that a network has an underlying hyperbolic geometry and it was shown that many complex real-world networks actually do [1].  Under this assumption the shortest path between two nodes can be found in sub-linear running time and even the NP-hard problem of finding the largest clique in the network can be solved in polynomial time.

The major difference between the well-known Euclidean geometry and hyperbolic geometry is the expansion of space.  In the latter space expands exponentially.  Consequently, a visualization of the hyperbolic space results in a fish-eye view, as can be seen in the image below.  Usually, when visualizing networks with thousands of nodes it is hard to locate the smaller parts that are of special interest.  On the other hand, while zooming in and panning around reveals the details of parts of the network, it also loses the overall structure of the graph.  Using the fish-eye view, however, one can look at a specific part of the network in closer detail while still maintaining some sense of the larger structure.  Consequently, such a visualization can be a powerful tool to understanding properties of networks with an underlying hyperbolic geometry.

The Project: Visualization.

There are two commonly used models that represent the two-dimensional hyperbolic space, namely, the Poincaré Disk (which can be seen in the image above) and the native representation.  A visualization of a hyperbolic grid using the two models is shown in videos below.  Both of them highlight the content in the center.  The advantage of the Poincaré Disk is the stronger focus on the details in the center of the view.  The overall structure of the graph, however, is not as well preserved as in the native representation.

The Poincaré Disk Model

The Native Representation

The goal of this project is to build a web application that presents an interactive visualization of graphs in the hyperbolic plane using the above models.  Given a graph, the tool should compute the hyperbolic coordinates of the nodes (using a C++ program that is already available) and display the resulting drawing to the user who can then move around in it.  The main focus here lies on efficiency. In order to obtain a tool that allows for fluid movements through drawings of very large graphs, a client-server system might be necessary, that shifts costly (pre-)computations to the server and only submits the currently required data to the client.  Determining which parts of the drawing are relevant to the user can be sped up using a geometric data structure.  Furthermore, achieving the desired efficiency and fluidity can require utilizing the clients graphics card.  The challenges in this project thus lie in understanding the hyperbolic geometry and its different representations, and to setup a system that efficiently visualizes large amounts of data.

What you need. You should be interested in implementing a system that presents large amounts of data in a unique way.  This consists of building a web application and might require setting up a client-server system and working with graphics cards.  You should be willing to find out on your own (or already know) how this is done.

What we can offer. We offer an introduction into a late-breaking research topic which explores the connections between real-world networks and the hyperbolic geometry.  A tool is provided that, given a network, determines the hyperbolic coordinates of the nodes and an exemplary implementation of a visualization tool (which works on small networks) is already implemented and can be used as a reference.

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

Project Team

The Master Project is organized by the Algorithm Engineering Group. The following group members 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

Benjamin Feldmann

Project Participant

Chair for Algorithm Engineering
Hasso Plattner Institute


E-Mail: Benjamin.Feldmann(at)student.hpi.uni-potsdam.de

Ahmed Rekik

Project Participant

Chair for Algorithm Engineering
Hasso Plattner Institute


E-Mail: Ahmed.Rekik(at)student.hpi.uni-potsdam.de