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.ĭmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguñá: Hyperbolic Geometry of Complex Networks, Phys. We offer an introduction into a late-breaking research topic which explores the connections between real-world networks and the hyperbolic geometry. You should be willing to find out on your own (or already know) how this is done. This consists of building a web application and might require setting up a client-server system and working with graphics cards. You should be interested in implementing a system that presents large amounts of data in a unique way. 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. Furthermore, achieving the desired efficiency and fluidity can require utilizing the clients graphics card. Determining which parts of the drawing are relevant to the user can be sped up using a geometric data structure. 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. 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 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. Consequently, such a visualization can be a powerful tool to understanding properties of networks with an underlying hyperbolic geometry. 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. 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. Usually, when visualizing networks with thousands of nodes it is hard to locate the smaller parts that are of special interest. Consequently, a visualization of the hyperbolic space results in a fish-eye view, as can be seen in the image below. In the latter space expands exponentially. The major difference between the well-known Euclidean geometry and hyperbolic geometry is the expansion of space. 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. 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.Ī very promising model assumes that a network has an underlying hyperbolic geometry and it was shown that many complex real-world networks actually do. 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. When analyzing the running time of graph algorithms, it is often observed that there is a huge gap between theory and practice.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |