Project Summary

The lack of predictive power over complex systems, either designed by humans or evolved by nature, is a foundational problem in contemporary science. The Internet offers a paradigmatic example: nothing in its architecture and design explains its complex large-scale structure, unexpectedly discovered decades after its inception. We face an unsettling truth: the Internet has acquired emergent properties that are beyond our full understanding, much less control.

As scientists, we are compelled to explore how the peculiar structure relates to the function(s) of complex networks. Many complex networks in nature share the peculiar structural character of the Internet, but they also manifest phenomenal behavior: they efficiently route information without any observable routing communication protocol. This achievement is currently beyond the reach of man-made networks. The Internet still uses a 30-year old routing architecture with fundamentally unscalable overhead requirements. Yet in those 30 years, the Internet's inter-domain topology has evolved toward a structure for which nature has superior routing technology, if only we can figure out how to use it!

The prospect of zero-overhead routing is sufficiently attractive that in our previous NeTS-FIND project we developed a new theoretical framework to study it. We now propose to apply that framework in a broader network scientific context. In our framework, nodes in real networks exist in a separate but related hidden metric space, which guides routing without overhead or topology knowledge. We found strong evidence that not only do hidden metric spaces underlie real complex network topologies including the Internet, but that a greedy routing mechanism applied to such topologies and underlying spaces yields a maximum percentage of paths that successfully reach their destinations. Remarkably, these successful paths almost always are shortest, regardless of the hidden space structure. This explanation for why (if not how) complex networks are naturally navigable had sufficiently high interdisciplinary impact for recent publication in Nature.

However, even though almost all successful greedy paths are shortest, not all paths are successful. The percentage of successful paths does depend on the hidden space structure. The intellectual merit of our proposed work will lie in the identification of hidden spaces that make all greedy paths both shortest and successful. The most basic geometric property of a space is its curvature K. Spaces fall into three categories depending on their curvature K: Euclidean (K=0), spherical (K > 0), or hyperbolic (K < 0). We propose three tasks to explore the hypothesis that spaces hidden under real networks, including the Internet, are hyperbolic. First we will show analytically that the negative curvature of hidden geometries not only provides an explanation for the basic common structural properties of complex networks, but also optimizes an already efficient new approach to routing over such networks. Second, we will verify that hidden spaces underlying real networks are in fact negatively curved, and measure their basic geometric properties. Finally, our most challenging task will be to construct embeddings of the Internet and other complex networks into the identified hyperbolic spaces.

One broader impact of discovering a hidden space for the Internet and other communication networks that require transmission of topology updates is the removal of a fundamental scaling limitation these networks face. But elucidating this mysterious connection between network structure and function implies impact far broader than the Internet, including for recommender systems, search engines, terrorist network modeling, cancer and brain research, protein folding, and drug design. The proposed work will not only improve our knowledge of the basic principles of organization, function, and evolution of large-scale complex networks, but also transform research on how to model, predict, and control complex networked systems.