Many important problems in computer networking depend on the observed properties of network graphs --- graphs obtained by measuring real network. These include networks of routers, autonomous systems, wireless nodes, and social relationships. Unfortunately, despite the explosion of detailed data now available, such graphs are still poorly understood, in part because of the high dimensionality of graph data. The project is developing new methods for, and applications of, dimensionality reduction of network graphs. The starting point is recent work by illustrating the power of hyperbolic geometry for the problem. Accordingly, the project has three goals: developing new methods for dimensionality reduction by embedding network graphs in hyperbolic spaces; discovering the applicability of hyperbolic embedding for a wide range of network graphs; and applying hyperbolic embedding to address practical networking questions. Among the problems being investigated is finding new methods for routing that combine the simplicity of greedy routing with the desirable properties of high success rate and efficiency of paths. The project's results will create unique software tools for the community, facilitating research in this area by others; it will shed new light on the properties of graphs that are important to networking; and it will develop new methods for routing that may be used in future networks. This project will provide training for two graduate students and its results will be disseminated in the form of both publications and freely distributed software.
One of the most basic challenges in building communication networks like the Internet is in designing algorithms for routing -- that is, algorithms for computing the path a packet should travel from its source node to its destination node. This project has developed new routing methods that are particularly simple, scalable, and effective. The core idea is to assign nodes to points in space and to forward packets from point to point in the "direction" of the destination -- an approach called "greedy routing." Greedy routing is very appealing because nodes only need to keep track of the positions of their neighbors (rather than tracking information about every other node in the network). Unfortunately, greedy routing cannot work in general when nodes are placed in Euclidean space (the everyday kind of space that we live in). This project has shown how to use a different kind of space (discovered in the 19th century) called hyperbolic space to solve problems in greedy routing. Hyperbolic space has the property that it expands with distance much faster than Euclidean space, and this makes it possible to place network nodes in such a way that greedy routing always succeeds. The project has delivered a number of research products that are of benefit to engineering and to society generally. The project produced the first software package capable of placing networks into hyperbolic space in an optimal fashion; this package is freely distributed in open source form by the project investigators. This package enables other researchers to experiment with and study networks in hyperbolic space. The project also produced the first algorithms that allowed growing networks (networks that are adding nodes) to be embedded in hyperbolic space in a fashion that ensures greedy routing will always succeed. This result has been widely cited in the literature and has led to considerable follow-on work by other researchers. Finally, the project also produced the first algorithms that allowed networks to be embedded in hyperbolic space in a way that attempts to minimize the lengths of the paths taken by packets. All of these results have been published in the open, peer-reviewed literature (conferences and journals). The project has been the training ground for multiple graduate students, who have developed expertise in network measurement, network analysis, routing algorithms, and non-Euclidean geometry. The researchers supported by this project include one student whose PhD thesis was entirely based on the research funded by this grant.
