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.
